06｜TreeMap：红黑树真的有那么难吗？
该思维导图由 AI 生成，仅供参考
荧光笔
直线
曲线- 深入了解
- 翻译
- 解释
- 总结
红黑树是一种自平衡的二叉搜索树，具有良好的查询、插入和删除时间复杂度，被广泛应用于中间件等场景。本文深入浅出地解释了红黑树的本质，打破了读者对红黑树难以理解的困惑，为进一步深入学习打下基础。文章从二分查找树和平衡二分查找树的概念出发，介绍了红黑树的由来和实现原理。通过对“2-3树”的学习，读者可以理解红黑树设计的奇妙之处。红黑树的定义和约束保证了每一颗红黑树和2-3 Tree是一一对应的，并且红黑树的实现也没有想象中的那么困难。文章还介绍了红黑树的基本操作，如旋转操作的实现，帮助读者更好地理解红黑树和2-3树之间的关系。此外，文章还讨论了红黑树的操作复杂度，以及如何利用红黑树统计单词数量。总之，红黑树是一个复杂但非常值得掌握的数据结构，通过理解其本质，读者可以对红黑树有一个比较不错的掌握。
《业务开发算法 50 讲》，新⼈⾸单¥59
全部留言(10)
- 最新
- 精选
- Paul Shan红黑树每次看的时候都好像明白了，过一段时间就会忘记旋转细节。但是，红黑树确实是工程实现的典范，为了让完全二叉树容纳各种数量的节点，引入了2，3树的概念，也就是保持树的形状为完全二叉树，让树的节点容纳一个或者两个元素来承载变化。有了这个灵活性，平衡二叉树的实现就方便很多，而且也高效不少（半数插入不用调整树的结构）。增加节点的颜色来代替异构节点简化了实现。引入了根节点为黑色和红色节点只出现在左侧的约束，在没有降低红黑树表达功能和性能的前提下，进一步简化实现。
作者回复: 总结的很不错
2021-12-2327 
友红黑看过几个版本 一个是算法4 一个是邓公的 关于旋转操作我看过邓公的那个 connect34方法 我惊了我根本没想到可以这样通过打散然后组合的方式作者回复: 哈哈哈 那我也去看看邓公的课，学习一下
2021-12-235
qinsi左偏红黑树和算法4作者的亲自讲解 https://www.coursera.org/lecture/algorithms-part1/red-black-bsts-GZe13作者回复: 好耶！ 学到了～
2021-12-233
blentleavl 实现更简单，比红黑树性能并没有差多少，为什么应用场景没有红黑树那么广呢作者回复: 供参考 ------- 红黑树的查询性能略微逊色于AVL树，因为他比avl树会稍微不平衡最多一层，也就是说红黑树的查询性能只比相同内容的avl树最多多一次比较，但是，红黑树在插入和删除上完爆avl树， avl树每次插入删除会进行大量的平衡度计算，而红黑树为了维持红黑性质所做的红黑变换和旋转的开销，相较于avl树为了维持平衡的开销要小得多。 作者：陈智超 链接：http://www.zhihu.com/question/43744788/answer/98258881
2021-12-2332
LW第一次看懂了红黑树实现作者回复: 嗯嗯 重点就是先搞懂2-3树
2022-01-251
.这个比另一个专栏红黑树讲得好。。。。那个专栏红黑树我直接放弃了作者回复: 哈哈哈！感谢支持；欢迎+v： constant_variation 一起学习交流～ 觉得有帮助的话，也可以推荐给朋友一起学习哈。
2021-12-28
这是白猫HashMap 和 TreeMap 都是使用红黑树实现的，区别是HashMap多了外面的基于hashCode的有序链表，因此在重复数据较多时使用Treemap，反之大量不重复数据时使用 HashMap，是不是这样呢老师作者回复: HashMap的核心不在于红黑树，而是hash算法，不用红黑树也可以实现Hashmap。 TreeMap更重要的特点是有序性；比如你有类似需要时刻取出最大的元素，或者最小的元素之类的操作就可以优先使用TreeMap。
2021-12-23
拓山1、应该再说明下 为什么同样是平衡二叉树的AVL树没有被选中 2、红黑树严格意义上应该是等价2-3-4树而不是2-3树2023-08-09归属地：浙江
大叮当老师好，请教个问题，完全二叉树为啥要规定可以有左叶子节点没有右叶子节点，这个规定的原因是什么呢？2022-10-31归属地：中国香港1
| ~浑蛋~这一点不是很明白： 2-3 树上，每个节点到叶子节点的数量一定是一样的2022-07-023
