红黑树|系列1（简介）

导言：

红黑树是一种自平衡二叉搜索树，其中每个节点都有一个额外的位，该位通常被解释为颜色（红色或黑色）。这些颜色用于确保树在插入和删除期间保持平衡。虽然树的平衡并不完美，但它足以减少搜索时间并将其保持在O（logn）时间左右，其中n是树中元素的总数。这棵树是鲁道夫·拜尔在1972年发明的。

必须注意的是，由于每个节点只需要1位空间来存储颜色信息，这些类型的树显示出与经典（未着色）二叉搜索树相同的内存占用。

每棵红黑树都要遵守的规则：

1. 每个节点都有一种红色或黑色。
2. 树根总是黑色的。
3. 没有两个相邻的红色节点（红色节点不能有红色父节点或红色子节点）。
4. 从一个节点（包括根节点）到其任何子节点的每个路径都有相同数量的黑色节点。
5. 所有叶节点都是黑色节点。

为什么是红黑树？

大多数BST操作（例如，搜索、最大、最小、插入、删除等）需要O（h）时间，其中h是BST的高度。对于倾斜的二叉树，这些操作的成本可能会变成O（n）。如果我们确保在每次插入和删除后树的高度仍然是O（logn），那么我们就可以保证所有这些操作都有O（logn）的上限。红黑树的高度始终为O（logn），其中n是树中的节点数。

“n”是红黑树中元素的总数。

与 平衡二叉树 :

与红黑树相比，AVL树更平衡，但在插入和删除过程中，它们可能会导致更多的旋转。因此，如果你的应用程序涉及频繁的插入和删除，那么红黑树应该是首选。如果插入和删除的频率较低，搜索的频率更高，那么AVL树应该优先于红黑树。

红黑树如何确保平衡？

理解平衡的一个简单例子是，红黑树中不可能有3个节点的链。我们可以尝试任何颜色的组合，看到它们都违反了红黑树的属性。

A chain of 3 nodes is not possible in Red-Black Trees. Following are NOT Red-Black Trees        30             30               30              /             /               /       20  NIL         20   NIL         20   NIL    /              /               /       10  NIL          10  NIL          10  NIL  Violates          Violates        ViolatesProperty 4.      Property 4       Property 3 Following are different possible Red-Black Trees with above 3 keys         20                           20       /                           /        10     30                    10     30    /     /                   /      /   NIL  NIL NIL NIL             NIL  NIL NIL NIL

关于红黑树的有趣之处：

1. 红黑树的黑色高度是从根节点到叶节点的路径上的黑色节点数。叶节点也算作黑色节点。因此，高度为h的红黑树的黑色高度>=h/2。
2. 具有n个节点的红黑树的高度为h<=2 log _2. （n+1）。
3. 所有的叶子（无）都是黑色的。
4. 节点的黑色深度定义为从根到该节点的黑色节点数，即黑色祖先数。
5. 每棵红黑树都是二叉树的特例。

红黑树的黑色高度：

Black height是从根到叶的路径上的黑色节点数。叶节点也被计算为黑色节点。根据上述性质3和4，我们可以得出：， 高度为h的红黑树的黑色高度>=h/2 .

从一个节点到其最远子代叶的节点数不超过到最近子代叶的节点数的两倍。

每个有n个节点的红黑树都有高度<= 2Log _2. （n+1） 这可以用以下事实来证明：

1. 对于一般的二叉树，让 K 是所有根到空路径上的最小节点数，则n>=2 ^K –1（例如，如果k为3，则n至少为7）。这个表达式也可以写成k<=Log _2. （n+1）。
2. 根据红黑树的性质4和上述主张，我们可以说，在一个有n个节点的红黑树中，有一条根到叶的路径，最多有Log _2. （n+1）黑色节点。
3. 根据红黑树的性质3和性质5，我们可以断言红黑树中的黑节点数至少为⌊ n/2⌋ 其中n是节点总数。

从以上几点，我们可以得出结论，红黑树 N 节点的高度小于等于2Log _2. （n+1）

红黑树中的搜索操作：

由于每个红黑树都是二叉树的特例，因此红黑树的搜索算法与二叉树的搜索算法类似。

算法：

searchElement (tree, val)Step 1:If tree -> data = val OR tree = NULL    Return treeElseIf val < data        Return searchElement (tree -> left, val)    Else        Return searchElement (tree -> right, val)    [ End of if ][ End of if ]Step 2: END

对于该计划，您可以参考 平衡二叉树 .

示例：在下面的红黑树中搜索11。

解决方案：

1. 从根开始。
2. 将插入元素与root进行比较，如果小于root，则向左递归，否则向右递归。
3. 如果在任何地方找到要搜索的元素，则返回true，否则返回false。

跟着蓝色泡泡走。

在这篇文章中，我们介绍了红黑树，并讨论了如何确保平衡。最难的部分是在添加和删除键时保持平衡。我们还看到了如何从红黑树中搜索元素。我们很快将在红黑树上的后续帖子中讨论插入和删除操作。

练习：

1) 有可能在一棵红黑树中有所有黑色节点吗？ 2) 画一棵红黑相间的树 平衡二叉树 结构方面？

插入和删除

红黑树插入 红黑树删除

应用：

1. 大多数自平衡BST库函数如图和C++中的C++（或TeSeSET和TreMeP在爪哇）使用红黑树。
2. 它用于在Linux上实现CPU调度。 完全公平调度器 使用它。
3. 此外，它们还用于K-均值聚类算法中，以降低时间复杂度。
4. 此外，MySQL还使用红黑树作为表的索引。

参考资料：

• 算法导论第三版由Clifford Stein、Thomas H.Cormen、Charles E.Leiserson、Ronald L.Rivest编写
• http://en.wikipedia.org/wiki/Red%E2%80%93black_tree
• Tim Roughgarden关于红黑树的视频讲座
• 麻省理工学院红黑树视频讲座
• 麻省理工学院关于红黑树的课堂讲稿