2. 红黑树

R-B Tree，全称是 Red-Black Tree，又称为“红黑树”，它是一种特殊的二叉查找树。 红黑树的每个节点上都有存储位表示节点的颜色，可以是红（Red）或黑（Black）。

2.1. 特性

  • 满足二叉查找树的性质。

  • 每个节点或者是黑色，或者是红色。

  • 根节点是黑色。

  • 每个叶子节点（NIL）是黑色。 [注意：这里的叶子节点是指为空（NIL 或 NULL）的叶子节点！]

  • 如果一个节点是红色的，则它的子节点必须是黑色的。

  • 从一个节点到该节点的子孙叶子节点的所有路径上包含相同数目的黑节点（black-height）。

../_images/02_rbTree.png

红黑树的应用比较广泛，主要是用它来存储有序的数据，查找、插入、删除操作的平均和最坏情况下的时间复杂度是 \(\mathcal{O}(\log n)\) ，效率非常之高。C++ STL中的set、map，以及Linux虚拟内存的管理，都是通过红黑树去实现的。

一颗具有 \(n\) 个键值的红黑树，其高度 \(h\) 满足：

\[h \leqslant 2 \log (n+1).\]

2.2. BST 与 AVL 树

BST（二叉查找树）的特点是左子树的所有节点值比父亲节点小，而右子树的所有节点值比父亲节点大。查找的平均时间复杂度是 \(\mathcal{O}(\log n)\) ，但是如果二叉查找树很不平衡，甚至退化为“链表”（除了叶子节点，每个节点只有一个子节点），则时间复杂度是 \(\mathcal{O}(n)\) 。

AVL 树是最早被发明的自平衡二叉查找树。在 AVL 树中，任一节点对应的两棵子树的最大高度差为 1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是 \(\mathcal{O}(\log n)\) 。 然而，这种高度平衡性是很严格的条件，如果需要频繁插入、删除节点，那么需要较大的代价来维护树的平衡性。

对红黑树而言，一方面，在最坏情况下，查找的时间复杂度也是 \(\mathcal{O}(\log n)\) ，查找性能有保证；另一方面，即使需要频繁插入、删除节点，红黑树的维护代价也比 AVL 树更低。

2.3. 参考资料

  1. 红黑树(一)之 原理和算法详细介绍

  1. 30张图彻底理解红黑树

  1. Red–black tree