作者RUOK5566 (乌绿微微)
看板Grad-ProbAsk
标题[理工] 红黑树高度的worst case ？
时间Sat Jan 18 04:36:04 2020
<课本内容>
假设红黑树有 n 个内部节点，
每条路径有 r 个black nodes，
则其高度h >= 2log[2] (n+1)
h的worst case为2log[2] (n+1)
《课本证明》
（a) h <= 2r
（b) n >= 2^r-1 即 r <= log[2] (n+1)
故得证 h <= 2log[2] (n+1)
<疑问>
但是h <= 2r <= 2log[2] (n+1)
I. 前面的h=2r成立时
代表最长路径红黑相间
II. 後面的2r = 2log[2] (n+1)成立时
代表n个节点都是黑色的
所以I & II 不会同时成立
是不是应该写成 h < 2log[2] (n+1) ？
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 220.142.74.15 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1579293366.A.48B.html
1F：推 mi981027: 满有道理的01/18 06:37
2F：推 hero97212: 2r和 2log(n+1)没有直接的关系 所以2r<=2log(n+1)这个01/18 08:09
3F：→ hero97212: 假设不成立01/18 08:09
4F：→ mi981027: 没有直接关系是什麽意思01/18 09:23
5F：→ hero97212: 比方说a<=b , a<=c01/18 10:43
6F：→ hero97212: 不只到b和c谁比较大 不能直接a<= b<= c01/18 10:45
7F：→ hero97212: *知道01/18 10:46
8F：→ mi981027: 2r <= 2log(n+1)是根据b得来的01/18 10:48
9F：推 mi981027: 当然写<=不会出错啦 但原po提的这个是更严格的upper bou01/18 10:51
10F：→ mi981027: nd 我觉得满有道理的 也就是我们其实画不出 h = 2 ceili01/18 10:51
11F：→ mi981027: ng (log(n+1)) 的红黑树01/18 10:51
12F：推 hero97212: 没看到那行 抱歉01/18 11:00
13F：推 hero97212: 这样蛮有道理的01/18 11:02
因为一直看到worst case是2log(n+1)的叙述
但是画不出来，想说是不是我对红黑树的理解有问题
这样看来课本想表达的重点应该是
->红黑树高度worst case的复杂度=O(log n)
感谢大家一起参与讨论～
※ 编辑: RUOK5566 (220.142.74.15 台湾), 01/18/2020 17:45:42