)
《Hello 算法》AVL 樹全解析以旋轉對抗退化將增刪查改穩定維持在 O(log n)【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo導讀AVL 樹是資料結構與演算法課程中的經典內容也是《Hello 算法》「樹」章節中最具代表性的平衡二元搜尋樹balanced binary search tree。本文以 zh-hant/docs/chapter_tree/avl_tree.md 為主體骨架結合倉庫中 C 語言實現 與 Python 實現 的完整原始碼系統講解 AVL 樹的退化困境、節點高度與平衡因子、四種旋轉操作的原理與選擇條件以及插入、刪除、查詢的完整實現流程。讀完本文你將能獨立理解並寫出一個可運行、可驗證的自平衡二元搜尋樹。為什麼需要 AVL 樹二元搜尋樹的退化困境在「二元搜尋樹」章節中提到若持續在樹中執行插入與刪除操作樹的形態可能嚴重失衡。最極端的情況下二元搜尋樹會退化成鏈結串列——此時查詢、插入、刪除等操作的時間複雜度將從理想的 $O(\log n)$ 劣化為 $O(n)$。下圖展示了一棵二元搜尋樹在連續刪除節點後退化為鏈結串列的過程再看一個插入方向的例子在一棵完美二元樹中插入兩個節點後樹會嚴重向左傾斜查詢操作的時間複雜度隨之劣化為了解決這一問題1962 年 G. M. Adelson-Velsky 和 E. M. Landis 在論文 “An algorithm for the organization of information” 中提出了AVL 樹。其核心思想是透過一系列「旋轉」操作保證樹在持續新增與刪除節點後不會退化從而使各項操作的時間複雜度始終保持在 $O(\log n)$ 級別。在需要頻繁進行增刪查改的場景中AVL 樹能始終保持高效的資料操作效能。AVL 樹的常見術語AVL 樹既是二元搜尋樹也是平衡二元樹同時滿足這兩類樹的全部性質因此它本質上就是一種平衡二元搜尋樹。節點高度AVL 樹的所有相關操作都需要獲取節點高度因此節點類別中需要新增一個height變數。倉庫中 Python 版節點定義 如下class TreeNode: 二叉树节点类 def __init__(self, val: int 0): self.val: int val # 节点值 self.height: int 0 # 节点高度 self.left: TreeNode | None None # 左子节点引用 self.right: TreeNode | None None # 右子节点引用在 C 語言的工具標頭檔 中節點同樣攜帶height欄位並提供newTreeNode建構子完成記憶體分配與初始化。需要特別注意的是「節點高度」的定義它指的是從該節點到其最遠葉節點的距離即所經過的「邊」的數量。其中葉節點的高度為 $0$空節點的高度為 $-1$。基於此定義獲取與更新節點高度的工具函式如下摘自 avl_tree.pydef height(self, node: TreeNode | None) - int: 获取节点高度 # 空节点高度为 -1 叶节点高度为 0 if node is not None: return node.height return -1 def update_height(self, node: TreeNode | None): 更新节点高度 # 节点高度等于最高子树高度 1 node.height max([self.height(node.left), self.height(node.right)]) 1從 C 實現avl_tree.c可以看出height()對空指標返回-1而updateHeight()取左右子樹高度的較大者再加一。之所以將空節點高度定為 $-1$正是為了讓葉節點左右皆空的高度正確計算為 $\max(-1, -1) 1 0$。節點平衡因子節點的平衡因子balance factor定義為左子樹高度減去右子樹高度並規定空節點的平衡因子為 $0$def balance_factor(self, node: TreeNode | None) - int: 获取平衡因子 # 空节点平衡因子为 0 if node is None: return 0 # 节点平衡因子 左子树高度 - 右子树高度 return self.height(node.left) - self.height(node.right)若設平衡因子為 $f$則一棵 AVL 樹的任意節點皆滿足 $-1 \le f \le 1$。一旦某個節點的平衡因子絕對值超過 $1$就稱該節點為「失衡節點」需要透過旋轉使其恢復平衡。AVL 樹的旋轉操作旋轉是 AVL 樹的靈魂。它能在不影響二元樹中序走訪序列的前提下使失衡節點重新恢復平衡——換句話說旋轉既能保持「二元搜尋樹」的排序性質也能使樹重新變為「平衡二元樹」。根據失衡情況的不同旋轉分為四種右旋、左旋、先左旋後右旋、先右旋後左旋。右旋Right Rotation從底至頂觀察二元樹找到首個失衡節點並記為node其左子節點記為child。右旋操作以child為旋轉原點將node向右旋轉使child提升為子樹的新根def right_rotate(self, node: TreeNode | None) - TreeNode | None: 右旋操作 child node.left grand_child child.right # 以 child 为原点将 node 向右旋转 child.right node node.left grand_child # 更新节点高度 self.update_height(node) self.update_height(child) # 返回旋转后子树的根节点 return child當child本身帶有右子節點記為grand_child時需要在右旋中加入關鍵一步將grand_child掛接為node的左子節點以維持二元搜尋樹的排序性質左旋Left Rotation左旋是右旋的「映象」操作適用於鏡像對稱的失衡情況。以child node.right為原點將node向左旋轉當child帶有左子節點grand_child時需要將grand_child掛接為node的右子節點def left_rotate(self, node: TreeNode | None) - TreeNode | None: 左旋操作 child node.right grand_child child.left # 以 child 为原点将 node 向左旋转 child.left node node.right grand_child # 更新节点高度 self.update_height(node) self.update_height(child) # 返回旋转后子树的根节点 return child右旋與左旋在邏輯上完全鏡像對稱將右旋程式碼中的所有left與right互換即可得到左旋實現。兩種旋轉各自解決的失衡情況也同樣對稱。先左旋後右旋Left-Right Rotation某些失衡形態無法靠單次左旋或右旋解決。例如當失衡節點node的左子樹偏右傾斜時需要先對child執行左旋將其轉化為左偏形態再對node執行右旋子樹才能恢復平衡先右旋後左旋Right-Left Rotation同理對於上述情形的鏡像需要先對child執行右旋再對node執行左旋旋轉的選擇條件四種失衡情況與四種旋轉一一對應。判斷方法很直接觀察失衡節點的平衡因子再觀察其較高一側子節點的平衡因子正負號。失衡節點的平衡因子子節點的平衡因子應採用的旋轉方法$ 1$左偏樹$\geq 0$右旋$ 1$左偏樹$ 0$先左旋後右旋$ -1$右偏樹$\leq 0$左旋$ -1$右偏樹$ 0$先右旋後左旋為了便於使用倉庫將四種情況統一封裝為rotate()方法avl_tree.pydef rotate(self, node: TreeNode | None) - TreeNode | None: 执行旋转操作使该子树重新恢复平衡 # 获取节点 node 的平衡因子 balance_factor self.balance_factor(node) # 左偏树 if balance_factor 1: if self.balance_factor(node.left) 0: # 右旋 return self.right_rotate(node) else: # 先左旋后右旋 node.left self.left_rotate(node.left) return self.right_rotate(node) # 右偏树 elif balance_factor -1: if self.balance_factor(node.right) 0: # 左旋 return self.left_rotate(node) else: # 先右旋后左旋 node.right self.right_rotate(node.right) return self.left_rotate(node) # 平衡树无须旋转直接返回 return node對照 C 語言版rotate可以確認兩種語言的判斷邏輯完全一致先看失衡節點本身是左偏$bf 1$還是右偏$bf -1$再看子節點的平衡因子符號從而精準選擇單旋或雙旋。有了這個統一的入口後續的插入與刪除就只需要在每個節點上呼叫rotate()即可。AVL 樹的常用操作插入節點AVL 樹的插入與二元搜尋樹主體流程相同先依大小關係遞迴尋找插入位置。唯一的區別在於插入新節點後從該節點到根節點的路徑上可能出現一系列失衡節點因此需要在遞迴回溯的過程中自底向上更新高度並執行旋轉avl_tree.pydef insert(self, val): 插入节点 self._root self.insert_helper(self._root, val) def insert_helper(self, node: TreeNode | None, val: int) - TreeNode: 递归插入节点辅助方法 if node is None: return TreeNode(val) # 1. 查找插入位置并插入节点 if val node.val: node.left self.insert_helper(node.left, val) elif val node.val: node.right self.insert_helper(node.right, val) else: # 重复节点不插入直接返回 return node # 更新节点高度 self.update_height(node) # 2. 执行旋转操作使该子树重新恢复平衡 return self.rotate(node)值得注意的細節重複節點不插入直接返回這保證了 AVL 樹中不會出現重複值而每次遞迴返回前先update_height再rotate確保父節點能基於最新的子樹高度做正確的平衡判斷。刪除節點刪除操作同樣在二元搜尋樹刪除邏輯的基礎上於遞迴回溯時自底向上執行旋轉avl_tree.pydef remove(self, val: int): 删除节点 self._root self.remove_helper(self._root, val) def remove_helper(self, node: TreeNode | None, val: int) - TreeNode | None: 递归删除节点辅助方法 if node is None: return None # 1. 查找节点并删除 if val node.val: node.left self.remove_helper(node.left, val) elif val node.val: node.right self.remove_helper(node.right, val) else: if node.left is None or node.right is None: child node.left or node.right # 子节点数量 0 直接删除 node 并返回 if child is None: return None # 子节点数量 1 直接删除 node else: node child else: # 子节点数量 2 则将中序遍历的下个节点删除并用该节点替换当前节点 temp node.right while temp.left is not None: temp temp.left node.right self.remove_helper(node.right, temp.val) node.val temp.val # 更新节点高度 self.update_height(node) # 2. 执行旋转操作使该子树重新恢复平衡 return self.rotate(node)刪除邏輯需要處理三種子節點情況子節點數量為 $0$直接返回None完成刪除子節點數量為 $1$用唯一的子節點頂替被刪除節點子節點數量為 $2$找到中序走訪的下一個節點即右子樹中最左節點先遞迴刪除該節點再將其值賦給當前節點避免破壞二元搜尋樹的排序性質。在 C 語言實現 中因引入了stdio.h刪除函式被命名為removeItem以避免與標準庫的remove衝突——這是閱讀 C 版本時值得注意的細節。此外 C 版需要手動處理記憶體透過 tree_node.h 中的freeMemoryTree遞迴釋放整棵樹。查詢節點AVL 樹的查詢與普通二元搜尋樹完全一致沿根節點向下二分比較即可無需任何旋轉avl_tree.pydef search(self, val: int) - TreeNode | None: 查找节点 cur self._root # 循环查找越过叶节点后跳出 while cur is not None: # 目标节点在 cur 的右子树中 if cur.val val: cur cur.right # 目标节点在 cur 的左子树中 elif cur.val val: cur cur.left # 找到目标节点跳出循环 else: break # 返回目标节点 return cur動手驗證運行倉庫中的 AVL 樹示例倉庫中每種語言的avl_tree檔案都附帶可直接運行的 Driver Code用於觀察插入、刪除後 AVL 樹如何保持平衡。以 Python 為例avl_tree.py在codes/python目錄下執行python3 chapter_tree/avl_tree.pyDriver 的測試序列設計非常有針對性連續插入遞增序列1, 2, 3, 4, 5, 8, 7, 9, 10, 6若不加平衡這組數據足以讓二元搜尋樹嚴重退化而 AVL 樹在每次插入後都會印出樹形可直觀看到旋轉如何即時修正失衡插入重複節點7驗證「重複值不插入」的行為刪除三種度數的節點remove(8)刪除度為 $0$ 的節點、remove(5)刪除度為 $1$ 的節點、remove(4)刪除度為 $2$ 的節點覆蓋刪除邏輯的全部分支查詢節點7驗證查詢返回正確的節點物件。C 語言版本avl_tree.c的測試流程與 Python 版一致可透過 chapter_tree 的 CMakeLists.txt 中的add_executable(avl_tree avl_tree.c)編譯後運行。複雜度分析由於 AVL 樹保證任意節點平衡因子的絕對值不超過 $1$樹的高度被嚴格限制在 $O(\log n)$ 量級因此查詢、插入、刪除的時間複雜度均為 $O(\log n)$插入與刪除在回溯路徑上至多觸發 $O(\log n)$ 次高度更新與旋轉操作每次旋轉僅修改常數個指標整體開銷仍為 $O(\log n)$相比普通二元搜尋樹在極端情況下退化為 $O(n)$AVL 樹以「每次寫入操作多做一次平衡檢查與旋轉」的代價換取了所有操作穩定高效的效能保障。AVL 樹的典型應用組織與儲存大型資料適合高頻查詢、低頻增刪的場景能將查詢效能穩定維持在 $O(\log n)$構建資料庫索引系統AVL 樹嚴格平衡的特性使其適合對讀取延遲敏感的索引結構作為其他平衡樹的對比基準紅黑樹也是一種常見的平衡二元搜尋樹。相較於 AVL 樹紅黑樹的平衡條件更寬鬆插入與刪除節點所需的旋轉次數更少因而節點增刪的平均效率更高但 AVL 樹更嚴格的高度限制使其在純查詢場景下通常擁有更好的最壞情況保證。實際選型時可根據讀寫比例在兩者之間權衡。小結AVL 樹的核心價值在於以「節點高度」為度量、以「平衡因子」為判據、以「四種旋轉」為手段在保持二元搜尋樹排序性質不變的前提下把樹的高度嚴格控制在 $O(\log n)$。本文結合《Hello 算法》章節文檔與倉庫中 Python、C 的完整實現覆蓋了從退化問題、節點定義、高度與平衡因子到四種旋轉、插入、刪除、查詢與典型應用的全鏈路知識。讀者可在codes/目錄下找到包括 C、Java、Go、Rust、TypeScript 等在內的 14 種語言版本逐一對照閱讀即可徹底掌握 AVL 樹的實現細節。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 《Hello 算法》AVL 樹全解析：以旋轉對抗退化，將增刪查改穩定維持在 O(log n)
《Hello 算法》AVL 樹全解析以旋轉對抗退化將增刪查改穩定維持在 O(log n)【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo導讀AVL 樹是資料結構與演算法課程中的經典內容也是《Hello 算法》「樹」章節中最具代表性的平衡二元搜尋樹balanced binary search tree。本文以 zh-hant/docs/chapter_tree/avl_tree.md 為主體骨架結合倉庫中 C 語言實現 與 Python 實現 的完整原始碼系統講解 AVL 樹的退化困境、節點高度與平衡因子、四種旋轉操作的原理與選擇條件以及插入、刪除、查詢的完整實現流程。讀完本文你將能獨立理解並寫出一個可運行、可驗證的自平衡二元搜尋樹。為什麼需要 AVL 樹二元搜尋樹的退化困境在「二元搜尋樹」章節中提到若持續在樹中執行插入與刪除操作樹的形態可能嚴重失衡。最極端的情況下二元搜尋樹會退化成鏈結串列——此時查詢、插入、刪除等操作的時間複雜度將從理想的 $O(\log n)$ 劣化為 $O(n)$。下圖展示了一棵二元搜尋樹在連續刪除節點後退化為鏈結串列的過程再看一個插入方向的例子在一棵完美二元樹中插入兩個節點後樹會嚴重向左傾斜查詢操作的時間複雜度隨之劣化為了解決這一問題1962 年 G. M. Adelson-Velsky 和 E. M. Landis 在論文 “An algorithm for the organization of information” 中提出了AVL 樹。其核心思想是透過一系列「旋轉」操作保證樹在持續新增與刪除節點後不會退化從而使各項操作的時間複雜度始終保持在 $O(\log n)$ 級別。在需要頻繁進行增刪查改的場景中AVL 樹能始終保持高效的資料操作效能。AVL 樹的常見術語AVL 樹既是二元搜尋樹也是平衡二元樹同時滿足這兩類樹的全部性質因此它本質上就是一種平衡二元搜尋樹。節點高度AVL 樹的所有相關操作都需要獲取節點高度因此節點類別中需要新增一個height變數。倉庫中 Python 版節點定義 如下class TreeNode: 二叉树节点类 def __init__(self, val: int 0): self.val: int val # 节点值 self.height: int 0 # 节点高度 self.left: TreeNode | None None # 左子节点引用 self.right: TreeNode | None None # 右子节点引用在 C 語言的工具標頭檔 中節點同樣攜帶height欄位並提供newTreeNode建構子完成記憶體分配與初始化。需要特別注意的是「節點高度」的定義它指的是從該節點到其最遠葉節點的距離即所經過的「邊」的數量。其中葉節點的高度為 $0$空節點的高度為 $-1$。基於此定義獲取與更新節點高度的工具函式如下摘自 avl_tree.pydef height(self, node: TreeNode | None) - int: 获取节点高度 # 空节点高度为 -1 叶节点高度为 0 if node is not None: return node.height return -1 def update_height(self, node: TreeNode | None): 更新节点高度 # 节点高度等于最高子树高度 1 node.height max([self.height(node.left), self.height(node.right)]) 1從 C 實現avl_tree.c可以看出height()對空指標返回-1而updateHeight()取左右子樹高度的較大者再加一。之所以將空節點高度定為 $-1$正是為了讓葉節點左右皆空的高度正確計算為 $\max(-1, -1) 1 0$。節點平衡因子節點的平衡因子balance factor定義為左子樹高度減去右子樹高度並規定空節點的平衡因子為 $0$def balance_factor(self, node: TreeNode | None) - int: 获取平衡因子 # 空节点平衡因子为 0 if node is None: return 0 # 节点平衡因子 左子树高度 - 右子树高度 return self.height(node.left) - self.height(node.right)若設平衡因子為 $f$則一棵 AVL 樹的任意節點皆滿足 $-1 \le f \le 1$。一旦某個節點的平衡因子絕對值超過 $1$就稱該節點為「失衡節點」需要透過旋轉使其恢復平衡。AVL 樹的旋轉操作旋轉是 AVL 樹的靈魂。它能在不影響二元樹中序走訪序列的前提下使失衡節點重新恢復平衡——換句話說旋轉既能保持「二元搜尋樹」的排序性質也能使樹重新變為「平衡二元樹」。根據失衡情況的不同旋轉分為四種右旋、左旋、先左旋後右旋、先右旋後左旋。右旋Right Rotation從底至頂觀察二元樹找到首個失衡節點並記為node其左子節點記為child。右旋操作以child為旋轉原點將node向右旋轉使child提升為子樹的新根def right_rotate(self, node: TreeNode | None) - TreeNode | None: 右旋操作 child node.left grand_child child.right # 以 child 为原点将 node 向右旋转 child.right node node.left grand_child # 更新节点高度 self.update_height(node) self.update_height(child) # 返回旋转后子树的根节点 return child當child本身帶有右子節點記為grand_child時需要在右旋中加入關鍵一步將grand_child掛接為node的左子節點以維持二元搜尋樹的排序性質左旋Left Rotation左旋是右旋的「映象」操作適用於鏡像對稱的失衡情況。以child node.right為原點將node向左旋轉當child帶有左子節點grand_child時需要將grand_child掛接為node的右子節點def left_rotate(self, node: TreeNode | None) - TreeNode | None: 左旋操作 child node.right grand_child child.left # 以 child 为原点将 node 向左旋转 child.left node node.right grand_child # 更新节点高度 self.update_height(node) self.update_height(child) # 返回旋转后子树的根节点 return child右旋與左旋在邏輯上完全鏡像對稱將右旋程式碼中的所有left與right互換即可得到左旋實現。兩種旋轉各自解決的失衡情況也同樣對稱。先左旋後右旋Left-Right Rotation某些失衡形態無法靠單次左旋或右旋解決。例如當失衡節點node的左子樹偏右傾斜時需要先對child執行左旋將其轉化為左偏形態再對node執行右旋子樹才能恢復平衡先右旋後左旋Right-Left Rotation同理對於上述情形的鏡像需要先對child執行右旋再對node執行左旋旋轉的選擇條件四種失衡情況與四種旋轉一一對應。判斷方法很直接觀察失衡節點的平衡因子再觀察其較高一側子節點的平衡因子正負號。失衡節點的平衡因子子節點的平衡因子應採用的旋轉方法$ 1$左偏樹$\geq 0$右旋$ 1$左偏樹$ 0$先左旋後右旋$ -1$右偏樹$\leq 0$左旋$ -1$右偏樹$ 0$先右旋後左旋為了便於使用倉庫將四種情況統一封裝為rotate()方法avl_tree.pydef rotate(self, node: TreeNode | None) - TreeNode | None: 执行旋转操作使该子树重新恢复平衡 # 获取节点 node 的平衡因子 balance_factor self.balance_factor(node) # 左偏树 if balance_factor 1: if self.balance_factor(node.left) 0: # 右旋 return self.right_rotate(node) else: # 先左旋后右旋 node.left self.left_rotate(node.left) return self.right_rotate(node) # 右偏树 elif balance_factor -1: if self.balance_factor(node.right) 0: # 左旋 return self.left_rotate(node) else: # 先右旋后左旋 node.right self.right_rotate(node.right) return self.left_rotate(node) # 平衡树无须旋转直接返回 return node對照 C 語言版rotate可以確認兩種語言的判斷邏輯完全一致先看失衡節點本身是左偏$bf 1$還是右偏$bf -1$再看子節點的平衡因子符號從而精準選擇單旋或雙旋。有了這個統一的入口後續的插入與刪除就只需要在每個節點上呼叫rotate()即可。AVL 樹的常用操作插入節點AVL 樹的插入與二元搜尋樹主體流程相同先依大小關係遞迴尋找插入位置。唯一的區別在於插入新節點後從該節點到根節點的路徑上可能出現一系列失衡節點因此需要在遞迴回溯的過程中自底向上更新高度並執行旋轉avl_tree.pydef insert(self, val): 插入节点 self._root self.insert_helper(self._root, val) def insert_helper(self, node: TreeNode | None, val: int) - TreeNode: 递归插入节点辅助方法 if node is None: return TreeNode(val) # 1. 查找插入位置并插入节点 if val node.val: node.left self.insert_helper(node.left, val) elif val node.val: node.right self.insert_helper(node.right, val) else: # 重复节点不插入直接返回 return node # 更新节点高度 self.update_height(node) # 2. 执行旋转操作使该子树重新恢复平衡 return self.rotate(node)值得注意的細節重複節點不插入直接返回這保證了 AVL 樹中不會出現重複值而每次遞迴返回前先update_height再rotate確保父節點能基於最新的子樹高度做正確的平衡判斷。刪除節點刪除操作同樣在二元搜尋樹刪除邏輯的基礎上於遞迴回溯時自底向上執行旋轉avl_tree.pydef remove(self, val: int): 删除节点 self._root self.remove_helper(self._root, val) def remove_helper(self, node: TreeNode | None, val: int) - TreeNode | None: 递归删除节点辅助方法 if node is None: return None # 1. 查找节点并删除 if val node.val: node.left self.remove_helper(node.left, val) elif val node.val: node.right self.remove_helper(node.right, val) else: if node.left is None or node.right is None: child node.left or node.right # 子节点数量 0 直接删除 node 并返回 if child is None: return None # 子节点数量 1 直接删除 node else: node child else: # 子节点数量 2 则将中序遍历的下个节点删除并用该节点替换当前节点 temp node.right while temp.left is not None: temp temp.left node.right self.remove_helper(node.right, temp.val) node.val temp.val # 更新节点高度 self.update_height(node) # 2. 执行旋转操作使该子树重新恢复平衡 return self.rotate(node)刪除邏輯需要處理三種子節點情況子節點數量為 $0$直接返回None完成刪除子節點數量為 $1$用唯一的子節點頂替被刪除節點子節點數量為 $2$找到中序走訪的下一個節點即右子樹中最左節點先遞迴刪除該節點再將其值賦給當前節點避免破壞二元搜尋樹的排序性質。在 C 語言實現 中因引入了stdio.h刪除函式被命名為removeItem以避免與標準庫的remove衝突——這是閱讀 C 版本時值得注意的細節。此外 C 版需要手動處理記憶體透過 tree_node.h 中的freeMemoryTree遞迴釋放整棵樹。查詢節點AVL 樹的查詢與普通二元搜尋樹完全一致沿根節點向下二分比較即可無需任何旋轉avl_tree.pydef search(self, val: int) - TreeNode | None: 查找节点 cur self._root # 循环查找越过叶节点后跳出 while cur is not None: # 目标节点在 cur 的右子树中 if cur.val val: cur cur.right # 目标节点在 cur 的左子树中 elif cur.val val: cur cur.left # 找到目标节点跳出循环 else: break # 返回目标节点 return cur動手驗證運行倉庫中的 AVL 樹示例倉庫中每種語言的avl_tree檔案都附帶可直接運行的 Driver Code用於觀察插入、刪除後 AVL 樹如何保持平衡。以 Python 為例avl_tree.py在codes/python目錄下執行python3 chapter_tree/avl_tree.pyDriver 的測試序列設計非常有針對性連續插入遞增序列1, 2, 3, 4, 5, 8, 7, 9, 10, 6若不加平衡這組數據足以讓二元搜尋樹嚴重退化而 AVL 樹在每次插入後都會印出樹形可直觀看到旋轉如何即時修正失衡插入重複節點7驗證「重複值不插入」的行為刪除三種度數的節點remove(8)刪除度為 $0$ 的節點、remove(5)刪除度為 $1$ 的節點、remove(4)刪除度為 $2$ 的節點覆蓋刪除邏輯的全部分支查詢節點7驗證查詢返回正確的節點物件。C 語言版本avl_tree.c的測試流程與 Python 版一致可透過 chapter_tree 的 CMakeLists.txt 中的add_executable(avl_tree avl_tree.c)編譯後運行。複雜度分析由於 AVL 樹保證任意節點平衡因子的絕對值不超過 $1$樹的高度被嚴格限制在 $O(\log n)$ 量級因此查詢、插入、刪除的時間複雜度均為 $O(\log n)$插入與刪除在回溯路徑上至多觸發 $O(\log n)$ 次高度更新與旋轉操作每次旋轉僅修改常數個指標整體開銷仍為 $O(\log n)$相比普通二元搜尋樹在極端情況下退化為 $O(n)$AVL 樹以「每次寫入操作多做一次平衡檢查與旋轉」的代價換取了所有操作穩定高效的效能保障。AVL 樹的典型應用組織與儲存大型資料適合高頻查詢、低頻增刪的場景能將查詢效能穩定維持在 $O(\log n)$構建資料庫索引系統AVL 樹嚴格平衡的特性使其適合對讀取延遲敏感的索引結構作為其他平衡樹的對比基準紅黑樹也是一種常見的平衡二元搜尋樹。相較於 AVL 樹紅黑樹的平衡條件更寬鬆插入與刪除節點所需的旋轉次數更少因而節點增刪的平均效率更高但 AVL 樹更嚴格的高度限制使其在純查詢場景下通常擁有更好的最壞情況保證。實際選型時可根據讀寫比例在兩者之間權衡。小結AVL 樹的核心價值在於以「節點高度」為度量、以「平衡因子」為判據、以「四種旋轉」為手段在保持二元搜尋樹排序性質不變的前提下把樹的高度嚴格控制在 $O(\log n)$。本文結合《Hello 算法》章節文檔與倉庫中 Python、C 的完整實現覆蓋了從退化問題、節點定義、高度與平衡因子到四種旋轉、插入、刪除、查詢與典型應用的全鏈路知識。讀者可在codes/目錄下找到包括 C、Java、Go、Rust、TypeScript 等在內的 14 種語言版本逐一對照閱讀即可徹底掌握 AVL 樹的實現細節。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考