[理工][資結][DS]台大102電機丙

看板Grad-ProbAsk作者 (Eric)時間13年前 (2013/02/02 17:48), 編輯推噓4(4推 0噓 10→)
留言14則, 5人參與, 最新討論串1/1
今天考出一題關於紅黑數的高度的題目（是非題） 是問說「紅黑樹的左右子樹高度差會<=2」 我試著畫，盡量讓他不平衡 感覺答案應該是True 不知道版上的各位有無其他的見解？ 謝謝！ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.4.174
→
02/02 19:12, , 1F
沒錯...
02/02 19:12, 1F
→
02/02 19:13, , 2F
我那棵樹畫好幾次...我還以為我畫錯
02/02 19:13, 2F
→
02/02 19:13, , 3F
因為只知道 AVL 插 1
02/02 19:13, 3F
→
02/02 19:13, , 4F
不過最終還是把答案擦掉..直接不寫
02/02 19:13, 4F
→
02/02 19:14, , 5F
回來看筆記..確實可以差2..
02/02 19:14, 5F
推
02/02 19:14, , 6F
紅黑樹、2-3樹、B樹也是高度平衡樹
02/02 19:14, 6F
推
02/02 21:13, , 7F
大家覺得今年題目簡單嗎?
02/02 21:13, 7F
→
02/02 21:14, , 8F
倒扣四分好痛@@
02/02 21:14, 8F
推
02/02 21:51, , 9F
我是選false耶，有畫出例子來，而且印象中，紅黑樹root
02/02 21:51, 9F
→
02/02 21:51, , 10F
到leaf的長距離最多是最短距離的2倍，而不是最多差2
02/02 21:51, 10F
推
02/02 22:08, , 11F
我是用這順序去試100,50,150,25,75,10,40,0,15,-5,5,
02/02 22:08, 11F
→
02/02 22:09, , 12F
-10,-3,-15，最後左子樹高5，右子樹高2，整個樹高6
02/02 22:09, 12F
→
02/02 23:28, , 13F
真令人振奮...我那題亂寫 false 還對..那他就還我4分了
02/02 23:28, 13F
→
02/03 06:14, , 14F
QQ爆了，感謝kaifreeice大大的見解~
02/03 06:14, 14F
‣ 更多 eric78929 的文章
文章代碼(AID): #1H3E3ekR (Grad-ProbAsk)