Red-Black Tree, 红黑树, R-B Tree

https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/03.01.md

二叉查找树

由于红黑树本质上就是一棵二叉查找树，所以在了解红黑树之前，咱们先来看下二叉查找树。

二叉查找树 (Binary Search Tree) ，也称有序二叉树 (ordered binary tree) ,排序二叉树 (sorted binary tree) ，是指一棵空树或者具有下列性质的二叉树:

若任意结点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

若任意结点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

任意结点的左、右子树也分别为二叉查找树。

没有键值相等的结点 (no duplicate nodes) 。

因为，一棵由n个结点，随机构造的二叉查找树的高度为lgn，所以顺理成章，一般操作的执行时间为O (lgn) . (至于n个结点的二叉树高度为lgn的证明，可参考算法导论 第12章 二叉查找树 第12.4节) 。

但二叉树若退化成了一棵具有n个结点的线性链后，则此些操作最坏情况运行时间为O (n) 。后面我们会看到一种基于二叉查找树-红黑树，它通过一些性质使得树相对平衡，使得最终查找、插入、删除的时间复杂度最坏情况下依然为O (lgn) 。

红黑树

前面我们已经说过，红黑树，本质上来说就是一棵二叉查找树，但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。

但它是如何保证一棵n个结点的红黑树的高度始终保持在h = logn的呢？这就引出了红黑树的5条性质:

  1. 每个结点要么是红的，要么是黑的。

  2. 根结点是黑的。

  3. 每个叶结点 (叶结点即指树尾端NIL指针或NULL结点) 是黑的。

  4. 如果一个结点是红的，那么它的俩个儿子都是黑的。

  5. 对于任一结点而言，其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点。

正是红黑树的这5条性质，使得一棵n个结点是红黑树始终保持了logn的高度，从而也就解释了上面我们所说的"红黑树的查找、插入、删除的时间复杂度最坏为O(log n)“这一结论的原因。

红黑树是不符合AVL树的平衡条件的，即每个节点的左子树和右子树的高度最多差1的二叉查找树。但是提出了为节点增加颜色，红黑是用非严格的平衡来换取增删节点时候旋转次数的降低，任何不平衡都会在三次旋转之内解决，而AVL是严格平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多。所以红黑树的插入效率更高！！！

这里引用一下知乎上的回答:

Answer 1:

  1. 如果插入一个node引起了树的不平衡，AVL和RB-Tree都是最多只需要2次旋转操作，即两者都是O(1)；但是在删除node引起树的不平衡时，最坏情况下，AVL需要维护从被删node到root这条路径上所有node的平衡性，因此需要旋转的量级O(logN)，而RB-Tree最多只需3次旋转，只需要O(1)的复杂度。

  2. 其次，AVL的结构相较RB-Tree来说更为平衡，在插入和删除node更容易引起Tree的unbalance，因此在大量数据需要插入或者删除时，AVL需要rebalance的频率会更高。因此，RB-Tree在需要大量插入和删除node的场景下，效率更高。自然，由于AVL高度平衡，因此AVL的search效率更高。

  3. map的实现只是折衷了两者在search、insert以及delete下的效率。总体来说，RB-tree的统计性能是高于AVL的。 作者: Acjx 链接: http://www.zhihu.com/question/20545708/answer/58717264

Answer 2 这个总结比较好: 红黑树的 查询性能略微逊色于AVL树，因为他比avl树会稍微不平衡最多一层，也就是说红黑树的查询性能只比相同内容的avl树最多多一次比较，但是，红黑树在插入和删除上完爆avl树， avl树每次插入删除会进行大量的平衡度计算，而红黑树为了维持红黑性质所做的红黑变换和旋转的开销，相较于avl树为了维持平衡的 开销要小得多

作者: 陈智超 链接: http://www.zhihu.com/question/43744788/answer/98258881

Answer 3 : 功能、性能、空间开销的折中结果。

AVL更平衡，结构上更加直观，时间效能针对读取而言更高；维护稍慢，空间开销较大。

红黑树，读取略逊于AVL，维护强于AVL，空间开销与AVL类似，内容极多时略优于AVL，维护优于AVL。 基本上主要的几种平衡树看来，红黑树有着良好的稳定性和完整的功能，性能表现也很不错，综合实力强，在诸如STL的场景中需要稳定表现。 作者: Coldwings 链接: http://www.zhihu.com/question/20545708/answer/44370878

所以简单说，如果你的应用中，搜索的次数远远大于插入和删除，那么选择AVL，如果搜索，插入删除次数几乎差不多，应该选择RB。

下面的文章来源: http://blog.csdn.net/klarclm/article/details/7780319

1 好处 及 用途

    红黑树并不追求“完全平衡”——它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能。

红黑树能够以O(log2 n) 的时间复杂度进行搜索、插入、删除操作。此外，由于它的设计，任何不平衡都会在三次旋转之内解决。当然，还有一些更好的，但实现起来更复杂的数据结构 能够做到一步旋转之内达到平衡，但红黑树能够给我们一个比较“便宜”的解决方案。红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高。

    当然，红黑树并不适应所有应用树的领域。如果数据基本上是静态的，那么让他们待在他们能够插入，并且不影响平衡的地方会具有更好的性能。如果数据完全是静态的，例如，做一个哈希表，性能可能会更好一些。

在实际的系统中，例如，需要使用动态规则的防火墙系统，使用红黑树而不是散列表被实践证明具有更好的伸缩性。

典型的用途是实现关联数组

2 AVL树是最先发明的自平衡二叉查 找树。在AVL树中任何节点的两个儿子子树的高度最大差别为一，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O(log n)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者 G.M. Adelson-Velsky 和 E.M. Landis，他们在 1962 年的论文 “An algorithm for the organization of information” 中发表了它。

引入二叉树的目的是为了提高二叉树的搜索的效率,减少树的平均搜索长度.为此,就必须每向二叉树插入一个结点时调整树的结构,使得二叉树搜索保持平衡,从而可能降低树的高度,减少的平均树的搜索长度.

AVL树的定义: 一棵AVL树满足以下的条件: 1>它的左子树和右子树都是AVL树 2>左子树和右子树的高度差不能超过1 从条件1可能看出是个递归定义,如GNU一样.

性质: 1>一棵n个结点的AVL树的其高度保持在0(log2(n)),不会超过3/2log2(n+1) 2>一棵n个结点的AVL树的平均搜索长度保持在0(log2(n)). 3>一棵n个结点的AVL树删除一个结点做平衡化旋转所需要的时间为0(log2(n)).

从1这点来看红黑树是牺牲了严格的高度平衡的优越条件为 代价红黑树能够以O(log2 n)的时间复杂度进行搜索、插入、删除操作。此外，由于它的设计，任何不平衡都会在三次旋转之内解决。当然，还有一些更好的，但实现起来更复杂的数据结构 能够做到一步旋转之内达到平衡，但红黑树能够给我们一个比较“便宜”的解决方案。红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高.

版权声明: 本文为CSDN博主「mmshixing」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接: https://blog.csdn.net/mmshixing/article/details/51692892

可以完全放到内存中时，红黑树的时间复杂度比B树低。

如linux中进程的调度用的是红黑树。

反之，数据量较大，外存中占主要部分时，B树因其读磁盘次数少，而具有更快的速度。

https://www.jianshu.com/p/e3506cee4010