資料結構›Ch5 樹狀結構第 1 題/共 48 題
1. AVL Tree 插入與旋轉
#DS-05-001中AVL Tree旋轉
給定一個空的 AVL Tree,依序插入 14, 17, 11, 7, 53, 4, 13, 12,請畫出最終的樹狀結構,並標明每次插入後是否需要旋轉。
參考答案與解析
依序插入並在失衡時旋轉:
- 插入 14、17、11、7、53:都沒有失衡,樹為 14(左子 11,11 的左子 7;右子 17,17 的右子 53)。
- 插入 4:成為 7 的左子。節點 11 左子樹高 2、右子樹高 0,LL 型失衡,對 11 右旋:7 升上來,左子 4、右子 11。
- 插入 13:成為 11 的右子,沒有失衡。
- 插入 12:成為 13 的左子。節點 11 左子樹高 0、右子樹高 2,RL 型失衡,先對 13 右旋、再對 11 左旋:12 升上來,左子 11、右子 13。
最終的樹(根為 14):
14
/ \
7 17
/ \ \
4 12 53
/ \
11 13
共旋轉兩次:插入 4 時一次單旋轉(LL),插入 12 時一次雙旋轉(RL),其餘插入都不需要旋轉。
📄 練習題
▤完整推導請見《WH 資工筆記 · 資料結構》Ch5 樹狀結構