# [資演] 11- AVL樹

###### tags: `資演`

[AVL樹（Adelson-Velsky and Landis Tree）](https://www.programiz.com/dsa/avl-tree)是一種Binary search tree的實做方式，大部分的實做方式與BST一樣，差異在於AVL樹在生長（增加節點）的過程中會透過計算並調整樹的結構來讓樹維持平衡，而不會導致BST過度傾斜（不平衡）。

要達成這個目的，我們首先需要三個概念：
* 節點的高度
* 節點的的balance factor
* 高度平衡樹

## 節點的高度
節點的高度，也就是這個節點到葉節點的最長路徑長度。另一種定義方式是使用遞迴的定義，把葉節點的高度設為 $0$，其他節點的高度定義如下：
$$
高度 = \max(左小孩的高度, 右小孩的高度 )+1
$$事實上，葉節點的高度也適用這個定義，只要把那些空的子節點的高度設為 $-1$ 就行了。

## 節點的 balance factor
對於任一節點 $T$（或者說，以該節點為根的子樹），計算出節點 $T$ 的左右子節點高度，然後把左小孩高度減掉右小孩高度，即為balance factor $\text{BF}(T)$。

balance factor有以下特性：
* $\text{BF}(T) < -1$
右邊subtree比較重，需要將一些右邊節點往左邊調整。
* $-1 \leq \text{BF}(T) \leq 1$
表示平衡，暫時不用調整。
* $\text{BF}(T) > 1$
左邊subtree比較重，需要將一些左邊節點往右邊調整。

## 高度平衡樹
一棵樹是高度平衡的（height-balanced），如果它滿足以下條件：
* 它的左子樹和右子樹都是高度平衡的
* $|左小孩的高度-右小孩的高度|\leq 1$

另外，一棵空的樹是高度平衡的。

維持一棵樹的平衡，就是AVL樹最主要的目的。

遵循以下步驟，可以判斷一個二元樹是否平衡：計算根節點左右小孩的高度，得到高度後相減，如果得到的結果 $< -1$ 或 $> 1$，則表示這棵樹有某一側比較重，處於不平衡的狀態，需要調整來讓樹繼續維持平衡。下圖標示為綠色的節點為平衡，紅色為不平衡：


## AVL樹的旋轉

在遇到不平衡情況時，需要調整樹的節點，稱為旋轉（rotation）。注意旋轉前與旋轉後的樹，需要**保持它們的 in-order traversal 不變**。可以參考[這個動畫](https://en.wikipedia.org/wiki/AVL_tree#/media/File:AVL_Tree_Example.gif)來了解AVL樹是怎樣透過旋轉來調整達到平衡的。

AVL樹的旋轉有兩種基本形式：
* 左旋轉（left rotation）
* 右旋轉（right rotation）

從這兩種基本形式，衍伸出四種旋轉：
* 左左旋轉（left-left rotation, LL）
* 右右旋轉（right-right rotation, RR）
* 左右旋轉（left-right rotation, LR）
* 右左旋轉（right-left rotation, RL）

其中，LL和RR只是進行兩次相同的旋轉，故在此不再做介紹。

### 左旋轉
考慮一棵原本長這樣的樹：
我們想要在節點 $x$ 進行一次左旋轉，該怎麼做呢？首先，如果節點 $x$ 的右小孩 $y$ 有左子樹 $\beta$，把 $x$ 的右子樹換成 $\beta$：
那剩下來的 $y$ 節點和他的右子樹 $\gamma$ 呢？這時候我們要考慮三種狀況：
1. 如果 $x$ 沒有parent（也就是說，$x$ 是根節點）
--> 把 $y$ 設成 根節點
2. 如果 $x$ 的 parent 是 $p$，且 $x$ 是 $p$ 的左小孩
--> 把 $y$ 設成 $p$ 的左小孩，取代 $x$ 本來的位置
3. 如果 $x$ 的 parent 是 $p$，且 $x$ 是 $p$ 的右小孩
--> 把 $y$ 設成 $p$ 的右小孩，取代 $x$ 本來的位置


完成以上動作之後，再把以 $x$ 為根的那個子樹設成 $y$ 的左子樹。如此便完成了一次左旋轉。

### 右旋轉
考慮一棵原本長這樣的樹：

要在 $y$ 節點進行一次右旋轉，首先，如果節點 $y$ 的左小孩 $x$ 有右子樹 $\beta$，把 $y$ 的左子樹換成 $\beta$：
接著，對於剩下的 $x$ 節點及其左子樹 $\gamma$，我們一樣考慮三種情況：
1. 如果 $y$ 沒有parent（也就是說，$y$ 是根節點）
--> 把 $x$ 設成 根節點
2. 如果 $y$ 的 parent 是 $p$，且 $y$ 是 $p$ 的右小孩
--> 把 $x$ 設成 $p$ 的右小孩，取代 $y$ 本來的位置
3. 如果 $y$ 的 parent 是 $p$，且 $y$ 是 $p$ 的左小孩
--> 把 $x$ 設成 $p$ 的左小孩，取代 $y$ 本來的位置。


完成以上動作之後，再把以 $y$ 為根的那個子樹設成 $x$ 的左子樹。如此便完成了一次左旋轉。


事實上，右旋轉是跟左旋轉完全對稱的操作，只要記住一種，就能推出另外一種。

### 左右旋轉
先在 $x$ 進行一次左旋轉：
再在 $z$ 進行一次右旋轉：
如此便完成了一次左右旋轉。
### 右左旋轉
先在 $x$ 進行一次右旋轉：
再在 $z$ 進行一次左旋轉：
如此便完成了一次右左旋轉。

## AVL樹的節點插入操作
AVL樹的插入跟BST的插入如出一轍，但是在插入後需要進行旋轉以達成平衡。完成插入之後，我們必須確認是不是有節點存在違反AVL樹對balance factor的要求。

首先，我們知道，插入的新節點，一定是一個葉節點，並且它的balance factor一定是 $0$。

考慮插入前樹原本長這個樣子：

現在如果想插入一個節點 $9$，要放在哪裡呢？根據BST的定義，應該把它放在 $8$ 的右小孩。重新計算balance factor，得到：

我們發現有些節點不平衡了，需要在一些節點上進行旋轉讓樹維持平衡。這種時候可以分成兩種狀況來看：
* 節點的balance factor大於 $1$
--> 左子樹的高度比較高
--> 進行**右旋轉**或**左右旋轉**
--> 如果**要插入的元素小於左小孩**，進行右旋轉
--> 否則進行左右旋轉
* 節點的balance factor小於 $-1$
--> 右子樹的高度比較高
--> 進行**左旋轉**或**右左旋轉**
--> 如果**要插入的元素大於右小孩**，進行左旋轉
--> 否則進行右左旋轉

在這個案例中，我們發現 $11$ 這個節點需要進行一次左右旋轉：

最後得到的樹為：

## AVL樹的節點刪除操作
AVL樹的刪除操作和BST相同，只是刪除後一樣要透過旋轉來維持平衡。

首先，我們必須先透過尋訪來找到要刪除的那個節點。

對於要刪除的節點有三種情形需要考慮：
* 要刪除的節點是葉節點
--> 直接刪除該節點即可
* 要刪除的節點有一個子節點（左小孩或右小孩）
--> 把該節點刪除後，由小孩取代該節點原本的位置即可
* 要刪除的節點有兩個子節點（左右小孩都非空）
--> 找出該節點的in-order traversal的下一個節點（in-order successer），把它原本的位置抽換成那個節點

進行以上動作之後，再做rebalance（也就是進行適當的旋轉），就完成了AVL樹的節點刪除動作。

例如，我們想在下面的樹刪除掉 $13$ 這個節點：

我們發現節點 $13$ 有兩個小孩，而其in-order successer為 $21$，所以我們就用21來取代它原本的位置，並重新計算balance factor：

在這邊我們對 $21$ 這個節點進行一次右旋轉：

得到：

## 程式實作

# AVL tree implementation in Python


import sys

# Create a tree node
class TreeNode(object):
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1


class AVLTree(object):

    # Function to insert a node
    def insert_node(self, root, key):

        # Find the correct location and insert the node
        if not root:
            return TreeNode(key)
        elif key < root.key:
            root.left = self.insert_node(root.left, key)
        else:
            root.right = self.insert_node(root.right, key)

        root.height = 1 + max(self.getHeight(root.left),
                              self.getHeight(root.right))

        # Update the balance factor and balance the tree
        balanceFactor = self.getBalance(root)
        if balanceFactor > 1:
            if key < root.left.key:
                return self.rightRotate(root)
            else:
                root.left = self.leftRotate(root.left)
                return self.rightRotate(root)

        if balanceFactor < -1:
            if key > root.right.key:
                return self.leftRotate(root)
            else:
                root.right = self.rightRotate(root.right)
                return self.leftRotate(root)

        return root

    # Function to delete a node
    def delete_node(self, root, key):

        # Find the node to be deleted and remove it
        if not root:
            return root
        elif key < root.key:
            root.left = self.delete_node(root.left, key)
        elif key > root.key:
            root.right = self.delete_node(root.right, key)
        else:
            if root.left is None:
                temp = root.right
                root = None
                return temp
            elif root.right is None:
                temp = root.left
                root = None
                return temp
            temp = self.getMinValueNode(root.right)
            root.key = temp.key
            root.right = self.delete_node(root.right,
                                          temp.key)
        if root is None:
            return root

        # Update the balance factor of nodes
        root.height = 1 + max(self.getHeight(root.left),
                              self.getHeight(root.right))

        balanceFactor = self.getBalance(root)

        # Balance the tree
        if balanceFactor > 1:
            if self.getBalance(root.left) >= 0:
                return self.rightRotate(root)
            else:
                root.left = self.leftRotate(root.left)
                return self.rightRotate(root)
        if balanceFactor < -1:
            if self.getBalance(root.right) <= 0:
                return self.leftRotate(root)
            else:
                root.right = self.rightRotate(root.right)
                return self.leftRotate(root)
        return root

    # Function to perform left rotation
    def leftRotate(self, z):
        y = z.right
        T2 = y.left
        y.left = z
        z.right = T2
        z.height = 1 + max(self.getHeight(z.left),
                           self.getHeight(z.right))
        y.height = 1 + max(self.getHeight(y.left),
                           self.getHeight(y.right))
        return y

    # Function to perform right rotation
    def rightRotate(self, z):
        y = z.left
        T3 = y.right
        y.right = z
        z.left = T3
        z.height = 1 + max(self.getHeight(z.left),
                           self.getHeight(z.right))
        y.height = 1 + max(self.getHeight(y.left),
                           self.getHeight(y.right))
        return y

    # Get the height of the node
    def getHeight(self, root):
        if not root:
            return 0
        return root.height

    # Get balance factor of the node
    def getBalance(self, root):
        if not root:
            return 0
        return self.getHeight(root.left) - self.getHeight(root.right)

    def getMinValueNode(self, root):
        if root is None or root.left is None:
            return root
        return self.getMinValueNode(root.left)

    def preOrder(self, root):
        if not root:
            return
        print("{0} ".format(root.key), end="")
        self.preOrder(root.left)
        self.preOrder(root.right)

    # Print the tree
    def printHelper(self, currPtr, indent, last):
        if currPtr != None:
            sys.stdout.write(indent)
            if last:
                sys.stdout.write("R----")
                indent += "     "
            else:
                sys.stdout.write("L----")
                indent += "|    "
            print(currPtr.key)
            self.printHelper(currPtr.left, indent, False)
            self.printHelper(currPtr.right, indent, True)