数据结构–红黑树

首先明白红黑树的5条性质就好理解了:

  1. 结点都是红色或者黑色组成
  2. 根节点是黑色结点
  3. 每个叶结点都是有两个NIL结点组成,默认为黑色结点
  4. 红色结点不能想连,其父节点和子节点一定是黑色结点
  5. 从任意结点出发到NIL结点的普通路径上黑色结点的个数相等

这几条性质保证了红黑树的平衡性,不断插入或者删除的时候,左右子树不会出现大的不平衡,尤其是第5条
红黑树的结点有三个指针,左右孩子和父指针

插入

那么插入的时候实际上很好想了,自己做几个例子就明白了,

小技巧:动手枚举情况,然后总结规律

分为5种情况:

  1. 插入结点为 root
  2. 插入结点的父节点为黑色(无操作)
  3. 插入结点父节点为红色,叔叔结点也是红色
  4. 插入结点父节点为红色,叔叔结点为黑色,插入点并且和父亲方向相反
  5. 插入结点父节点为红色,叔叔结点为黑色,插入点并且和父亲方向相同

其实都是蛮简单的处理就OK了,就是这几个条件的初始规律比较难发现

然后我们分情况进行讨论:

1. 插入结点为 root 或者父节点为黑色
直接插入,设置颜色为黑色
2. 插入结点的父节点为黑色
直接插入,无需变色
3. 插入结点父节点为红色,叔叔结点也是红色
祖父结点变红色,父亲和叔叔结点变黑色
然后指针转道祖父结点,继续向上调整,重新从步骤1开始判断
1

4. 插入结点父节点为红色,叔叔结点为黑色,插入点并且和父亲方向相反
首先旋转至一致的方向
如果父节点为祖父结点左儿子,父亲结点右旋
父节点和祖父结点交换颜色,祖父结点左旋
插入之前经过G的左右子树的黑色结点数量是 U + 1
经过调整之后,虽然暂时违反性质4,但是黑色结点数量被维护了
然后现在相当于下一阶段的情况5

2

5. 插入结点父节点为红色,叔叔结点为黑色,插入点并且和父亲方向相同
如果父节点为祖父结点左儿子,父节点和祖父结点颜色交换,然后祖父结点右旋

如果父节点为祖父结点的右儿子,父节点和祖父结点交换颜色,然后祖父结点左旋
旋转之前 Bh(U)+1 = Bh(1)+1
旋转之后 Bh(U)+1 = BH(1)+1
黑色结点数量保持不变

3

发现只有情况3的插入情况才能引起祖父结点以上的结点发生变化,而其他的均是本地调整就行

删除

红黑树的删除和二叉树的删除关系紧密,我们只需要考虑最多只有一个子树的删除,因为有两个非空子树的结点,最后的删除对象能够转移到例如左子树的左右子树这样的结点上来。

我们首先把要删除的节点N替换为它的左儿子的最右或者右儿子的最左叫做CHILD(只选一种) ,如果都没有则用自身表示并继续用N表示,这个删除任意结点的问题就转化为删除该子节点了(有1个或者2个空节点)。

我们这里选择左子树的最右结点, 用 n 表示 要被 删除的结点(也就是找到的CHILD), 用 child 表示要替换 n 的左子树(如果为空则是Nil 结点)n的兄弟结点是S,他的两个孩子 SL 和 SR,代码中的处理逻辑是先从n开始调整,整体调整完毕之后,再删除n,所以调整和删除并不是同时进行的,如果出现需要向上调整的情况,直接将n赋值为要调整的结点。

删除实际上也是可以分情况的,不过情况比较多,分为一下几种情况:

  1. n是根节点,直接删除n
  2. n是红色
  3. n是黑色,Child是红色
  4. n是黑色,Child是黑色,S是红色(P是黑色)
  5. n是黑色,Child是黑色,S是黑色,P是红色, SL和SR同为黑色
  6. n是黑色,Child是黑色,S是黑色,P是黑色,SL和SR同为黑色
  7. n是黑色,Child是黑色,S是黑色,P是任意,与N方向相反的点为黑色,另一个为红色
  8. n是黑色,Child是黑色,S是黑色,P是任意,与N方向相反的点为红,另一个为黑色或者红色

处理方法:
0. 要替换的结点是根节点,说明树只有一个根结点,直接删除n就行
1. 如果要删除的结点是红色,删除n,那直接将父节点指向child结点就行
n 是红色结点,那么child 以及n的 parent 一定是 黑色结点,直接将 parent的对应的 孩子 替换为child即可,性质4,5 都不会破坏
2. n是黑色,Child是红色 ,child变为黑色,删除n
n是黑色如果删除的话,经过n的所有分支黑色数量会减少,为了维持性质5,直接将子节点上提变色

可以发现情况0-2都是最简单的直接操作,之后的3-7的情况n都是黑色,删除黑色结点的硬性主要是性质5,经过n的路径上的黑色结点数量变少,所以我们的调整方式会变的复杂一些,但主要目的就是为了维持经过n的黑色结点数量尽可能和原来的保持一致,如果实在不能一致,需要先转化为状态,再调整,例如3,那就需要进行向上的调整了。

3. n是黑色,Child是黑色,S是红色(P是黑色)
n是黑色如果删除的话,经过n的所有分支黑色数量会减少,需要进行操作维持性质5。
从父节点开始进行左旋(逆时针),然后P和S变色,如下图:

d1

    这时候我们发现SL 和 SR 这两个分支上的黑色结点数量和原来是一致的,但是N还是不确定,但问题已经转化为,情况 4 || 6 || 7 。

4. n是黑色,Child是黑色,S是黑色,P是红色, SL和SR同为黑色
在这种情况下,我们的问题是删除n之后P的左右子树不平衡,性质5被违反了
这种情况实际上很好解决,能让S分支黑色结点数量不变,且N分支黑色数量结点+1的方法是,直接将P变为黑色,S变为红色,问题就解决了

5. n是黑色,Child是黑色,S是黑色,P是黑色,SL和SR同为黑色
这种情况实际上是情况4的一个小变种,在这种情况下,无论如何调整,经过P的路径黑色节点数肯定会少1的,只能是首先保证删除N之后,经过P的两个子树的黑色结点数量先保持一致,然后问题集中到了P结点,那么指针移动到P结点,重新从情况1开始调整
d3

 接下来的两种情况,我们来说明一下同向和反向结点的概念,n为父节点左子树,则S的左子树称为n的同向结点,反之是n的反向结点。

肯定会发现一个和上面条件不一样的地方是P颜色是任意的, 情况6和情况7都是这样的,这是因为如果出现SL 或者 SR 为红色的情况,那么父节点的颜色肯定是不用换了,保持黑色结点不变的方法肯定是将 父节点 旋转到 N的分支上(变黑),然后把S提上来(保持父节点颜色),并且将S的反向子节点变黑,同向结点分给P做为子结点,所以父亲结点P什么颜色在这种情况下并不重要。

如果反向结点为红色,这里颜色随便,可以进行调整(情况7),如果反向结点为黑色,这里必须是黑色才能进行调整(情况4,5),但如果同向为红色,反向为黑色则需要进行调整了(情况6)。

6. n是黑色,Child是黑色,S是黑色,P是任意,与n反向的子结点为黑色,同向为红色
通过上面的分析,可以知道同向结点需要是黑色的,在不改变S的左右黑结点数量的情况下,将同向结结点变为黑色,就是让S按照同向的方向旋转,(左结点左旋,右结点右旋),如下图,这样就能保证同向结点为黑色了。
d5

7. n是黑色,Child是黑色,S是黑色,P是任意,与N同向的点为红,另一个为黑色或者红色
这个处理步骤实际上在上面的分析中给出了,P转向n所在的分支,变黑,S转到P的位置,保持P颜色,反向结点变为S的子子结点,变黑,操作如下图:
d4

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.