学习笔记 | 红黑树的故事

红黑树是一个平衡二叉树,他的左右子树的高度不能相差超过 1

节点结构

颜色(color),左子树指针(left),右子树指针(right),父节点指针(parent),数值(value)

规则

1. 每一个节点都是有颜色的,红色或者黑色
2. 根的颜色是黑色的
3. 叶子节点也是黑色的(指的是不存在的叶子结点)
4. 两个红色节点不能相连(两个黑色节点可以)
5. 从任意一个节点出发到叶子结点,路过的黑色节点数量相等

旋转

左旋

右旋

新节点的插入

插入规则

1. 插入的节点默认是红色的
2. 假如插入节点的父节点是黑色的,则不会变形
3. 假如插入节点的父节点是红色的,要通过重新着色或者是旋转来保持平衡

插入情况

根节点

直接插入并且设置为黑色

父节点是黑色节点

直接插入,颜色为红色

父节点是红色节点,叔叔节点也是红色节点

将父和叔节点设为黑色,爷爷节点(父节点的父节点)设为红色,同时将爷爷节点作为新节点向上检查颜色(递归处理)

父节点是红色节点,叔叔节点是黑色或者不存在,新节点是父节点的右节点

情况一:左旋 + 变色

情况二:左旋 + 右旋 + 变色

父节点是红色节点,叔叔节点是黑色或者不存在,新节点是父节点的左节点

情况一:右旋 + 变色

情况二:右旋 + 左旋 + 变色

节点的删除

节点的删除并不是真正的删除,而是用其后继节点来代替它(值拷贝),然后删除原来的后继节点就好了

0. 假如删除的是红色节点,由于黑色节点的个数不会变,所以红黑树的性质不会改变,假如是黑色节点,要判断是否改变颜色(❤️ 注意这句话)
1. 是叶子节点,直接删除
2. 只有一个子节点,用子节点代替删除的节点并删除原来的子节点
3. 有两个子节点(子节点是要删除的后继节点的父节点的子节点)
   1. 删除节点的兄弟节点是红色节点
      
   2. 删除节点的兄弟节点是黑色节点,且只有右节点
      
   3. 删除节点的兄弟节点是黑色节点,且只有左节点,得到的结果是第二种情况
      
   4. 删除节点的兄弟节点是黑色节点,且有两个节点(n 是删除节点)