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

Wed, 20 Mar 2019 23:00:25 +0800

平衡树

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

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

数据结构 on 子恒的博客

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

平衡树

2-3-4树

红黑树