treemap - 树图如何使用红黑树算法

我已经阅读了许多关于Red black树的文章，这些文章花了O(log n)的时间进行操作。与二进制搜索树相比，我不太清楚它的工作方式以及树图实际上是如何使用red black树算法来平衡树的。

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

任何人都可以举例说明该算法如何工作。

最佳答案

红黑树是二叉搜索树。这只是BST的一种形式，具有精美版本的insert和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>，其中k \in K和v \in V。在以上附图(和大多数演示文稿)中，仅显示了按键(字母A-G)。在映射中，插入，查找和删除对这些对的工作非常明显。例如，查找使用常规BST算法搜索关键字。找到键后，还会找到该值，因为它在同一对中。那就是返回的内容。在Java中，该对称为Map.Entry。您可以在Java source code中检查出来。

我不会详细介绍红黑规则的工作原理，因为我无法改善the Wikipedia page。我的猜测和希望是，您错过了“大局”，因此现在进行讨论将是有意义的。好消息是，几乎所有语言都提供了经过全面测试和性能优化的树实现，因此不必了解旋转的奥秘细节。当然，如果您好奇并且只想知道，那就来吧!恭喜你!

值得一提的是，Top Coder对算法的解释并不总是最清楚的。到处寻找其他人，直到您“点击”。 CS中受人尊敬的教科书之所以受到尊重是有原因的:它们的解释非常出色。 Corman and Rivest是被接受的最爱。

关于treemap - 树图如何使用红黑树算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/31779786/