红黑树学习系列笔记 (一)

本贴最后更新于 1861 天前,其中的信息可能已经事过境迁

定义和性质

  1. 节点不是红色的就是黑色的
  2. 根节点是黑色的;
  3. 叶子节点是黑色的(NIL)空节点
  4. 红色的节点不能相邻,红色节点的子节点必须是黑色的
  5. 任意一节点到每个叶子节点的路径都包含数量相同的黑节点。

红黑树封面

三种操作:左旋、右旋和变色。

  1. 左旋:以某个节点作为支点 (旋转节点),其右子节点变为旋转节点的父节点,右子节点的左子节点变为旋转节点的右子节点,左子节点保持不变。
  2. 右旋:以某个节点作为支点 (旋转节点),其左子节点变为旋转节点的父节点,左子节点的右子节点变为旋转节点的左子结点,右子节点保持不变。右旋只影响旋转节点和其左子树的结构,把左子树的节点往右子树挪了。
  3. 变色:结点的颜色由红变黑或由黑变红。

旋转示意图

  • 左旋只影响旋转节点和其右子树的结构,把右子树的节点往左子树挪了。
  • 右旋只影响旋转节点和其左子树的结构,把左子树的节点往右子树挪了。

插入操作

情景 1 :关注节点的父节点为黑节点

由于插入的节点是红色的,当插入节点的黑色时,并不会影响红黑树的平衡,直接插入即可,无需做自平衡。

情景 2:关注节点结点的父结点为红节点

此时的祖父节点一定是黑色的,

2.1 关注节点的叔叔节点存在并且为红节点

CASE 1

操作

  • 将父节点和叔叔节点的颜色对换,
  • 此时的关注节点为祖父节点 C
情景 2.2 叔叔节点是黑色,关注节点是其父节点的右子节点,

CASE 2

操作

  • 关注节点变成节点 a 的父节点 b;
  • 围绕新的关注节点 b 左旋;
  • 跳到 CASE 2.3

情景 2.3:关注节点的叔叔节点不存在或为黑结点,并且关注节点的父亲结点是祖父结点的左子结点

CASE 3

操作

  • 围绕关注节点的祖父节点右旋
  • 将旋转后的关注节点的父节点、兄弟节点的颜色互换。

公众号

相关帖子

欢迎来到这里!

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

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

    图片都挂掉了

  • someone
    作者

    使用的是七牛的文件储存作为图床,我浏览是正常的哎,

    1 回复
  • 88250

    社区这边加载不了非 HTTPS 的图 🤣

  • someone
    作者

    好的,谢谢指导,我试试 https 的

  • 红树好看还是黑树好看,