[理工] 資結-balance tree

看板Grad-ProbAsk作者 (科比強暴犯)時間13年前 (2011/02/12 12:32), 編輯推噓4(4推 0噓 1→)
留言5則, 3人參與, 最新討論串1/2 (看更多)
請問一下紅黑樹是不是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)
推
02/12 14:31, , 1F
AVL定義對 紅黑樹就不是BALANCE cormen上寫是近似平衡
02/12 14:31, 1F
→
02/12 14:34, , 2F
balance: h = O(lg n) 非樹葉層都是填滿的
02/12 14:34, 2F
推
02/12 14:47, , 3F
AVL的h=O(1.44logn) red-black的h=O(2logn)
02/12 14:47, 3F
推
02/12 23:38, , 4F
紅黑樹是balance tree吧?
02/12 23:38, 4F
推
02/13 00:06, , 5F
回樓上其實還是可造出左右高度大於一的紅黑樹滿足條件
02/13 00:06, 5F
‣ 更多 koberaper 的文章
文章代碼(AID): #1DLWrXZC (Grad-ProbAsk)
‣ 更多 koberaper 的文章
文章代碼(AID): #1DLWrXZC (Grad-ProbAsk)