红黑树的属性，优点，以及插入介绍
发布于 5 年前 作者 TimLiu1 9020 次浏览 来自 分享

红黑树的属性，优点，以及插入介绍

学习: 在这篇文章中，我们主要学习三个点

  • 红黑树简介
  • 红黑树有优点
  • 红黑树的插入逻辑

红黑树

红黑树是一种自我平衡的红黑二叉树，红黑树满足所有的二叉查找树的属性，同时一些额外的属性被添加在红黑树中，红黑树的每个节点是黑色或则红色，它的高度是O(logn),n是这颗树的节点数量

红黑树的属性

  • 根节点总是黑色(其实也可以是红色，但是这个算法随机选择了一种规定)
  • 在红黑树中每个节点的空子节点代表黑色
  • 红色节点的子节点必须是黑色，红色节点的父节点也必须是黑色
  • 所有的叶子节点有相同的黑色节点深度
  • 每个简单路径来自于根节点到叶子节点有相同数量的黑色节点

红黑树的展示

image.png 当呈现一棵红黑树的时候所有的节点都应该被呈现出来，被标记为null的节点不是真正的物理节点，很容易从上面的节点看出红节点后面一定是黑色的节点，从上面这棵树可以总结出如下属性

  • 这是一棵二叉查找树
  • 根节点是黑色的
  • 红色节点的子节点一定是黑色的
  • 所有从根到外部节点的路径包含相同的黑色节点 比如 75-90-80-88-null 和 75-40-30-null 都包含三个相同的节点

红黑树的优点

  • 红黑树是效率相对较高的当我们插入和删除数据相对频繁的时候
  • 红黑树是自我平衡的所有操作的复杂度最多是O(logn)
  • 不管怎么变化，只有红黑两个常数

插入数据

需要被插入的数据应该被标记为红色 并不是每一个插入的节点都会造成不平衡，但是如果造成了不平衡，需要删除不平衡，删除操作依赖于这棵树之前的布局 当不平衡发生时，通常会使用

  1. 重新标记颜色
  2. 滚动

为了更深刻的理解插入操作，让我们先做如下假设 a. u是最新需要插入的节点 b. p是u节点的父亲节点 c. g是u节点的祖父节点 d. Un是u节点的叔叔节点

一个新节点插入之前这棵树肯定是一棵平衡数，但是当我们插入新节点的时候就会打破平衡，这时我们首先会采用转换颜色，如果还没有删除平衡，我们在滚动节点让树达到平衡

案例1

不平衡的发生主要是和叔叔节点相关，如果叔叔节点是红色的，那么有四种场景需要处理，可以通过重新调换颜色可以删除不平衡

1. LRr 不平衡

因为p是g的左节点，u是p的右节点，所以称为左右不平衡，不平衡的原因是因为插入的节点必须是红色的，但是红色节点不能相邻，所以需要其中一个变为黑色，所以需要重新标记颜色 image.png 删除左右不平衡可以通过下面几步

  • 把p的颜色变为黑色
  • 把Un的颜色变为黑色
  • 如果g不是根节点，则改变g为红色

注意 如果g是根节点则不需要变色 为什么这三个步骤能够删除不平衡，因为转换p和Un能够保证以g为根节点的两条线的黑色节点数量是相同的，但是如果g不是根节点，那么其实每条线黑色节点+1，需要减1，所以g的颜色需要变成红色，之后三个案例类似

2. LLr 不平衡
 因为p是g的左节点，u是p的左节点，所以称为左右不平衡，不平衡的原因是因为插入的节点必须是红色的，但是红色节点不能相邻，所以需要其中一个变为黑色，所以需要重新标记颜色

image.png 删除左右不平衡可以通过下面几步

  • 把p的颜色变为黑色
  • 把Un的颜色变为黑色
  • 如果g不是根节点，则改变g为红色
3. RRr 不平衡

因为p是g的右节点，u是p的右节点，所以称为左右不平衡，不平衡的原因是因为插入的节点必须是红色的，但是红色节点不能相邻，所以需要其中一个变为黑色，所以需要重新标记颜色

删除左右不平衡可以通过下面几步

  • 把p的颜色变为黑色
  • 把Un的颜色变为黑色
  • 如果g不是根节点，则改变g为红色
4.RLr 不平衡

因为p是g的右节点，u是p的左节点，所以称为左右不平衡，不平衡的原因是因为插入的节点必须是红色的，但是红色节点不能相邻，所以需要其中一个变为黑色，所以需要重新标记颜色 image.png 删除左右不平衡可以通过下面几步

  • 把p的颜色变为黑色
  • 把Un的颜色变为黑色
  • 如果g不是根节点，则改变g为红色

案例2

不平衡在uncle节点是黑色的时候同样也会发生，下面有四种场景将会被提及，这四种场景的不平衡能够被通过移动节点删除 LR 不平衡 LL 不平衡 RR 不平衡 RL 不平衡

LL和RR不平衡能够通过下面两个步骤删除

a. p滚动占据g的位置，g滚动占据Un的位置 b. p重新标记为黑色，g重新标记为红色 image.png

这个逻辑也比较好理解，主要是保证以g为根节点的两个分支黑色节点数量不发生变化，后面类似

LR和RL不平衡能够通过下面两个步骤删除

a. u滚动两次占据g的位置，g成为u的子节点 b. 重新标记u为黑色，g和p为红色 image.png

提醒:

插入节点的默认颜色一定是红色 如果Un节点不存在则按照黑色节点的逻辑进行处理

(原文链接)[https://www.includehelp.com/data-structure-tutorial/red-black-tree.aspx]

回到顶部