二元堆積樹與 AVL 樹操作筆記

二元堆積樹（Heap）

基本定義與特性

• Heap（堆積） 是一種完全二元樹（Complete Binary Tree），分為 最大堆（Max-Heap） 和 最小堆（Min-Heap）：
  • 最大堆：每個節點的值都大於或等於其子節點的值，根節點是整棵樹中的最大值。
  • 最小堆：每個節點的值都小於或等於其子節點的值，根節點是整棵樹中的最小值。

常用操作與程式碼實現

插入操作（Insertion）

class MinHeap:
    def __init__(self):
        self.heap = []

    def insert(self, val):
        self.heap.append(val)  # 新值加入到堆的尾端
        self._heapify_up(len(self.heap) - 1)  # 向上調整

    def delete_min(self):
        if len(self.heap) > 1:
            self._swap(0, len(self.heap) - 1)  # 將根節點與最後一個節點交換
            min_value = self.heap.pop()  # 取出最小值
            self._heapify_down(0)  # 向下調整
        elif self.heap:
            min_value = self.heap.pop()
        else:
            min_value = None
        return min_value

    def _heapify_up(self, index):
        parent_index = (index - 1) // 2
        if index > 0 and self.heap[index] < self.heap[parent_index]:
            self._swap(index, parent_index)
            self._heapify_up(parent_index)

    def _heapify_down(self, index):
        left_index = 2 * index + 1
        right_index = 2 * index + 2
        smallest = index

        if left_index < len(self.heap) and self.heap[left_index] < self.heap[smallest]:
            smallest = left_index
        if right_index < len(self.heap) and self.heap[right_index] < self.heap[smallest]:
            smallest = right_index
        if smallest != index:
            self._swap(index, smallest)
            self._heapify_down(smallest)

    def _swap(self, i, j):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]

# 測試程式碼
min_heap = MinHeap()
min_heap.insert(5)
min_heap.insert(3)
min_heap.insert(8)
min_heap.insert(2)
print("Heap after insertion:", min_heap.heap)
print("Deleted min:", min_heap.delete_min())
print("Heap after deletion:", min_heap.heap)

刪除操作（Deletion）#####

刪除堆積中的最小值或最大值後，會進行「向下堆積調整（heapify-down）」來保持堆積特性。

適用場景

優先順序佇列、Heap Sort 排序演算法、圖演算法中的最短路徑問題（如 Dijkstra 演算法）。

AVL 樹

基本定義與特性

AVL 樹 是一種自平衡的二元搜尋樹（Binary Search Tree, BST），每個節點的左右子樹高度差（平衡因子）不超過 1。
平衡因子（Balance Factor, BF）：用來衡量每個節點的平衡狀態。計算公式：BF = Height(Left Subtree) - Height(Right Subtree)。

常用操作與程式碼實現

插入操作（Insertion）

class AVLTreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.height = 1

class AVLTree:
    def _get_height(self, node):
        if not node:
            return 0
        return node.height

    def _get_balance_factor(self, node):
        if not node:
            return 0
        return self._get_height(node.left) - self._get_height(node.right)

    def _left_rotate(self, z):
        y = z.right
        T2 = y.left

        # 左旋轉
        y.left = z
        z.right = T2

        # 更新高度
        z.height = 1 + max(self._get_height(z.left), self._get_height(z.right))
        y.height = 1 + max(self._get_height(y.left), self._get_height(y.right))
        return y

    def _right_rotate(self, z):
        y = z.left
        T3 = y.right

        # 右旋轉
        y.right = z
        z.left = T3

        # 更新高度
        z.height = 1 + max(self._get_height(z.left), self._get_height(z.right))
        y.height = 1 + max(self._get_height(y.left), self._get_height(y.right))
        return y

    def insert(self, root, key):
        # 1. 標準二元搜尋樹插入
        if not root:
            return AVLTreeNode(key)
        elif key < root.value:
            root.left = self.insert(root.left, key)
        else:
            root.right = self.insert(root.right, key)

        # 2. 更新高度
        root.height = 1 + max(self._get_height(root.left), self._get_height(root.right))

        # 3. 計算平衡因子
        balance_factor = self._get_balance_factor(root)

        # 4. 根據平衡因子調整
        # LL 旋轉
        if balance_factor > 1 and key < root.left.value:
            return self._right_rotate(root)
        # RR 旋轉
        if balance_factor < -1 and key > root.right.value:
            return self._left_rotate(root)
        # LR 旋轉
        if balance_factor > 1 and key > root.left.value:
            root.left = self._left_rotate(root.left)
            return self._right_rotate(root)
        # RL 旋轉
        if balance_factor < -1 and key < root.right.value:
            root.right = self._right_rotate(root.right)
            return self._left_rotate(root)
        return root

# 測試程式碼
avl = AVLTree()
root = None
elements = [10, 20, 30, 40, 50, 25]
for element in elements:
    root = avl.insert(root, element)

刪除操作（Deletion）

AVL 樹的刪除操作與標準二元搜尋樹相同，但刪除後可能需要進行旋轉操作來保持平衡。

適用場景

資料庫索引、符號表、搜尋引擎中的快速查找、編譯器中的變數與函數查找。