红黑树 刺骨的言语ヽ痛彻心扉 2022-04-23 12:06 244阅读 0赞 红黑树(Red Black Tree) 是一种自平衡二叉查找树,是在[计算机][Link 1]科学中用到的一种[数据结构][Link 2],典型的用途是实现[关联数组][Link 3]。 它是在1972年由Rudolf Bayer发明的,当时被称为平衡二叉B树(symmetric binary B-trees)。后来,在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。 红黑树和AVL树类似,都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。 它虽然是复杂的,但它的最坏情况运行时间也是非常良好的,并且在实践中是高效的: 它可以在O(log n)时间内做查找,插入和删除,这里的n 是树中元素的数目。 [![红黑树][e4dde71190ef76c641326b589d16fdfaae5167e5.jpg]][e4dde71190ef76c641326b589d16fdfaae5167e5.jpg 1]红黑树 它的统计性能要好于[平衡二叉树][Link 4](有些书籍根据作者姓名,Adelson-Velskii和Landis,将其称为AVL-树),因此,红黑树在很多地方都有应用。在C++ STL中,很多部分(包括set, multiset, map, multimap)应用了红黑树的变体(SGI STL中的红黑树有一些变化,这些修改提供了更好的性能,以及对set操作的支持)。其他[平衡树][Link 5]还有:[AVL][],[SBT][],[伸展树][Link 6],[TREAP][] 等等 [![树的左旋][86d6277f9e2f0708cdb73039ed24b899a901f25d.jpg]][86d6277f9e2f0708cdb73039ed24b899a901f25d.jpg 1] [树的左旋(2张)][86d6277f9e2f0708cdb73039ed24b899a901f25d.jpg 1] 当我们在对红黑树进行插入和删除等操作时,对树做了修改,那么可能会违背红黑树的性 质。 为了保持红黑树的性质,我们可以通过对树进行旋转,即修改树中某些结点的颜色及指针结构,以达到对红黑树进行插入、删除结点等操作时,红黑树依然能保持它特有的性质(五点性质)。 ## 性质 ## 红黑树是每个节点都带有颜色属性的二叉查找树,颜色或红色或黑色。在二叉查找树强制一般要求以外,对于任何有效的红黑树我们增加了如下的额外要求: 性质1. 节点是红色或黑色。 性质2. 根节点是黑色。 性质3 每个叶节点(NIL节点,空节点)是黑色的。 性质4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点) 性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。 这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例,这个在高度上的理论上限允许红黑树在最坏情况下都是高效的,而不同于普通的二叉查找树。 要知道为什么这些特性确保了这个结果,注意到性质4导致了路径不能有两个毗连的红色节点就足够了。最短的可能路径都是黑色节点,最长的可能路径有交替的红色和黑色节点。因为根据性质5所有最长的路径都有相同数目的黑色节点,这就表明了没有路径能多于任何其他路径的两倍长。 在很多树[数据结构][Link 7]的表示中,一个节点有可能只有一个子节点,而[叶子节点][Link 8]不包含数据。用这种范例表示红黑树是可能的,但是这会改变一些属性并使算法复杂。为此,本文中我们使用 "nil 叶子" 或"空(null)叶子",如上图所示,它不包含数据而只充当树在此结束的指示。这些节点在绘图中经常被省略,导致了这些树好象同上述原则相矛盾,而实际上不是这样。与此有关的结论是所有节点都有两个子节点,尽管其中的一个或两个可能是空叶子。 ## 术语 ## 红黑树是一种特定类型的[二叉树][Link 9],它是在计算机科学中用来组织数据比如数字的块的一种结构。所有[数据块][Link 10]都存储在[节点][Link 11]中。这些节点中的某一个节点总是担当起始位置的功能,它不是任何节点的儿子,我们称之为根节点或根。它有最多两个"儿子",都是它连接到的其他节点。所有这些儿子都可以有自己的儿子,以此类推。这样根节点就有了把它连接到在树中任何其他节点的路径。 如果一个节点没有儿子,我们称之为[叶子节点][Link 8],因为在直觉上它是在树的边缘上。子树是从特定[节点][Link 11]可以延伸到的树的某一部分,其自身被当作一个树。在红黑树中,叶子被假定为 null 或空。 由于红黑树也是二叉查找树,它们当中每一个节点的比较值都必须大于或等于在它的左子树中的所有节点,并且小于或等于在它的右子树中的所有节点。这确保红黑树运作时能够快速的在树中查找给定的值。 ## 用途 ## 红黑树和AVL树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。这不只是使它们在时间敏感的应用如即时应用(real time application)中有价值,而且使它们有在提供最坏情况担保的其他[数据结构][Link 7]中作为建造板块的价值;例如,在计算几何中使用的很多数据结构都可以基于红黑树。 红黑树在[函数][Link 12]式[编程][Link 13]中也特别有用,在这里它们是最常用的持久[数据结构][Link 7]之一,它们用来构造[关联数组][Link 14]和集合,在突变之后它们能保持为以前的版本。除了O(log n)的时间之外,红黑树的持久版本对每次插入或删除需要O(log n)的空间。 红黑树是 [2-3-4树][2-3-4]的一种等同。换句话说,对于每个 2-3-4 树,都存在至少一个[数据元素][Link 15]是同样次序的红黑树。在 2-3-4 树上的插入和删除操作也等同于在红黑树中颜色翻转和旋转。这使得 2-3-4 树成为理解红黑树背后的逻辑的重要工具,这也是很多介绍算法的教科书在红黑树之前介绍 2-3-4 树的原因,尽管 2-3-4 树在实践中不经常使用。 ## 操作 ## 在红黑树上只读操作不需要对用于二叉查找树的操作做出修改,因为它也是二叉查找树。但是,在插入和删除之后,红黑属性可能变得违规。恢复红黑属性需要少量(O(log n))的颜色变更(这在实践中是非常快速的)并且不超过三次[树旋转][Link 16](对于插入是两次)。这允许插入和删除保持为 O(log n) 次,但是它导致了非常复杂的操作。 \[1\] 词条图册[更多图册][Link 17] [![词条图片][9358d109b3de9c828cdb8e7c6481800a18d84382.jpg]][9358d109b3de9c828cdb8e7c6481800a18d84382.jpg 1] [词条图片(3)][9358d109b3de9c828cdb8e7c6481800a18d84382.jpg 1] [![树的左旋][86d6277f9e2f0708cdb73039ed24b899a901f25d.jpg 2]][86d6277f9e2f0708cdb73039ed24b899a901f25d.jpg 2 1] [树的左旋(2)][86d6277f9e2f0708cdb73039ed24b899a901f25d.jpg 2 1] ### Data\_structures ### <table> <tbody> <tr> <td>▪ <a href="http://baike.baidu.com/view/15216.htm" rel="nofollow">集合</a></td> <td>▪ <a href="http://baike.baidu.com/view/864334.htm" rel="nofollow">容器</a></td> <td> </td> <td> </td> </tr> <tr> <td> </td> </tr> </tbody> </table> <table> <tbody> <tr> <td>▪ <a href="http://baike.baidu.com/view/209670.htm" rel="nofollow">数组</a></td> <td>▪ <a href="http://baike.baidu.com/view/1654988.htm" rel="nofollow">关联数组</a></td> <td>▪ <a href="http://baike.baidu.com/searchword/?word=Multimap&pic=1&sug=1&enc=utf8" rel="nofollow">Multimap</a></td> <td>▪ <a href="http://baike.baidu.com/view/281152.htm" rel="nofollow">集</a></td> </tr> <tr> <td>▪ <a href="http://baike.baidu.com/view/6402784.htm" rel="nofollow">多重集</a></td> <td>▪ <a href="http://baike.baidu.com/view/1320746.htm" rel="nofollow">散列表</a></td> <td>▪ <a href="http://baike.baidu.com/view/1420784.htm" rel="nofollow">树状数组</a></td> <td> </td> </tr> <tr> <td> </td> </tr> </tbody> </table> <table> <tbody> <tr> <td>▪ <a href="http://baike.baidu.com/view/894433.htm" rel="nofollow">列表</a></td> <td>▪ <a href="http://baike.baidu.com/view/549479.htm" rel="nofollow">链表</a></td> <td>▪ <a href="http://baike.baidu.com/view/38959.htm" rel="nofollow">队列</a></td> <td>▪ <a href="http://baike.baidu.com/view/93201.htm" rel="nofollow">堆栈</a></td> </tr> <tr> <td>▪ <a href="http://baike.baidu.com/view/203647.htm" rel="nofollow">循环队列</a></td> <td>▪ <a href="http://baike.baidu.com/view/5107600.htm" rel="nofollow">跳跃列表</a></td> <td> </td> <td> </td> </tr> <tr> <td> </td> </tr> </tbody> </table> <table> <tbody> <tr> <td>▪ <a href="http://baike.baidu.com/view/143352.htm" rel="nofollow">树</a></td> <td>▪ <a href="http://baike.baidu.com/view/389459.htm" rel="nofollow">二叉查找树</a></td> <td>▪ <a href="http://baike.baidu.com/view/249120.htm" rel="nofollow">堆</a></td> <td>▪ <a href="http://baike.baidu.com/view/670683.htm" rel="nofollow">线段树</a></td> </tr> <tr> <td>▪ <strong>红黑树</strong></td> <td>▪ <a href="http://baike.baidu.com/view/671745.htm" rel="nofollow">AVL树</a></td> <td> </td> <td> </td> </tr> <tr> <td> </td> </tr> </tbody> </table> <table> <tbody> <tr> <td>▪ <a href="http://baike.baidu.com/view/143347.htm" rel="nofollow">图</a></td> <td>▪ <a href="http://baike.baidu.com/searchword/?word=%E6%9C%89%E5%90%91%E6%97%A0%E7%8E%AF%E5%9B%BE&pic=1&sug=1&enc=utf8" rel="nofollow">有向无环图</a></td> <td>▪ <a href="http://baike.baidu.com/searchword/?word=%E4%BA%8C%E5%85%83%E5%86%B3%E7%AD%96%E5%9B%BE&pic=1&sug=1&enc=utf8" rel="nofollow">二元决策图</a></td> <td>▪ <a href="http://baike.baidu.com/view/93110.htm" rel="nofollow">无向图</a></td> </tr> <tr> <td> </td> </tr> </tbody> </table> ### 计算机科学中的树 ### <table> <tbody> <tr> <th>二叉树</th> <td> <table> <tbody> <tr> <td> <table> <tbody> <tr> <td>▪ <a href="http://baike.baidu.com/view/88806.htm" rel="nofollow">二叉树</a></td> <td>▪ <a href="http://baike.baidu.com/view/389459.htm" rel="nofollow">二叉查找树</a></td> <td>▪ <a href="http://baike.baidu.com/view/6667519.htm" rel="nofollow">笛卡尔树</a></td> <td>▪ <a href="http://baike.baidu.com/searchword/?word=Top%20tree&pic=1&sug=1&enc=utf8" rel="nofollow">Top tree</a></td> </tr> <tr> <td>▪ <a href="http://baike.baidu.com/searchword/?word=T%E6%A0%91&pic=1&sug=1&enc=utf8" rel="nofollow">T树</a></td> <td> </td> <td> </td> <td> </td> </tr> <tr> <td> </td> </tr> </tbody> </table></td> </tr> </tbody> </table></td> </tr> </tbody> </table> <table> <tbody> <tr> <th>自平衡二叉查找树</th> <td> <table> <tbody> <tr> <td> <table> <tbody> <tr> <td>▪ <a href="http://baike.baidu.com/searchword/?word=AA%E6%A0%91&pic=1&sug=1&enc=utf8" rel="nofollow">AA树</a></td> <td>▪ <a href="http://baike.baidu.com/view/671745.htm" rel="nofollow">AVL树</a></td> <td>▪ <strong>红黑树</strong></td> <td>▪ <a href="http://baike.baidu.com/view/1118088.htm" rel="nofollow">伸展树</a></td> </tr> <tr> <td>▪ <a href="http://baike.baidu.com/searchword/?word=%E6%A0%91%E5%A0%86&pic=1&sug=1&enc=utf8" rel="nofollow">树堆</a></td> <td>▪ <a href="http://baike.baidu.com/searchword/?word=%E8%8A%82%E7%82%B9%E5%A4%A7%E5%B0%8F%E5%B9%B3%E8%A1%A1%E6%A0%91&pic=1&sug=1&enc=utf8" rel="nofollow">节点大小平衡树</a></td> <td> </td> <td> </td> </tr> <tr> <td> </td> </tr> </tbody> </table></td> </tr> </tbody> </table></td> </tr> </tbody> </table> <table> <tbody> <tr> <th>B树</th> <td> <table> <tbody> <tr> <td> <table> <tbody> <tr> <td>▪ <a href="http://baike.baidu.com/view/298408.htm" rel="nofollow">B树</a></td> <td>▪ <a href="http://baike.baidu.com/view/1168762.htm" rel="nofollow">B+树</a></td> <td>▪ <a href="http://baike.baidu.com/view/1605516.htm" rel="nofollow">B*树</a></td> <td>▪ <a href="http://baike.baidu.com/searchword/?word=Bx%E6%A0%91&pic=1&sug=1&enc=utf8" rel="nofollow">Bx树</a></td> </tr> <tr> <td>▪ <a href="http://baike.baidu.com/searchword/?word=UB%E6%A0%91&pic=1&sug=1&enc=utf8" rel="nofollow">UB树</a></td> <td>▪ <a href="http://baike.baidu.com/view/1668085.htm" rel="nofollow">2-3树</a></td> <td>▪ <a href="http://baike.baidu.com/view/1995382.htm" rel="nofollow">2-3-4树</a></td> <td>▪ <a href="http://baike.baidu.com/searchword/?word=%28a%2Cb%29-%E6%A0%91&pic=1&sug=1&enc=utf8" rel="nofollow">(a,b)-树</a></td> </tr> <tr> <td>▪ <a href="http://baike.baidu.com/searchword/?word=Dancing%20tree&pic=1&sug=1&enc=utf8" rel="nofollow">Dancing tree</a></td> <td>▪ <a href="http://baike.baidu.com/searchword/?word=H%E6%A0%91&pic=1&sug=1&enc=utf8" rel="nofollow">H树</a></td> <td> </td> <td> </td> </tr> <tr> <td> </td> </tr> </tbody> </table></td> </tr> </tbody> </table></td> </tr> </tbody> </table> <table> <tbody> <tr> <th>Trie</th> <td> <table> <tbody> <tr> <td> <table> <tbody> <tr> <td>▪ <a href="http://baike.baidu.com/searchword/?word=%E5%89%8D%E7%BC%80%E6%A0%91&pic=1&sug=1&enc=utf8" rel="nofollow">前缀树</a></td> <td>▪ <a href="http://baike.baidu.com/view/117678.htm" rel="nofollow">后缀树</a></td> <td>▪ <a href="http://baike.baidu.com/searchword/?word=%E5%9F%BA%E6%95%B0%E6%A0%91&pic=1&sug=1&enc=utf8" rel="nofollow">基数树</a></td> <td> </td> </tr> <tr> <td> </td> </tr> </tbody> </table></td> </tr> </tbody> </table></td> </tr> </tbody> </table> <table> <tbody> <tr> <th>空间划分树</th> <td> <table> <tbody> <tr> <td> <table> <tbody> <tr> <td>▪ <a href="http://baike.baidu.com/view/2063378.htm" rel="nofollow">四叉树</a></td> <td>▪ <a href="http://baike.baidu.com/view/1035343.htm" rel="nofollow">八叉树</a></td> <td>▪ <a href="http://baike.baidu.com/view/8668561.htm" rel="nofollow">k-d树</a></td> <td>▪ <a href="http://baike.baidu.com/searchword/?word=vp-%E6%A0%91&pic=1&sug=1&enc=utf8" rel="nofollow">vp-树</a></td> </tr> <tr> <td>▪ <a href="http://baike.baidu.com/view/906563.htm" rel="nofollow">R树</a></td> <td>▪ <a href="http://baike.baidu.com/searchword/?word=R%2A%E6%A0%91&pic=1&sug=1&enc=utf8" rel="nofollow">R*树</a></td> <td>▪ <a href="http://baike.baidu.com/searchword/?word=R%2B%E6%A0%91&pic=1&sug=1&enc=utf8" rel="nofollow">R+树</a></td> <td>▪ <a href="http://baike.baidu.com/searchword/?word=X%E6%A0%91&pic=1&sug=1&enc=utf8" rel="nofollow">X树</a></td> </tr> <tr> <td>▪ <a href="http://baike.baidu.com/searchword/?word=M%E6%A0%91&pic=1&sug=1&enc=utf8" rel="nofollow">M树</a></td> <td>▪ <a href="http://baike.baidu.com/view/670683.htm" rel="nofollow">线段树</a></td> <td>▪ <a href="http://baike.baidu.com/searchword/?word=%E5%B8%8C%E5%B0%94%E4%BC%AF%E7%89%B9R%E6%A0%91&pic=1&sug=1&enc=utf8" rel="nofollow">希尔伯特R树</a></td> <td>▪ <a href="http://baike.baidu.com/searchword/?word=%E4%BC%98%E5%85%88R%E6%A0%91&pic=1&sug=1&enc=utf8" rel="nofollow">优先R树</a></td> </tr> <tr> <td> </td> </tr> </tbody> </table></td> </tr> </tbody> </table></td> </tr> </tbody> </table> <table> <tbody> <tr> <th>非二叉树</th> <td> <table> <tbody> <tr> <td> <table> <tbody> <tr> <td>▪ <a href="http://baike.baidu.com/searchword/?word=Exponential%20tree&pic=1&sug=1&enc=utf8" rel="nofollow">Exponential tree</a></td> <td>▪ <a href="http://baike.baidu.com/searchword/?word=Fusion%20tree&pic=1&sug=1&enc=utf8" rel="nofollow">Fusion tree</a></td> <td>▪ <a href="http://baike.baidu.com/searchword/?word=%E5%8C%BA%E9%97%B4%E6%A0%91&pic=1&sug=1&enc=utf8" rel="nofollow">区间树</a></td> <td>▪ <a href="http://baike.baidu.com/searchword/?word=PQ%20tree&pic=1&sug=1&enc=utf8" rel="nofollow">PQ tree</a></td> </tr> <tr> <td>▪ <a href="http://baike.baidu.com/searchword/?word=Range%20tree&pic=1&sug=1&enc=utf8" rel="nofollow">Range tree</a></td> <td>▪ <a href="http://baike.baidu.com/searchword/?word=SPQR%20tree&pic=1&sug=1&enc=utf8" rel="nofollow">SPQR tree</a></td> <td>▪ <a href="http://baike.baidu.com/searchword/?word=Van%20Emde%20Boas%20tree&pic=1&sug=1&enc=utf8" rel="nofollow">Van Emde Boas tree</a></td> <td> </td> </tr> <tr> <td> </td> </tr> </tbody> </table></td> </tr> </tbody> </table></td> </tr> </tbody> </table> <table> <tbody> <tr> <th>其他类型</th> <td> <table> <tbody> <tr> <td> <table> <tbody> <tr> <td>▪ <a href="http://baike.baidu.com/view/249120.htm" rel="nofollow">堆</a></td> <td>▪ <a href="http://baike.baidu.com/searchword/?word=%E6%95%A3%E5%88%97%E6%A0%91&pic=1&sug=1&enc=utf8" rel="nofollow">散列树</a></td> <td>▪ <a href="http://baike.baidu.com/searchword/?word=Finger%20tree&pic=1&sug=1&enc=utf8" rel="nofollow">Finger tree</a></td> <td>▪ <a href="http://baike.baidu.com/searchword/?word=Metric%20tree&pic=1&sug=1&enc=utf8" rel="nofollow">Metric tree</a></td> </tr> <tr> <td>▪ <a href="http://baike.baidu.com/searchword/?word=Cover%20tree&pic=1&sug=1&enc=utf8" rel="nofollow">Cover tree</a></td> <td>▪ <a href="http://baike.baidu.com/searchword/?word=BK-tree&pic=1&sug=1&enc=utf8" rel="nofollow">BK-tree</a></td> <td>▪ <a href="http://baike.baidu.com/searchword/?word=Doubly-chained%20tree&pic=1&sug=1&enc=utf8" rel="nofollow">Doubly-chained tree</a></td> <td>▪ <a href="http://baike.baidu.com/searchword/?word=iDistance&pic=1&sug=1&enc=utf8" rel="nofollow">iDistance</a></td> </tr> <tr> <td>▪ <a href="http://baike.baidu.com/searchword/?word=Link-cut%20tree&pic=1&sug=1&enc=utf8" rel="nofollow">Link-cut tree</a></td> <td>▪ <a href="http://baike.baidu.com/view/1420784.htm" rel="nofollow">树状数组</a></td> <td> </td> </tr> </tbody> </table></td> </tr> </tbody> </table></td> </tr> </tbody> </table> [Link 1]: https://baike.baidu.com/item/%E8%AE%A1%E7%AE%97%E6%9C%BA [Link 2]: https://baike.baidu.com/item/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/1450 [Link 3]: https://baike.baidu.com/item/%E5%85%B3%E8%81%94%E6%95%B0%E7%BB%84/3317025 [e4dde71190ef76c641326b589d16fdfaae5167e5.jpg]: https://gss2.bdstatic.com/-fo3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D250/sign=d00e707ab6003af349badb65052bc619/e4dde71190ef76c641326b589d16fdfaae5167e5.jpg [e4dde71190ef76c641326b589d16fdfaae5167e5.jpg 1]: /images/20220319/69289da920ec4b5bb5bf8df7469399dc.png [Link 4]: https://baike.baidu.com/item/%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91 [Link 5]: https://baike.baidu.com/item/%E5%B9%B3%E8%A1%A1%E6%A0%91 [AVL]: https://baike.baidu.com/item/AVL [SBT]: https://baike.baidu.com/item/SBT [Link 6]: https://baike.baidu.com/item/%E4%BC%B8%E5%B1%95%E6%A0%91 [TREAP]: https://baike.baidu.com/item/TREAP [86d6277f9e2f0708cdb73039ed24b899a901f25d.jpg]: https://gss1.bdstatic.com/-vo3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D220/sign=ea3c202d46a7d933bba8e3719d4ad194/86d6277f9e2f0708cdb73039ed24b899a901f25d.jpg [86d6277f9e2f0708cdb73039ed24b899a901f25d.jpg 1]: /images/20220319/18773e0b7a2546bf86c5357f0cca9c74.png [Link 7]: https://baike.baidu.com/item/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84 [Link 8]: https://baike.baidu.com/item/%E5%8F%B6%E5%AD%90%E8%8A%82%E7%82%B9 [Link 9]: https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E6%A0%91 [Link 10]: https://baike.baidu.com/item/%E6%95%B0%E6%8D%AE%E5%9D%97 [Link 11]: https://baike.baidu.com/item/%E8%8A%82%E7%82%B9 [Link 12]: https://baike.baidu.com/item/%E5%87%BD%E6%95%B0 [Link 13]: https://baike.baidu.com/item/%E7%BC%96%E7%A8%8B [Link 14]: https://baike.baidu.com/item/%E5%85%B3%E8%81%94%E6%95%B0%E7%BB%84 [2-3-4]: https://baike.baidu.com/item/2-3-4%E6%A0%91 [Link 15]: https://baike.baidu.com/item/%E6%95%B0%E6%8D%AE%E5%85%83%E7%B4%A0 [Link 16]: https://baike.baidu.com/item/%E6%A0%91%E6%97%8B%E8%BD%AC [Link 17]: https://baike.baidu.com/pic/%E7%BA%A2%E9%BB%91%E6%A0%91/2413209?fr=lemma [9358d109b3de9c828cdb8e7c6481800a18d84382.jpg]: https://gss1.bdstatic.com/-vo3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D235/sign=d093432a3101213fcb3349df61e636f8/9358d109b3de9c828cdb8e7c6481800a18d84382.jpg [9358d109b3de9c828cdb8e7c6481800a18d84382.jpg 1]: /images/20220319/ed189aa6d3a8417cabbea289efadeeba.png [86d6277f9e2f0708cdb73039ed24b899a901f25d.jpg 2]: https://gss1.bdstatic.com/-vo3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D235/sign=34cc8242d51373f0f13f689c910e4b8b/86d6277f9e2f0708cdb73039ed24b899a901f25d.jpg [86d6277f9e2f0708cdb73039ed24b899a901f25d.jpg 2 1]: /images/20220319/d94c9bdc7cb44f2f9b91acd25714b67c.png
相关 树:红黑树 1,红黑树引入 红黑树是对AVL树的补充。AVL树要求整个树的高度差不能超过1,超过后需要进行左旋或者右旋操作再次对树进行平衡,虽然这样能够解决二叉树退化为链表的缺 ╰半橙微兮°/ 2023年02月28日 01:25/ 0 赞/ 91 阅读
相关 红黑树 红黑树(Red Black Tree) 是一种自平衡二叉查找树,红黑树和AVL树类似,都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能,它虽然 谁践踏了优雅/ 2022年06月15日 12:57/ 0 赞/ 394 阅读
相关 红黑树 > 3.3 Balanced Search Trees > [http://algs4.cs.princeton.edu/33balanced/][http_algs4.c ╰+攻爆jí腚メ/ 2022年06月09日 12:48/ 0 赞/ 295 阅读
相关 红黑树 红黑树(Red Black Tree) 是一种自平衡二叉查找树,是在[计算机][Link 1]科学中用到的一种[数据结构][Link 2],典型的用途是实现[关联数组][Lin 刺骨的言语ヽ痛彻心扉/ 2022年04月23日 12:06/ 0 赞/ 245 阅读
相关 红黑树 转自 \[url\]http://www.cnblogs.com/fornever/archive/2011/12/02/2270692.html\[/url\] Dear 丶/ 2022年04月11日 05:50/ 0 赞/ 312 阅读
相关 红黑树 红黑树 概念 红黑树,又被称为对称二叉B树。 [红黑树模型][Link 1] 其本质是一种二叉查找树,单它在二叉查找树的基础上额外添加了一个标记(颜色),同时具 拼搏现实的明天。/ 2022年04月10日 02:39/ 0 赞/ 386 阅读
相关 红黑树 红黑树 R-B Tree,全称是Red-Black Tree,又称为“红黑树”,它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色,可以是红(Red)或黑 Myth丶恋晨/ 2022年02月24日 07:30/ 0 赞/ 368 阅读
相关 红黑树 先Mark,后续补充: [https://juejin.im/entry/58371f13a22b9d006882902d][https_juejin.im_entry_58 柔情只为你懂/ 2022年01月30日 14:57/ 0 赞/ 290 阅读
相关 红黑树 介绍 红黑树是一个平衡的二叉树,但不是一个完美的平衡二叉树。虽然我们希望一个所有查找都能在~lgN次比较内结束,但是这样在动态插入中保持树的完美平衡代价太高,所以,我们稍 墨蓝/ 2021年09月14日 23:34/ 0 赞/ 495 阅读
相关 红黑树 1. 从 2-3 树说起 一棵标准的 BST (二叉查找树 / 二叉搜索树)是长这个样子的: BST 其中,这棵二叉查找树中的每个结点也叫 2-结点 ,2-结点 就表示树... 系统管理员/ 2020年11月29日 04:30/ 0 赞/ 788 阅读
还没有评论,来说两句吧...