树图如何使用红黑树算法

Question

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

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

任何人都可以用一个例子解释算法是如何工作的.

Answer 1

红黑树是二叉搜索树.它只是BST的一种风格,它具有花哨的版本insert和delete操作,可以在树运行时对树进行重新组织,以使树永远不会变得"长而粗糙".树变得越长越有条理,它就像链表一样.平均而言,链表操作需要触摸列表的一半(或最坏情况下的整个列表),因此运行时间线性变化(元素数量为O(n)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的对数而变化而不是线性的.

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

然而,当红黑规则适用于整棵树时,可以通过一个聪明的数学证明表明它如上所述足够浓密.

树图怎么样？映射是具有称为密钥集K的域的函数,并且范围称为值集V.为了实现树映射,每个节点存储键和值对<k,v>,其中k \in K和v \in V.在上面的图(以及大多数演示文稿)中,仅显示了键(字母AG).在地图中,以非常明显的方式对这些对进行插入,查找和删除.例如,查找使用通常的BST算法搜索密钥.找到密钥后,也会找到该值,因为它位于同一对中.那就是归来的.在java中,调用该对Map.Entry.您可以在Java源代码中查看它.

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

对于它的价值,Top Coder对算法的解释并不总是最清楚的.寻找其他人,直到你"点击"为止.CS中备受推崇的教科书受到尊重是有原因的:他们的解释非常好.Corman和Rivest是最受欢迎的.