作者zaq851017 (交大小V)
看板Grad-ProbAsk
标题[理工] 资工 关於红黑树的平衡 跟 AVL高度平衡
时间Mon Dec 3 14:02:20 2018
如题。 今天读一读想到的。
我们知道AVL 的定义是 abs(Hl - Hr) <=1
就是左子树高度和右子树高度是差+-1以内的。
因为红黑树本身也是种平衡树<课本所说> 这里的平衡有详细定义吗?
因为我画红黑树的过程中，Hl-Hr有=2的 我想问不知道红黑树的Hl-Hr有一个range范围吗?
感谢各位的观看。
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.113.136.218
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1543816942.A.FA6.html
1F：推 wei12f8158: 从root算最长跟最短距离不超过2倍（证明的话洪逸说太 12/03 15:11
真的太感谢大大了！！！
2F：→ wei12f8158: 复杂了） 12/03 15:11
4F：推 AliennC: 如果你想深入了解红黑树的话，我会建议你去网路上找找设 12/03 16:19
5F：→ AliennC: 计红黑树的 Robert Sedgewick 教授的影片，他在普林斯顿 12/03 16:19
6F：→ AliennC: 演算法课中有简略说明他当初设计的想法，看完之後你应该 12/03 16:19
7F：→ AliennC: 可以更了解红黑树 "为什麽" 是那样操作，懂原理之後对於 12/03 16:19
8F：→ AliennC: 原本的问题应该自己想一下就通了 12/03 16:19
哈哈 没很想在考前仔细理解 不过还是感谢大大
※ 编辑: zaq851017 (140.113.136.218), 12/03/2018 16:38:25
※ 编辑: zaq851017 (140.113.136.218), 12/03/2018 16:38:53
9F：推 b0920075: 最短一定是全黑，最长一定是红黑交错，而从任节点开始 12/03 16:52
10F：→ b0920075: 到子节点黑色数目相同，故最长最短黑色都一样数目，而 12/03 16:52
11F：→ b0920075: 黑红交错，红色数量会跟黑色一样多，所以不超过两倍 12/03 16:52
12F：推 whatabiggun: 楼上大哥的解释很有道理欸 08/03 19:54