平衡二叉搜索树（AVL）和红黑树（RB-Tree）

二、红黑树——一种常被使用的平衡二叉搜索树

1、四大性质

• 1、每个节点都有颜色，要么黑色，要么是红色。
  2、树的根节点必须是黑色。
  3、父子两节点不得同时为红色。
  4、任一节点到叶子节点的每条路径上的黑色节点个数必须相同。

2、由四大性质引出的要插入的节点性质讨论

• 由二叉搜索树的性质可知，插入的节点一定是作为叶子节点。
• 可将当前叶子节点的下一NULL节点看做黑色。
• 由性质4可知，插入的叶子节点的颜色一定是红色。
  否则为黑色，该路径黑色节点+1，会破坏原红黑树的各条路径的黑色节点总个数相同原则。
• 由上可知插入节点必为红色，然后结合性质3可知，若其父节点为黑色，则没问题可以直接插入。
  但是，若其父节点为红色，则必然引起【父子节点同时为红色】的冲突。此时就要旋转节点和给节点变色，直到满足红黑树的四大性质。

3、红黑颜色的本质是bool值，红色是false0，黑色是true1

image.png

4、红黑树增加一个特殊的header节点

初始时，herder的左右子节点都指向本身，插入节点后；左子节点作为begin()指向的是(most)left最左边也就是最小值；右子节点作为end()指向的是(most)right最右边也就是最大值。

image.png

5、迭代器++和--的特殊操作

• 双向单步迭代器类型，和list一样，也是不能跳步随机访问的。
• ++和--跳到的元素，实际上是按照二叉搜索树的中序遍历排序结果来移动。
  ++就是移动到排序序列中的下一个元素位置，实际上指针再树中的移动情况可能更麻烦。
  --就是移动到排序序列中的上一个元素位置。
• 比较特殊的header和root，若是root没有右子节点（或左子节点），那么root++（或--）就到了header。因为root和header互为parent父节点。

6、AVL-tree平衡二叉树的平衡破坏情况

每个结点有一个元素是平衡因子Balance Factor，BF=该结点左子树高度-右子树高度，当BF的绝对值大于1时说明平衡被破坏。距离插入结点最近的BF绝对值大于1的结点，就作为要开始接受调整的结点，以它为根的子树叫做最小不平衡子树。

AVL-tree平衡调整

6.1、红黑树新插入节点保持平衡的变色和旋转条件

• 新插入节点X（红色）的父节点若是黑色，则直接插入，无冲突。（如根节点默认黑色，则刚开始的左右子节点都无冲突插入）
• 新插入节点X（红色）的父节点也是红色，那么一定有冲突。要么只进行变色，要么旋转（旋转一定附带变色）。【下面讨论的一定是这种父节点为红色有冲突的情况】
• 【X的父节点有兄弟，即X有伯父】

不管是左左（父节点是祖父节点的左子节点，X节点又是父节点的左子节点，后面同理）、左右、右左、右右，全部都只需要变色处理，而不需要旋转。
为了满足性质3【父子节点不能双红】则需要将父节点和伯父节点都转为黑色。此时这两路径黑色节点数+1，为了满足性质4【各节点所有路径黑色节点数相同】则需要将祖父节点变为红色。然后还需要继续向上检查是否有父子双红的颜色冲突，有的话就还需要继续向上变色处理，可能直到根节点才结束。

• 【X的父节点无兄弟，即X无伯父】

1、左左，单右旋转，附带变色。
2、右右，单左旋转，附带变色。
3、左右，先单左再单右的双旋转，附带变色。
4、右左，先单右再单左的双旋转，附带变色。

7、关于单旋转，双旋转的细节

单左旋。对应右右，或者左右的第一次旋转

单左旋

单右旋。对应左左，或者右左的第一次旋转

单右旋

8、平衡调整函数，调整颜色、调整位置（调用左旋转和右旋转）

调整平衡树函数

一个图示实例：将序列10、7、8、15、5、6、11、13、12依次插入红黑树的调整过程》》》》》