树图如何使用红黑树算法 [英] How tree map uses red black tree algorithm

问题描述

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

I have read many articles on Red black tree where it take O(log n) time for operations .I am not very clear how it works and how actually tree map uses red black tree algorithm to balance the tree compared to binary search tree.

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

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

Can anyone please explain with a example how the algorithm works.

推荐答案

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

A red-black tree is a binary search tree. It's just a flavor of BST that has fancy versions of insert and delete operations that reorganize the tree as they run so that the tree never gets "long and stringy." The longer and stringier a tree gets, the more it behaves like a linked list. On average, linked list operations require half the list to be touched (or the whole list in the worst case), so run time varies linearly (O(n) in the number of elements n). When the tree is "bushy" or nearly balanced, then operations are much cheaper ( O (log n) ) each. The red-black algorithms guarantee that the tree remains bushy.

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

To make this concrete, here are two trees that store the keys A to G. The left is long and stringy. Note how it looks like a list. In the worst case, it takes 4 key comparisons to find an element. The tree on the right is bushy. It needs only 3. Here the difference is small. For a tree of 1023 elements, the stringy tree needs 512 comparisons and the bushy one only 10. This is the power of log n.

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

不能保证红黑树是完全浓密的(用正确的术语来说是完美平衡")，但红黑规则以数学上严格的方式保证它足够浓密，以便操作时间随日志而变化n 的而不是 n 中的线性.

The red-black tree isn't guaranteed to be perfectly bushy (in correct terminology "perfectly balanced"), but the red-black rules guarantee that it's bushy enough in a mathematically strict way so that operation times vary as the log of n rather than linearly in n.

红黑规则的天才之处在于它们是本地的".在违反规则的插入或删除过程中，可以通过仅为操作触及的每个节点调整恒定数量的节点来恢复它们.因此，它们价格低廉且易于实施.

The red-black rules' genius is that they are "local." During an insertion or deletion that breaks the rules, it's possible to restore them by adjusting only a constant number of nodes for each node touched by the operation. Therefore they are cheap and fairly easy to implement.

然而，当整棵树的红黑规则都成立时，有可能通过一个聪明的数学证明来证明它已经足够浓密了，如上所述.

Yet when the red-black rules are true for the whole tree, it's possible to show by a clever mathematical proof that it's bushy enough as described above.

树图呢?映射是一个函数，其域称为键集 K，范围称为值集 V.为了实现树映射，每个节点存储一个键值对 <k,v> 其中 k \in K 和 v \in V.在上图中(和大多数演示文稿)中，只显示了键(字母 A-G).在映射中，插入、查找和删除以非常明显的方式处理这些对.例如，查找使用通常的 BST 算法搜索一个键.当找到键时，也会找到值，因为它在同一对中.这就是返回的内容.在java中，这对被称为Map.Entry.您可以在 Java 源代码.

What about the tree map? A map is a function with a domain called the key set K and range called the value set V. To implement a tree map, each node stores a key-value pair <k,v> where k \in K and v \in V. In the drawings above (and most presentations), only keys (letters A-G) are shown. In the map, insertion, lookup, and deletion work on these pairs in a pretty obvious way. For example, lookup searches for a key using the usual BST algorithm. When the key is found, the value is also found because it's in the same pair. That's what's returned. In java, the pair is called Map.Entry. You can check this out in the Java source code.

我不会详细介绍红黑规则的工作原理，因为我无法改进 维基百科页面.我的猜测和希望是你错过了大局"，所以现在讨论是有意义的.好消息是几乎所有语言都提供了经过彻底测试和性能优化的树实现，因此不需要了解旋转的神秘细节.当然，如果您很好奇并且只是想知道，那就来吧！恭喜！

I won't go into the details on how the red-black rules work because I couldn't improve on the Wikipedia page. My guess and hope is that you were missing the "big picture" so now that discussion will make sense. The good news is that nearly all languages provide a thoroughly tested and performance-optimized tree implementation, so knowing the arcane details of rotations is not necessary. Of course, if you're curious and just want to know, have at it! Congratulations!

就其价值而言，Top Coder 对算法的解释并不总是最清楚的.四处寻找其他人，直到为您点击".CS中受人尊敬的教科书受到尊重是有原因的:它们的解释非常好.Corman 和 Rivest 是公认的最爱.

For what it's worth, Top Coder explanations of algorithms are not always the clearest. Hunt around for others until one "clicks" for you. The respected textbooks in CS are respected for a reason: their explanations are excellent. Corman and Rivest is an accepted favorite.

这篇关于树图如何使用红黑树算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！