標題:
Avl tree問題求解
發問:
給特定順序的輸入數字。5 473 35 8 76 11 45 97 依序插入avl tree 中 怎麼算 還有平衡因子怎算？
- 天使熊做法@1@
- 五到六年級數學
- 大耳狗用品@1@
- 急!!!!請問750ML的香水大概幾公斤或是幾磅-
- 我想請問組這台電腦配備還可以嗎-
- 太陽效率計算問題--應急(徵求高手)@1@
- 不知來歷的紅包
- 尋懂稅務的大大幫忙～求遺產稅計算詳解
- SPALDING籃球的問題-@1@
- 士林好吃的客家菜-
此文章來自奇摩知識+如有不便請留言告知
最佳解答:
前幾天剛回答 AVL, 針對以下計算過程不懂可參考，網址列在參考資料欄 平衡因子算法為，一個節點左子樹高度減右子樹高度 1. 新增 5, tree 只有這個 node 它沒有任何子樹，平衡因子為 0 2. 新增 473, 473>5 故加在 5 的右子樹 473 平衡因子也為 0, 5 的平衡因子因為有右子樹而變成 -1 3. 新增 35, 被排在 473 的左子樹 473 因為多了左子樹，平衡因子變 1; 5 因為右子樹變高，平衡因子變 -2 5 因為平衡因子超過 ±1 而不平衡，此狀況為 RL 473, 35 先做 LL 旋轉把 35 取代 473 再 5, 35 做 RR 旋轉使 35 成為 root, 調整後平衡因子皆為 0 4. 新增 8, 比較完後其為 5 的右子樹 5, 35 平衡因子分別變為 -1, 1 5. 新增 76, 其為 473 的左子樹 473, 35 的平衡因子分別變為 1, 0 6. 新增 11, 其成為 8 的右子樹 8, 5, 35 平衡因子分別變為 -1, -2, 1 造成 5 的 node 不平衡，再次用 RR 旋轉方式 8 取代 5; 5, 11 變成它的兩個子樹，5, 8, 35 平衡因子都改為 0 7. 新增 45, 成為 76 的左子樹 76, 473, 35 平衡因子各改為 1, 2, -1 此為 LL 旋轉，76 代替 473, 45 與 473 為 76 左右子樹 76, 473, 35 平衡因子都改為 0 8. 新增 97, 成為 473 的左子樹 473, 76, 35 平衡因子各改為 1, -1, -1 故最後結果： n(l, r), 其中 n 為 node 的資料，l, r 為其左右子樹 node 的資料 35(8, 76) 8(5, 11) 76(45, 473) 473(--, 97), -- 表示無左子樹 無特別說明者為 leaf node 結算平衡因子除步驟 8 指定的改變外其他皆 0 希望這樣解釋對您有幫助！
其他解答:7C4150FCDCEDD023
留言列表
