60
/ \
45 65
/ \ \
32 54 74
/
52
1. 31
2. 55
3. 64
4. 66
ans: 66
為什麼是66? 要旋轉不是要右子樹的高度減去左子樹的高度不等於1 or 0 or -1 嗎?
更新1:
to Jacob Lee: 插入66之後,左子樹不是45,32這邊嗎? 還是我的認知不太正確? P.S 要怎麼做才能夠像你的回答一樣文字可變色,而且樹格式又不會跑掉?
不明白這個AVL樹的解法?
2009-05-07 8:34 am
下圖AVL樹,插入何者需要旋轉?
60
/ \
45 65
/ \ \
32 54 74
/
52
1. 31
2. 55
3. 64
4. 66
ans: 66
為什麼是66? 要旋轉不是要右子樹的高度減去左子樹的高度不等於1 or 0 or -1 嗎?
60
/ \
45 65
/ \ \
32 54 74
/
52
1. 31
2. 55
3. 64
4. 66
ans: 66
為什麼是66? 要旋轉不是要右子樹的高度減去左子樹的高度不等於1 or 0 or -1 嗎?
回答 (2)
2009-05-07 3:07 pm
✔ 最佳答案
60／ ＼
45 65
／ ＼ ／ ＼
32 54 64 74
／ ／ ＼
31 52 55
由上圖，可知：31, 55, 64 都不會有問題
60
／ ＼
45 65
／ ＼ ＼
32 54 66
／ ＼
52 74
但，66加入時，65那裡，右子樹高度為二，左子數高度為○！
差為二！
所以，插入 66 要旋轉。
哪不懂，請再問。 ^_^
2009-05-07 10:32:25 補充：
是 65 的左右不平衡！
不是 60 的！
60 的一直都很好。
格式不變：用全型
彩色：成為實習生 及 以上
參考: 開始學 種樹／繪圖 的 Jacob
2009-05-07 2:45 pm
After 66 is inserted, the sub-tree 60-65-74-66 will have a height > 1 and thus will have to rotate with 65-74-66.
收錄日期: 2021-04-30 13:27:38
原文連結 [永久失效]:
https://hk.answers.yahoo.com/question/index?qid=20090507000016KK00332