红黑树

路径如下

树->二叉树(BT)->二叉查找树(BST)->平衡二叉查找树(AVL)->红黑树(RBT)

红黑树特点

1. 每个节点要么是黑色，要么是红色

2. 根节点必须是黑色

3. 红节点不能连续出现（即，红色节点的父子节点必须是黑色），但黑节点无要求

4. 对于每个节点，从该节点到null（叶子节点的下一个伪节点为nul）的任何路径，都含有相同个数的黑节点

5. 由以上4个特点我们可知红黑树最短支路的情况就是路径上只有黑节点，最长支路的情况就是路径上红黑节点相互间隔，所以红黑树中最长支路不大于最短支路的2倍。

红黑树和平衡二叉查找树(AVL)比较

自从红黑树出来后，几乎在很大程度上取代了AVL，那么他们之间到底有那些有缺点，分别适用于什么情形呢：

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的。

• 这里总结一下：

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

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

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

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

  红黑树最典型的用途就是实现关联数组