AVL樹

習題預習

1. AVL Tree是什麼？
2. AVL Tree與Binary Tree之間的區別是什麼？
3. AVL Tree如何保持平衡？
4. AVL Tree是如何進行插入和刪除操作？
5. AVL Tree的時間複雜度是多少，並舉例說明？

說明知識

AVL Tree是一種自平衡二元搜尋樹，也就是說在插入或刪除節點時，會自動調整其結構，使樹保持平衡狀態，使搜索操作的時間複雜度保持在O(log n)級別。

AVL Tree的平衡是在節點的左右子樹高度之差不超過1的情況下進行的。當發現某一個節點的左右子樹高度差超過1時，就需要進行平衡操作。

常見的平衡操作有四種：左旋、右旋、先左旋再右旋和先右旋再左旋。旋轉操作會改變節點的位置，但不會改變節點的子節點，因此旋轉操作不會導致整棵樹的搜索順序改變。

以下是一個AVL Tree的例子：

在這個例子中，插入節點3時，發現節點7和節點9的高度差為2，需要進行平衡操作，先進行右旋操作，得到以下樹：

接著再插入節點5，這次發現節點6和節點9的高度差為2，需要進行平衡操作，先進行左旋操作，得到以下樹：

這樣的AVL Tree就是一個平衡樹，可以保證搜索操作的時間複雜度為O(log n)級別。

彙總重點

AVL Tree 的重点如下：

1. 平衡因子：每个节点的左子树和右子树的高度差称为平衡因子，AVL Tree中平衡因子的绝对值不超过1。

2. 左旋和右旋：为了维护AVL Tree的平衡性，需要通过左旋或右旋操作对树进行调整。

3. 插入和删除：插入和删除节点时，要注意平衡因子的变化，需要将不平衡的节点通过旋转调整为平衡状态。

4. 查找和遍历：AVL Tree 支持快速查找和各种遍历操作，包括前序遍历、中序遍历和后序遍历。

5. 时间复杂度：AVL Tree 的操作时间复杂度为O(log n)，其中n为树中节点的数量。因此，AVL Tree在实际应用中具有很高的效率和可靠性。

知識測驗

1. 在AVL Tree中插入元素10、15、12、20、25，請列出插入後AVL Tree的前序遍歷結果。
   答案：15 12 10 20 25

2. 在一個AVL Tree中，刪除元素3，請列出刪除後AVL Tree的後序遍歷結果。
   答案：4 2 5 1

3. 在AVL Tree中查找元素8的祖先，請列出查找結果。
   答案：10 9

4. 在AVL Tree中查找元素11的後繼，請列出查找結果。
   答案：12

5. 給定一組數列{8, 12, 10, 6, 11, 9, 14, 17, 20}，請構建出一棵AVL Tree。
   答案：12 8 9 6 10 11 17 14 20