Re: [理工] 資結-balance tree已刪文
: 請問一下紅黑樹是不是balance 的BST
: 我不知道所謂的balance BST 的balance有什麼定義
: 怎麼樣才叫做balance呢？
: AVL的定義是左右子樹高度最多差一
: 那這只是AVL的定義還是說這就是balance
: 我找不到一個很明確的定義
: 想請問大家
: 推 cksh3300110:AVL定義對 紅黑樹就不是BALANCE cormen上寫是近似平衡 02/12 14:31
: → annheilong:balance: h = O(lg n) 非樹葉層都是填滿的 02/12 14:34
: 推 joker0634:AVL的h=O(1.44logn) red-black的h=O(2logn) 02/12 14:47
: 推 annheilong:紅黑樹是balance tree吧? 02/12 23:38
: 推 cksh3300110:回樓上其實還是可造出左右高度大於一的紅黑樹滿足條件 02/13 00:06
可以造出高度差大於一沒錯
但是AVL的條件就是balance定義嗎?
Definition:
A tree where no leaf is much farther away from the root than any other leaf.
Different balancing schemes allow different definitions of "much farther"
and different amounts of work to keep them balanced.
http://xw2k.nist.gov/dads/html/balancedtree.html
我也覺得"balance"沒有所謂的定義
很像是一個概念而已
還是有人能找出課本或是補習班講義上
關於balance定義的文句嗎??
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.230.123.196
※ 編輯: starbury8 來自: 61.230.123.196 (02/13 00:36)
推
02/13 00:49, , 1F
02/13 00:49, 1F
→
02/13 00:50, , 2F
02/13 00:50, 2F
→
02/13 00:56, , 3F
02/13 00:56, 3F
推
02/13 01:08, , 4F
02/13 01:08, 4F
→
02/13 01:11, , 5F
02/13 01:11, 5F
→
02/13 01:12, , 6F
02/13 01:12, 6F
→
02/13 09:55, , 7F
02/13 09:55, 7F
→
02/13 09:56, , 8F
02/13 09:56, 8F
推
02/13 11:24, , 9F
02/13 11:24, 9F
→
02/13 11:25, , 10F
02/13 11:25, 10F
→
02/13 11:25, , 11F
02/13 11:25, 11F
→
09/11 14:15, , 12F
09/11 14:15, 12F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：