红黑树原理

tech2022-12-04  9

1.二叉查找树

     1.特点:

             左子树所有节点小于根节点   右子树所有节点大于根节点,左右子树分别是一棵二叉查找树。

      2.举例:

             

2.红黑树 【二叉查找树+自平衡(自旋+变色)】

     1.特点

              1.节点分为红色或者黑色

              2.根节点必为黑色

              3.叶子节点都为黑色,且为null

              4.连接红色节点的两个子节点都为黑色(红黑树不会出现相邻的红色节点)

              5.从任意节点出发,到其每个叶子节点的路径中包含相同数量的黑色节点

              6.新加入到红黑树的节点为红色节点

     2.红黑树插入

    名称约定:

 

举例:

例:插入 10,20,15,30,5,8; 为了简化,图中没有画出null的黑色节点。

 3.红黑树删除

名称约定:

 

 实例:

(1)删除50,删除动作-情形3 --> 删除动作-情形2,简单处理即可:

 (2)删除70,即黑色叶子节点,进行平衡:

(3)删除60:

 (4)删除10:

(5)删除20:

参考资料:https://www.jianshu.com/p/a9c064d38a92

最新回复(0)