###### tags: `資料結構` `Python`

# 資料結構 | AVL Tree 的介紹及實作 | 使用 Python

## 平衡二元樹
為了降低搜尋所花費的時間，二元樹通常是高度越低越好，但是對於經常變動的資料來說，這樣可能會造成二元樹的歪曲

假設我有一陣列 `[1,2,3,4,5]`輸入到二元樹，根據大的放右子樹，小的放左子樹會形成這樣的結構


可以見到，二元樹極度的歪斜，這又被稱為歪斜樹(Skewed Tree)。最慘這可能把搜尋的效率降低到 $O(n)$

為了解決這種方式，有了平衡樹的產生，平衡樹會在每次變動資料時整理二元樹的排序，讓他始終保持在最佳化

## AVL Tree
其中 `AVL Tree` 是最早被發明的自平衡二元搜索樹（self-balancing binary search tree）
他會在每次輸入新的值後改變樹的結構，讓樹保持平衡，讓它保持著每個節點的左右子樹高度差不超過$1$的特性

$H_l$ 表示左子樹高度，$H_r$ 右子樹的高度。兩者高度不能高於$1$ $$|H_l - H_r| > 1 $$

**以下是個不平衡二元樹**
如果你從root節點 來看，右子樹的高度為4，但是左子樹的高度卻是2，`|4-2|=2 > 1` 很明顯的不平衡

**而這是平衡後的二元樹**
從root來看左子樹高度為3，右子樹高度為2，`|3-2|=1 <= 1`

## 旋轉
AVL樹是一種自平衡二元搜尋樹，左旋和右旋是AVL樹中的兩種基本操作

### 左旋
左旋是指將某個節點的右子樹作為根節點，並將該節點作為其右子樹的左子樹。這個操作可以用來解決當某個節點的右子樹比左子樹高度更高時，使其保持平衡

把步驟拆分

1. 從 t1 獲取 t2
2. 從 t1 獲取 sub_root
3. 從 t2 獲取 o
4. t2.right 設為 t1
5. t1.parent 設為 t2
6. t1.left 設為 o
7. 如果 o 非 None 則 o.parent 設為 t1
8. t2.parent 設為 sub_root
9. 如果sub_root 是 None 則代表 t2 為 root
10. 如果非 None 則代表 t1 是 sub_root 的左或右子點
11. 更新高度

def _left_rotate(self, t1):
        sub_root = t1.parent
        t2 = t1.right
        o = t2.left
        #* 交換
        t2.left = t1
        t1.parent = t2
        t1.right = o
        if o != None: o.parent = t1
        #* 設定 sub_root
        t2.parent = sub_root
        if sub_root == None:
            self.root = t2
        else:
            if sub_root.left == t1: 
                sub_root.left = t2
            else: 
                sub_root.right = t2
        # 設定變換後的高度 
        t1.height = self._get_height(self._get_taller_node(t1)) + 1
        t2.height = self._get_height(self._get_taller_node(t2)) + 1

### 右旋
右旋是指將某個節點的左子樹作為根節點，並將該節點作為其左子樹的右子樹。這個操作可以用來解決當某個節點的左子樹比右子樹高度更高時，使其保持平衡

1. 從 t1 獲取 t2
2. 從 t1 獲取 sub_root
3. 從 t2 獲取 o
4. t2.left 設為 t1
5. t1.parent 設為 t2
6. t1.right 設為 o
7. 如果 o 非 None 則 o.parent 設為 t1
8. t2.parent 設為 sub_root
9. 如果sub_root 是 None 則代表 t2 為 root
10. 如果非 None 則代表 t1 是 sub_root 的左或右子點
11. 更新高度

    def _right_rotate(self, t1):
        sub_root = t1.parent
        t2 = t1.left
        o = t2.right
        #* 交換
        t2.right = t1
        t1.parent = t2
        t1.left = o
        if o != None: o.parent = t1
        #* 設定 sub_root
        t2.parent = sub_root
        if sub_root == None:
            self.root = t2
        else:
            if sub_root.left == t1:
                sub_root.left = t2
            else: 
                sub_root.right = t2
        # 設定變換後的高度
        t1.height = self._get_height(self._get_taller_node(t1)) + 1
        t2.height = self._get_height(self._get_taller_node(t2)) + 1

## 實作 AVL Tree

### 新增
每次新增時可能會打破樹的平衡，所以需要進行檢查和重新排序樹，流程會分成以下三個步驟

1. 輸入新的資料
2. 比較左右兩個子樹的高度
3. 如果大於1，根據歪斜的種類執行相對應的方法

#### 1. 輸入新資料

在輸入新資料後執行檢查

def _insert(self,value,cur_node):
    if value < cur_node.value:
        if cur_node.left == None:
    	    cur_node.left = node(value)
    	    cur_node.left.parent = cur_node 
    	    self._inspect_insertion(cur_node.left) # 檢查是否平衡
    else:
        self._insert(value,cur_node.left)
        
    elif value > cur_node.value:
        if cur_node.right == None:
    	    cur_node.right = node(value)
    	    cur_node.right.parent = cur_node 
    	    self._inspect_insertion(cur_node.right) # 檢查是否平衡
    	else:
            self._insert(value,cur_node.right) 
    else:
        print("Value 已存在!")

#### 2. 比較左右兩個子樹的高度

def _inspect_insertion(self,cur_node,path=[]):
    # 當為root節點則返回
    if cur_node.parent == None: return
    
    # 紀錄每次遞規時的node
    path = [cur_node] + path  

    # 算出父節點左右子樹的高度
    left_height = self.get_height(cur_node.parent.left)
    right_height = self.get_height(cur_node.parent.right)

    # 如果左右子樹高度 > 1 則執行
    if abs(left_height - right_height) > 1:
    	path=[cur_node.parent] + path
    	self._rebalance_node(path[0], path[1], path[2])
    	return

    # 更新當前高度
    new_height=1+cur_node.height 
    if new_height>cur_node.parent.height:
    	cur_node.parent.height = new_height

    # 執行遞規
    self._inspect_insertion(cur_node.parent, path)

#### 3. 執行方法
執行的方式有分為四個種類，分別為
1. LL，兩次都左
2. RR，兩次都右
3. LR，先左再右
4. RL，先右再左

##### LL
假設有一不平衡樹，`t2`是`t1`的左子節點，`t3`是`t2`的左子節點，如下圖


根據上面的圖來看，它需要進行`右旋`

if t1.left == t2 and t2.left == t3:
    self._right_rotation(t1)

##### RR
RR 也和 LL 一樣，不過需要左右顛倒

假設有一不平衡樹，`t2`是`t1`的右子節點，`t3`是`t2`的右子節點，如下圖


根據上面的圖來看，它需要進行`左旋`

if t1.right == t2 and t2.right == t3:
    self._left_rotation(t1)

##### LR
假設有一不平衡樹，`t2`是`t1`的左子節點，`t3`是`t2`的右子節點，如下圖


遇到這種你可以先使用`左旋`，再使用`右旋`，不過要注意起始點的位置

if t1.left == t2 and t2.right == t3:
    self._left_rotation(t2)
    self._right_rotation(t1)

##### RL
假設有一不平衡樹，`t2`是`t1`的右子節點，`t3`是`t2`的左子節點，如下圖


你可以先使用`右旋`，再使用`左旋`

if t1.right == t2 and t2.left == t3:
	self._right_rotate(t2)
	self._left_rotate(t1)

### 刪除
如果要刪除節點可能會打亂樹的平衡，所以在刪除完節點後需要再重新診斷並平衡樹

1. 刪除節點
2. 診斷被刪除節點的父節點左右兩子樹的高度
3. 執行平衡

#### 1. 刪除節點

def _delete(self, node):
	if node == None: return

	#* 計算該節點的子節點數量
	def number_of_children(node):
	    number = 0
	    if node.left != None: number += 1
	    if node.right != None: number +=1
	    return number
	

	def get_min_value(node):
	    current = node
	    while current.left != None:
	        current = current.left
	    return current

	parent = node.parent
	num_child = number_of_children(node)

	#TODO 沒有child，就刪除節點
	if num_child == 0:
	    if parent == None: # 代表 root
	        self.root = None
	    else:
	        if parent.left == node: # 確認節點的位置並從父節點刪除
	            parent.left = None
	        else:
	            parent.right = None
	    return

	#TODO 1個child，直接讓子節點篡位
	if num_child == 1:
	    child = node.left if node.left != None else node.right

	    if parent == None: # 刪除的節點如果為 root，子節點篡位
	        self.root = child
	    else:
	        if parent.left == node: # 確認被刪除節點的位置，子節點直接篡位
	            parent.left = child
	            child.parent = parent
	        else:
	            parent.right = child 
	            child.parent = parent   
	
	#TODO 2個child，獲取要刪除節點右節點的最小值或是左節點的最大值，並代替刪除的節點
	if num_child == 2:
	    successor = get_min_value(node.right)
	    node.value = successor.value # 篡位該節點
	    self._delete(successor) # 刪除該節點原本的位置

	# 節點刪除後，處理樹的平衡
	self._inspect_deletion(node.parent)

#### 2. 診斷被刪除節點的父節點左右兩子樹的高度

:::warning
node節點為被刪除節點的父節點
:::

1. 獲取左右子樹的高度
2. 比較兩者差距是否 > 1
3. 判斷左右兩子節點的高度，高度較高的進行變動
4. 執行平衡方法

def _inspect_deletion(self, node):
	
	#* 比較左右高度 > 1，則執行 
	#* 從node開始選擇較高的節點 t2，t2中較高的 t3
	if node == None: return

    #* 1. 獲取左右子樹的高度
	left = self._get_height(node.left)
	right = self._get_height(node.right)

    # 2. 比較兩者差距是否 > 1
	if abs(left - right) > 1:
        # 3. 判斷左右兩子節點的高度，高度較高的進行變動
	    t2 = self._get_taller_node(node)
	    t3 = self._get_taller_node(t2)
        # 4. 執行平衡方法，詳情見上
	    self._rebalance_node(node, t2, t3)

	#* 往上診斷
    self._inspect_deletion(node.parent)
    
def _get_taller_node(self, node):
    #* 比較左右子節點高度
    #* return高度較高的節點
    left = self._get_height(node.left)
    right = self._get_height(node.right)
    return node.left if left > right else node.right

#### 3. 執行平衡
執行平衡方法同插入新節點的方式，詳情如上

## 完整程式碼

class Node:
    def __init__(self, value=None) -> None:
        self.value = value
        self.left = None
        self.right = None
        self.parent = None # 節點的父節點
        self.height = 1 # 節點在樹中的高度


class Binary_search_tree:
    def __init__(self) -> None:
        self.root = None

    def insert(self,value):
        if self.root == None:
            self.root = Node(value)
        else:
            self._insert(value, self.root)
    def _insert(self, value, cur_node):
        #* 如果 insertValue < 當前節點，放左邊 
        if cur_node.value > value:
            if cur_node.left == None:
                cur_node.left = Node(value)
                cur_node.left.parent = cur_node
                self._inspect_insertion(cur_node.left)
            else:
                self._insert(value, cur_node.left)

        #* 如果 insertValue > 當前節點，放右邊 
        elif cur_node.value < value:
            if cur_node.right == None:
                cur_node.right = Node(value)
                cur_node.right.parent = cur_node
                self._inspect_insertion(cur_node.right)
            else:
                self._insert(value, cur_node.right)
        else:
            print('已存在節點')

    def delete(self, value):
        return self._delete(self.find(value))
    
    def _delete(self, node):
        if node == None: return

        #* 計算該節點的子節點數量
        def number_of_children(node):
            number = 0
            if node.left != None: number += 1
            if node.right != None: number +=1
            return number
        

        def get_min_value(node):
            current = node
            while current.left != None:
                current = current.left
            return current

        parent = node.parent
        num_child = number_of_children(node)

        #TODO 沒有child，就刪除節點
        if num_child == 0:
            if parent == None: # 代表 root
                self.root = None
            else:
                if parent.left == node: # 確認節點的位置並從父節點刪除
                    parent.left = None
                else:
                    parent.right = None
            return

        #TODO 1個child，直接讓子節點篡位
        if num_child == 1:
            child = node.left if node.left != None else node.right

            if parent == None: # 刪除的節點如果為 root，子節點篡位
                self.root = child
            else:
                if parent.left == node: # 確認被刪除節點的位置，子節點直接篡位
                    parent.left = child
                    child.parent = parent
                else:
                    parent.right = child 
                    child.parent = parent   
    
        #TODO 2個child，獲取要刪除節點右節點的最小值或是左節點的最大值，並代替刪除的節點
        if num_child == 2:
            successor = get_min_value(node.right)
            node.value = successor.value # 篡位該節點
            self._delete(successor) # 刪除該節點原本的位置

        # 節點刪除後，處理樹的平衡
        self._inspect_deletion(node.parent)
            
    

    def find(self, value):
        if self.root == None:
            print('不存在該節點')
            return None
        else:
            return self._find(value, self.root)

    def _find(self, value, cur_node):
        #* 思路: 返回相同值，沒有則遞迴查找
        if cur_node.value == value:
            return cur_node
        elif cur_node.value < value and cur_node.right != None:
            return self._find(value, cur_node.right)
        elif cur_node.value > value and cur_node.left != None:
            return self._find(value, cur_node.left)
        else:
            print(f'不存在該數值 {value}')
            return None


    def _inspect_insertion(self, cur_node, path=[]):
        #* 先計算出每個節點距離ROOT的高度
        #* 根據節點左右兩點的差值來判斷是否要啟動變動
        if cur_node.parent == None: return

        path = [cur_node] + path

        left_height = self._get_height(cur_node.parent.left)
        right_height = self._get_height(cur_node.parent.right)

        # 如果當前節點的父節點左右子點高度相差 > 1 則啟動變換
        if abs(left_height - right_height) > 1:
            # 準備要調整的三個節點
            path = [cur_node.parent] + path
            self._rebalance_node(path[0], path[1], path[2])
            return

        new_height = cur_node.height + 1
        # 父節點的高度一定比子高，如果有歪斜，則採最大的那個
        if new_height > cur_node.parent.height:
            cur_node.parent.height = new_height

        # 往上探查
        self._inspect_insertion(cur_node.parent, path)

    def _inspect_deletion(self, node):
        #* 獲取左右子樹的高度
        #* 比較左右高度 > 1，則執行 
        #* 從node開始選擇較高的節點 t2，t2中較高的 t3
        if node == None: return

        left = self._get_height(node.left)
        right = self._get_height(node.right)

        if abs(left - right) > 1:
            t2 = self._get_taller_node(node)
            t3 = self._get_taller_node(t2)
            self._rebalance_node(node, t2, t3)

        #* 往上診斷
        self._inspect_deletion(node.parent)


    def _rebalance_node(self, t1, t2, t3): # T1最上面 T3最下面
        #TODO LL | 右
        if t1.left == t2 and t2.left == t3:
            self._right_rotate(t1)
         #TODO RR | 左
        if t1.right == t2 and t2.right == t3:
            self._left_rotate(t1)
        #TODO LR | 先右再左
        if t1.left == t2 and t2.right == t3:
            self._left_rotate(t2)
            self._right_rotate(t1)
        #TODO RL | 先左再右
        if t1.right == t2 and t2.left == t3:
            self._right_rotate(t2)
            self._left_rotate(t1)


    def _right_rotate(self, t1):
        sub_root = t1.parent
        t2 = t1.left
        o = t2.right
        #* 交換
        t2.right = t1
        t1.parent = t2
        t1.left = o
        if o != None: o.parent = t1
        #* 設定 sub_root
        t2.parent = sub_root
        if sub_root == None: # 如果三者的上面是None那一定是Root
            self.root = t2
        else:
            if sub_root.left == t1:
                sub_root.left = t2
            else: 
                sub_root.right = t2
        #* 設定變換後的高度
        t1.height = self._get_height(self._get_taller_node(t1)) + 1
        t2.height = self._get_height(self._get_taller_node(t2)) + 1
    

    def _left_rotate(self, t1):
        sub_root = t1.parent
        t2 = t1.right
        o = t2.left
        #* 交換
        t2.left = t1
        t1.parent = t2
        t1.right = o
        if o != None: o.parent = t1
        #* 設定 sub_root
        t2.parent = sub_root
        if sub_root == None:
            self.root = t2
        else:
            if sub_root.left == t1: 
                sub_root.left = t2
            else: 
                sub_root.right = t2
        #* 設定變換後的高度 
        t1.height = self._get_height(self._get_taller_node(t1)) + 1
        t2.height = self._get_height(self._get_taller_node(t2)) + 1

        
    def _get_height(self, cur_node):
        return 0 if cur_node == None else cur_node.height

    def _get_taller_node(self, node):
        #* 判斷節點左右高度，並return高度較高的節點
        left = self._get_height(node.left)
        right = self._get_height(node.right)
        return node.left if left > right else node.right