16 | 红黑树（上）：红黑树基础与插入调整操作

胡光

我们都知道，AVL 树有一个缺点，每次更新后都需要调整自己的平衡性。红黑树可以很好地解决这个问题。

公开

同步至部落

取消

完成

0/2000

荧光笔

直线

曲线

笔记

复制

AI

深入了解
翻译
英语
中文简体
中文繁体
法语
德语
日语
韩语
俄语
西班牙语
阿拉伯语
解释
总结

该试读文章来自《常用算法 25 讲》，如需阅读全部文章，
请先通过赠一得一解锁课程

赠一得一

登录后留言

全部留言(6)

最新
精选

norton/Dark
老师，我有个疑问，弄懂这个好像对leetcode解题没什么帮助，没什么实际价值？
编辑回复: 这位同学你好，首先，红黑树在基础岗位面试的时候可能都会问。其次，红黑树这个数据结构里面的一些比较巧妙的思维还是很有用的。而且，刷LeetCode，其实并不是为了背答案，过面试。而是为了锻炼算法思维，就像面试官考察算法是为了考察我们个人的基本功，看看我们能否胜任基础开发工作。所以，我们一定要搞清楚，到底是为了什么刷leetcode的题目。

3
小树
胡老师，插入元素case1那里不太明白为什么要将C变成红色，不变红好像也没破坏红黑树的性质，反而变成红色要向上调整。如果C恰好是根，那变红不是直接破坏了根必须是黑色这个性质吗？
编辑回复: 这位同学你好，如果C不变红，那么C所在的子树里面所有的路径就会多一个黑色节点，性质5直接被打破了，如果C是根无所谓，C不是根一定打破性质5


庄家杰
胡老师好，关于红黑树一直有一个疑问，通过旋转保持红黑树稳定，这种特性是经过严格的数学证明还是？为什么通过旋转就可以保持稳定？百度过很多文章都是说怎么旋转怎么处理，但是没有看到为什么这么做就可以得到结果。。。
1
5
梁智行
请问一下老师，设计出可以比平衡树更少调整的红黑树，是基于什么出发点或者思路？或者说是怎么设计出来的

1
陈阳
“所以，对于有 N 个节点的两个孩子，以它们为根的子树分别会有至少 2blackheight(T)−1 个节点，而以 N 为根的子树至少会有 2blackheight(T)−1×2+1=2blackheight(T)−1 个节点。” 里面的N到底指的是数量N 还是节点N 看不懂，前后对不上


小树
又仔细想了想，确实C要变红，因为如果不变红经过A,B路径的黑节点会比其他路径多一个。"因此，处理方法就很简单了，把 z 节点的父亲和叔叔，也就是 A 节点和 D 节点变成黑色，这样 z 的祖父 C 节点就变成红色了。"，第一遍看这句话的时候没有考虑到非经过A或者B节点的路径，还有如果C是根节点应该不用变成红色吧？否则变了还得调整过来，否则破坏了性质2?



收起评论