红黑树笔记

红黑树学习

rb1:根结点必须是黑色，空叶子结点视为是黑色

rb2:不能有两个相邻的红色节点（父节点和子节点不能同时为红色）

rb3:从根结点到任意空叶子结点的路径的黑色结点数相等。

衍生推论：

1.红黑树从根结点起，最长路径比最短路径节点数比，不会超过2:1

2.以红黑树任意黑色节点为根，都是一颗红黑树

3.任意节点到外部节点的所有路径中，黑色节点数是一致的。

术语：

外部节点：红黑树的空叶子节点

红黑树节点的阶：一个节点到外部节点的路径中的黑色节点数，是红黑树的阶。

rb2不平衡状态：插入操作中会出现，即违反了相邻节点不能是红色节点的规则的状态，有八种情况

LLr,LLb,LRr,LRb,RLr,RLb,RRr,RRb.

现有节点X

第一个字母表示：L即X的左子节点为红色，R即X的右子节点为红色

第二个字母表示：L即第一个字母对应的节点的左叶子节点为红色，R即第一个字母对应的右叶子节点为红色。

第三个字母表示：X的另一个子节点颜色。r红色，b黑色

LLr为例子：代表X节点的左节点及左节点的左节点为红色，X的右节点为红色

RLb为例子：代表X节点的右节点及右节点的做节点为红色，X的左节点为黑色

插入操作：

新插入的节点都是红色节点，因为插入黑节点会导致rb2定律不符合，且很难调整。

如果是XYr型(LLr,LRr,RLr,RRr)不平衡状态，需要进行变色操作，其余的需要进行旋转。

变色：XYr型不平衡状态，左右子节点都是红色节点，为了保持rb3规则，此时需要将当前节点变红色，子节点都变为黑色，这样变色不会影响到rb3规则。

变色之后可能会产生新的不平衡状态。除了8中不平衡状态，还有可能出现根结点变红，如果根结点变红直接染黑。其余8种不平衡状态，依然照常处理，直至平衡。

删除操作：

删除操作和插入操作大同小异，就是分析不同的情况进行染色或者旋转，删除略微复杂一下，大概思想了解了就行了，不再详述了。

性能分析：

红黑树在删除和插入的时候平均性能比较好，因为有概率只需要染色不需要旋转。

红黑树是不平衡的，但是因为rb2的缘故，极端情况下，红黑树从根结点出发的最长路径最多比最短路径长一倍。红黑树节点越多，性能差异就越小，在实际查询中，性能差异基本可以忽略。

红黑树实现相对复杂一些。