作者koberaper (科比強暴犯)
看板Grad-ProbAsk
標題[理工] 資結-balance tree
時間Sat Feb 12 12:32:31 2011
請問一下紅黑樹是不是balance 的BST
我不知道所謂的balance BST 的balance有什麼定義
怎麼樣才叫做balance呢?
AVL的定義是左右子樹高度最多差一
那這只是AVL的定義還是說這就是balance
我找不到一個很明確的定義
想請問大家
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.136
※ 編輯: koberaper 來自: 140.112.30.136 (02/12 12:34)
1F:推 cksh3300110:AVL定義對 紅黑樹就不是BALANCE cormen上寫是近似平衡 02/12 14:31
2F:→ annheilong:balance: h = O(lg n) 非樹葉層都是填滿的 02/12 14:34
3F:推 joker0634:AVL的h=O(1.44logn) red-black的h=O(2logn) 02/12 14:47
4F:推 annheilong:紅黑樹是balance tree吧? 02/12 23:38
5F:推 cksh3300110:回樓上其實還是可造出左右高度大於一的紅黑樹滿足條件 02/13 00:06