学习笔记 | 红黑树的故事

本贴最后更新于 1709 天前,其中的信息可能已经物是人非

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

节点结构

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

规则

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

旋转

左旋

021036114848527.png

右旋

021036282345144.png

新节点的插入

插入规则

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

插入情况

根节点

直接插入并且设置为黑色

父节点是黑色节点

直接插入,颜色为红色

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

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

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

情况一:左旋 + 变色
1312454268b6930e4589487989eecad1e4825285.jpg
情况二:左旋 + 右旋 + 变色
1312455487c6459c6a9b44069022a8e8956e9e71.jpg

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

情况一:右旋 + 变色
13124530c257dc3cc2244676be93b8d0e1c54171.jpg
情况二:右旋 + 左旋 + 变色
13124607968c7d8de6b744a3857dcbf2ea86775a.jpg

节点的删除

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

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

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...