红黑树 (Red-Black Tree) – 介绍

发布网友发布时间：2024-10-03 19:19

共1个回答

热心网友时间：2024-10-05 20:54

介绍：

红黑树是一种自平衡二叉搜索树，每个节点包含一个额外的位，通常被解释为颜色（红色或黑色）。这种颜色用于保证树在插入和删除操作中保持平衡。尽管树的平衡并不完美，但能将搜索时间减少并保持在 O(log n) 左右，其中 n 是树中元素的总数。红黑树由 Rudolf Bayer 在 1972 年发明。

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

每棵红黑树都遵循的规则：

为什么是红黑树？

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

与 AVL 树的比较：

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

红黑树如何确保平衡？

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

红黑树的属性：

红黑树的黑色高度：

黑色高度是从根到叶子的路径上黑色节点的数量。叶节点也算作黑色节点。从上面的属性 3 和 4，我们可以得出，高度为 h 的红黑树的 black-height >= h/2。

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

每个具有 n 个节点的红黑树的高度 <= 2Log2(n+1)

证明如下：

对于一般的二叉树，设k是所有根到 NULL 路径上的最小节点数，则 n >= 2k – 1（例如，如果 k 为 3，则 n 至少为 7）。这个表达式也可以写成 k <= Log2(n+1)。

从红黑树的属性 4 和上述声明，我们可以说在具有 n 个节点的红黑树中，有一条从根到叶的路径最多具有 Log2(n+1) 个黑色节点。

根据红黑树的属性 3 和 5，我们可以声称红黑树中黑色节点的数量至少为 ⌊n/2⌋，其中 n 是节点的总数。

从以上几点，我们可以得出这样一个事实：具有 n 个节点的红黑树的高度 <= 2Log2(n+1)

红黑树中的搜索操作：

由于每棵红黑树都是二叉树的特例，所以红黑树的搜索算法与二叉树的搜索算法类似。

算法：

实例: 在以下红黑树中搜索11

红黑树的应用：

相关文章：

（二）红黑树（Red-Black Tree）- 插入操作 - 嗅探网的文章 - 知乎

（三）红黑树（Red-Black Tree）- 删除操作 - 嗅探网的文章 - 知乎

完整示例代码下载链接：（包含各种语言：C语言、Python、Java，C++等均有示例）

见标题