树图如何使用红黑树算法

我读过很多关于红黑树的文章，其中操作需要 O(log n) 时间。我不太清楚它是如何工作的，以及与二叉搜索树相比，树图实际上如何使用红黑树算法来平衡树。

参考链接https://www.topcoder.com/community/data-science/data-science-tutorials/an-introduction-to-binary-search-and-red-black-trees/ https://www.topcoder.com/community/data-science/data-science-tutorials/an-introduction-to-binary-search-and-red-black-trees/

谁能用一个例子解释一下该算法是如何工作的。

一棵红黑树is二叉搜索树。这只是 BST 的一种风格，有一些奇特的版本insert and delete在运行时重新组织树的操作，以便树永远不会变得“又长又细”。树越长、越细，它的行为就越像链表。平均而言，链表操作需要访问一半的列表（或者在最坏的情况下是整个列表），因此运行时间呈线性变化（元素数量 n 为 O(n)）。当树“茂密”或接近平衡时，每次操作都会便宜得多（ O (log n) ）。红黑算法保证树保持茂密。

为了具体说明这一点，这里有两棵树，用于存储键 A 到 G。左边的树又长又细。请注意它看起来像一个列表。在最坏的情况下，需要 4 次关键比较才能找到一个元素。右边的树很茂密。只需要 3 个。这里差别很小。对于一棵包含 1023 个元素的树，弦状树需要 512 次比较，而浓密树只需 10 次比较。这是 log n 的幂。

  B                    _D_
 / \                  /   \
A   D                B     F
   / \              / \   / \
  C   F            A   C E   G
     / \
    E   G

红黑树不能保证完全茂密（正确的术语是“完美平衡”），但红黑规则保证它以数学上严格的方式足够茂密，因此操作时间随着 n 的对数而变化，而不是比在 n 中呈线性关系。

红黑规则的天才在于它们是“局部的”。在违反规则的插入或删除过程中，可以通过仅调整操作涉及的每个节点的恒定数量的节点来恢复规则。因此它们很便宜并且相当容易实施。

然而，当红黑规则适用于整棵树时，可以通过巧妙的数学证明来证明它如上所述足够茂密。

那么树形图呢？映射是一个函数，其域称为键集 K，范围称为值集 V。为了实现树形映射，每个节点都存储一个键值对<k,v> where k \in K and v \in V。在上图中（以及大多数演示文稿）中，仅显示了按键（字母 A-G）。在映射中，插入、查找和删除以非常明显的方式对这些对进行操作。例如，查找使用通常的 BST 算法来搜索键。当找到键时，也会找到值，因为它位于同一对中。这就是返回的内容。在java中，该对称为Map.Entry。您可以在Java源代码 http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/Map.java#Map.Entry.

我不会详细介绍红黑规则如何运作，因为我无法改进维基百科页面 https://en.wikipedia.org/wiki/Red%E2%80%93black_tree。我的猜测和希望是，您错过了“大局”，所以现在讨论将有意义。好消息是，几乎所有语言都提供了经过彻底测试和性能优化的树实现，因此无需了解旋转的神秘细节。当然，如果你好奇并且只是想知道，那就去吧！恭喜！

无论如何，Top Coder 对算法的解释并不总是最清晰的。到处寻找其他人，直到有人“点击”你。受人尊敬的计算机科学教科书之所以受人尊敬是有原因的：它们的解释非常出色。科曼和里维斯特 https://en.wikipedia.org/wiki/Introduction_to_Algorithms是公认的最爱。