Contents

[数据结构]深入理解红黑树

平衡树

在谈红黑树之前,可以先看看红黑树的根源,234树。234树也是一种平衡树。
平衡树的原型都是二叉查找树,即左面的节点比他小,右边的节点比他大。但是在二叉查找树的过程中,很有可能变成树朝一边严重倾斜的情况。为了解决这个问题,设计了如下变种:

  1. avl:严格控制树的平衡,左右树的高度差不大于1。所以查找性能是logn。在插入和删除操作时,最差的情况是每一级的父节点都会旋转。时间复杂度都是O(logn)。
  2. 红黑树:红黑树的左右子树最高差时,一个子树是另一个子树的一倍。最坏查找性能是2logn。在插入操作时,最差旋转2次,删除操作最差旋转三次,可以减少avl的平衡操作,但是依然是O(logn)的复杂度(在找到节点的插入位置就要花费logn时间)。
  3. splay:插入删除复杂度也是O(logn),可以用数组实现,不需要额外维护树的节点信息。但在最坏情况下他会退化成一条链。而且只读操作也会影响树的结构,在多线程环境访问下比较复杂。
  4. 替罪羊树:在查找树不平衡的时候,找到最高的一个节点(满足左右子树不差0.7倍的平衡点),重构整个子树

查找问题还可以用哈希表解决。哈希表是无序的,而且会耗费大块的内存。
一些常见的面试题:常见面试题-cnblog

各种树的性能

2-3-4树

2-3-4树-CSDN
234树是红黑树的等价变种。先来看看2-3树,这种树有两种节点,2节点和3节点。
2-节点:普通节点,有两个子连接
3-节点:有两个值A、B,三个连接(分别指向小于A,介于AB之间,大于B的儿子)
2-3树可以保证插入的时候所有叶子到根节点的距离是相同的。我们看看他如何插入:
(1) 如果值插入2节点,把他扩充成一个3节点。
(2) 如果插入插入3节点
A. 整个树只有一个3节点:把他扩展成4-节点,然后分解4-节点,然后将分解后的新树的父节点融入到2-节点的父节点中去。
B. 3-节点有一个2-节点的父节点,此时的操作是,3-节点扩充为4-节点,然后分解4-节点,然后将分解后的新树的父节点融入到2-节点的父节点中去。
C. 3-节点有一个3-节点的父节点,此时操作是:3-节点扩充为4-节点,然后分解4-节点,新树父节点向上融合,上面的3-节点继续扩充,融合,分解,新树继续向上融合,直到父节点为2-节点为止,如果向上到根节点都是3-节点,将根节点扩充为4-节点,然后分解为新树,至此,整个树增加一层,仍然保持平衡。
23树的流程比较复杂,而且涉及不同节点的转换,所以出现了红黑树来简化操作。我们把3节点的两个元素红色连接连起来。这时候红色连接出去的那个节点就成了红黑树的红节点,其余的都是黑节点。如果你将红黑树中所有的红色链接放平,那么它所有的叶子节点到根节点的距离都是相同的,所以是一个完美的黑色平衡。
所以,红黑树的另一种定义是满足下列条件的二叉查找树:
⑴ 红链接均为左链接。
⑵ 没有任何一个结点同时和两条红链接相连。(这样会出现4-节点)
⑶ 该树是完美黑色平衡的,即任意空链接到根结点的路径上的黑链接数量相同。

红黑树

github红黑树(有比较好的图解)
cnblog红黑树流程详解
红黑树的五条性质:
1)每个结点要么是红的,要么是黑的。
2)根结点是黑的。
3)每个叶结点(叶结点即指树尾端NIL指针或NULL结点)是黑的。
4)如果一个结点是红的,那么它的俩个儿子都是黑的。
5)对于任一结点而言,其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点。

如果我们插入一个节点,并把他染红,则树的1235项原则都不会被破坏。如何保证原则4呢?调整的原则是把红色问题向上修正到根节点,最后把根节点染黑,来达到平衡。
我们先把插入的节点染红,然后进行修正操作:
插入修复情况1:当前结点的父结点是红色且叔叔结点是红色。
将当前结点的父结点和叔叔结点涂黑,祖父结点涂红。在以祖父节点为新的当前结点再做一遍。
A. 为了解决本节点和父节点都是红色,把父节点染黑。
B. 但是父节点的在子树多了个黑色,所以要把叔叔也染黑来平衡。
C. 此时爷爷节点的子树也多了个黑色,所以把他染红。
D. 爷爷节点被染红了上面的节点曾爷爷有可能是红的,在做一次。
插入修复情况2:当前结点的父结点是红色,叔叔结点是黑色,当前结点是其父结点的右子
对策:当前结点的父结点做为新的当前结点,以新当前结点为支点左旋。左旋后,本节点上移,把问题向上修正。可以转化到情况3
插入修复情况3:当前结点的父结点是红色,叔叔结点是黑色,当前结点是其父结点的左子
解法:父结点变为黑色,祖父结点变为红色,在祖父结点为支点右旋
A. 为了解决本节点和父节点都为红,把父节点染黑
B. 为了解决父节点在的子树多了一个黑色,把叔叔染红并右旋解决