红黑树

NIL

22

25

8

21

红黑树

左旋： 逆时针旋转，父节点被自己的右孩子取代，而自己成为自己的左孩子

向红黑树中插入14的节点，由于15是黑色节点，所以没有破坏结构，不需要做任何的改变

13

27

c

Y

X

15

1

17

a

6

右旋：顺时针旋转，父节点被做孩子取代，而自己成为自己的右孩子

b

11

如果向树中插入21的话，会破坏红黑树的规则，必须要调整，就是变色和旋转

红黑(Red-black)树       是一种自平衡二叉查找树，1972年由Rudolf Bayer发明，它与AVL树类似，都在插入和删除操作时能通过旋转操作保持二叉查找树的平衡，以便能获得高效的查找性能。它可以在 O(logn) 时间内做查找，插入和删除等操作。红黑树是2-3-4树的一种等同，但有些红黑树设定只能左边是红树，这种情况就是2-3树的一种等同了。对于AVL树来说，红黑树牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树。特点：       节点是红色或黑色。       根节点是黑色。       每个叶节点（NIL节点）是黑色的。       每个红色节点的两个子节点都为黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)       从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。       最长路径不超过最短路径的2倍

为了符合红黑树的规则，会把节点红变黑或者黑变红，21，22是连续的红色，因此要将22红变黑

此时还没有结束，因为25和27都出现了红色，因此需要将27变成黑色

基础知识补充

14

此时，不符合规则5，因此需要将25黑变红