红黑树的增加

   声明:本站部分内容来自互联网,如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。

27

类比于234树,4阶B树所有节点的元素个数 x 都符合 1 ≤ x ≤ 3

性质:

1. 节点是 RED 或者 BLACK

2. 根节点是 BLACK

3. 叶子节点(外部节点,空节点)都是 BLACK

4. RED 节点的子节点都是 BLACK ✓ RED 节点的 parent 都是 BLACK ->从根节点到叶子节点的所有路径上不能有 2 个连续的 RED 节点

5. 从任一节点到叶子节点的所有路径都包含相同数目的 BLACK 节点

红黑树的增加(添加的都是红色)

根节点必须是黑色

1.添加节点的父节点是黑色,不做任何改变

2.添加的节点的父节点是红色

        1.父节点是祖父节点的左孩子/右孩子 且祖父节点只有一个孩子

        1.1添加到父节点左边LL/父节点右边RR         52 60

                只需要进行右旋和左旋,

         1.2添加到父节点的右边LR/RL

                将添加节点和父节点做一个旋转,转化为1.1,再旋转即可

        2父节点是祖父节点的左孩子/右孩子 且祖父节点有2个孩子

        这个时候就不能单纯旋转就可以解决,可以将祖父节点染红当成添加节点添加到上面去,然后把父节点和叔叔节点染黑,向上递归添加操作

        

 

 此时可以看作把父亲节点和叔叔节点染黑独立出来,将祖父节点染红,添加到根节点的左边,因为根节点是黑色的,所以直接添加即可。

 

这种也是一样