[理工] 紅黑樹

[PTTleader (PTT領導)]

http://imgur.com/a/oFpgR

右邊那個樹

是紅黑樹嗎

紅黑樹是balanced tree

可是我感覺它不是balanced tree

還是我搞錯定義了

balanced tree 的定義是什麼?

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.224.41.243
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1479132810.A.F27.html
→ ken52011219: 紅黑樹的Balabce是看 black 是否一樣高
→ ken52011219: 無關子樹的高度是否一樣
推 aa06697: 洪逸上課有說紅黑樹balance不是指本身balance 是指對應回
→ aa06697: 去的234tree balance
推 aa06697: 另外wiki: The balancing of the tree is not perfect, b
→ aa06697: ut it is good enough to allow it to guarantee searchi
→ aa06697: ng in O(log n) time