前端面試專欄-算法篇：22.樹結構（二叉樹、B樹、紅黑樹）

🔥 歡迎來到前端面試通關指南專欄！從js精講到框架到實戰，漸進系統化學習，堅持解鎖新技能，祝你輕松拿下心儀offer。
前端面試通關指南專欄主頁
前端面試專欄規劃詳情

樹結構（二叉樹、B樹、紅黑樹）

在計算機科學中，樹結構是一種非常重要的非線性數據結構，它能夠高效地組織和存儲數據。與線性數據結構如數組和鏈表相比，樹結構具有層級關系，更適用于表示具有父子關系的數據。樹結構廣泛應用于以下領域：

數據庫系統：用于索引實現（如B樹、B+樹）
文件系統：目錄結構組織
搜索引擎：網頁排名和索引
網絡路由：路由器表查找
人工智能：決策樹算法

二叉樹

二叉樹是最基本的樹結構之一，每個節點最多有兩個子節點，分別稱為左子節點和右子節點。二叉樹有以下幾種重要的變種：

完全二叉樹

除最后一層外，其他各層的節點數都達到最大值，且最后一層的節點都集中在左側。這種結構常用于堆的實現。

滿二叉樹

每一層的節點數都達到最大值。即如果樹的高度為h，則節點數為2^h-1。

二叉搜索樹(BST)

具有以下性質：

左子樹所有節點的值小于根節點的值
右子樹所有節點的值大于根節點的值
左右子樹也分別為二叉搜索樹

二叉搜索樹的平均時間復雜度：

查找：O(log n)
插入：O(log n)
刪除：O(log n)

但在最壞情況下（如插入有序數據時退化為鏈表），時間復雜度會降為O(n)。

B樹

B樹是一種平衡的多路搜索樹，主要應用于磁盤存儲系統。其特點包括：

節點結構：
- 每個節點最多包含m個子節點（m階B樹）
- 根節點至少有兩個子節點（除非它是葉子節點）
- 非根非葉子節點至少有?m/2?個子節點
操作特性：
- 所有葉子節點位于同一層次
- 插入操作可能導致節點分裂
- 刪除操作可能導致節點合并

典型應用場景：

數據庫索引（如MySQL的InnoDB存儲引擎使用B+樹）
文件系統（如NTFS、ReiserFS）

B樹與二叉搜索樹相比的優勢：

減少磁盤I/O次數（一個節點可以存儲多個鍵值）
更適合處理大規模數據
保持平衡的特性保證操作效率

紅黑樹

紅黑樹是一種自平衡的二叉搜索樹，具有以下性質：

節點著色規則：
- 每個節點是紅色或黑色
- 根節點是黑色
- 每個葉子節點（NIL節點）是黑色
- 紅色節點的子節點必須是黑色
- 從任一節點到其每個葉子節點的路徑包含相同數目的黑色節點
平衡特性：
- 最長路徑不超過最短路徑的兩倍
- 保證基本操作在最壞情況下的時間復雜度為O(log n)
- 通過旋轉（左旋/右旋）和重新著色維持平衡

紅黑樹的應用實例：

Java的TreeMap和TreeSet實現
C++ STL的map和set容器
Linux內核的進程調度
計算幾何中的區間樹

與其他平衡樹的比較：

與AVL樹相比，紅黑樹的平衡要求更寬松，插入/刪除操作需要的旋轉更少
與B樹相比，紅黑樹更適合內存中的數據結構實現

在實際系統設計中，選擇哪種樹結構取決于具體應用場景、數據規模和性能要求。理解這些樹結構的特點和實現原理，有助于開發高效、穩定的軟件系統。

一、二叉樹（Binary Tree）

1.1 基本概念

二叉樹是一種樹形數據結構，其特點是每個節點最多有兩個子節點，分別稱為左子節點和右子節點。二叉樹的定義具有遞歸性，即一個二叉樹要么為空，要么由一個根節點和兩棵互不相交的子二叉樹組成。這種遞歸特性使得二叉樹非常適合使用遞歸算法來處理。

二叉樹的基本術語：

根節點(Root)：位于樹頂端的節點，沒有父節點
葉子節點(Leaf)：沒有子節點的節點
內部節點：至少有一個子節點的節點
深度(Depth)：從根節點到該節點的路徑長度
高度(Height)：從該節點到葉子節點的最長路徑
度(Degree)：節點的子節點數目

二叉樹的幾種特殊形式：

滿二叉樹：每個節點要么有兩個子節點，要么沒有子節點。若高度為h，則節點總數為2^h-1
完全二叉樹：除了最后一層外，每一層都被完全填充，且最后一層的節點都盡可能靠左。常用于堆的實現
二叉搜索樹（BST）：對于每個節點，其左子樹的所有節點值小于該節點值，右子樹的所有節點值大于該節點值。這種特性使得查找、插入和刪除操作的平均時間復雜度為O(log n)

示例：

這是一個典型的二叉搜索樹示例，其中：

8是根節點
1、4、7、9、14是葉子節點
節點6的度為2，深度為2，高度為1
滿足BST特性：任意節點的左子樹節點值都小于它，右子樹節點值都大于它

二叉樹在計算機領域有廣泛應用：

文件系統目錄結構
數據庫索引(B樹、B+樹)
編譯器中的語法分析樹
游戲開發中的決策樹
網絡路由算法

1.2 二叉搜索樹（BST）的實現

以下是二叉搜索樹的Python實現，包含節點類和基本操作：

class Node:def __init__(self, key):self.key = keyself.left = Noneself.right = Noneclass BinarySearchTree:def __init__(self):self.root = Nonedef insert(self, key):"""插入新節點"""self.root = self._insert_recursive(self.root, key)def _insert_recursive(self, root, key):if root is None:return Node(key)if key < root.key:root.left = self._insert_recursive(root.left, key)else:root.right = self._insert_recursive(root.right, key)return rootdef search(self, key):"""查找節點"""return self._search_recursive(self.root, key)def _search_recursive(self, root, key):if root is None or root.key == key:return rootif key < root.key:return self._search_recursive(root.left, key)return self._search_recursive(root.right, key)def inorder_traversal(self):"""中序遍歷（升序輸出）"""result = []self._inorder_recursive(self.root, result)return resultdef _inorder_recursive(self, root, result):if root:self._inorder_recursive(root.left, result)result.append(root.key)self._inorder_recursive(root.right, result)def min_value_node(self, root):"""找到最小節點"""current = rootwhile current.left is not None:current = current.leftreturn currentdef delete(self, key):"""刪除節點"""self.root = self._delete_recursive(self.root, key)def _delete_recursive(self, root, key):if root is None:return rootif key < root.key:root.left = self._delete_recursive(root.left, key)elif key > root.key:root.right = self._delete_recursive(root.right, key)else:# 節點只有一個子節點或沒有子節點if root.left is None:return root.rightelif root.right is None:return root.left# 節點有兩個子節點，獲取右子樹的最小節點temp = self.min_value_node(root.right)root.key = temp.keyroot.right = self._delete_recursive(root.right, temp.key)return root# 使用示例
bst = BinarySearchTree()
bst.insert(50)
bst.insert(30)
bst.insert(20)
bst.insert(40)
bst.insert(70)
bst.insert(60)
bst.insert(80)print("中序遍歷結果:", bst.inorder_traversal())  # 輸出: [20, 30, 40, 50, 60, 70, 80]bst.delete(20)
print("刪除20后的中序遍歷:", bst.inorder_traversal())  # 輸出: [30, 40, 50, 60, 70, 80]bst.delete(50)
print("刪除50后的中序遍歷:", bst.inorder_traversal())  # 輸出: [30, 40, 60, 70, 80]

1.3 二叉樹的應用場景

文件系統目錄結構：
現代操作系統普遍采用樹形結構管理文件和目錄，其中每個目錄節點可以包含多個子目錄或文件。例如在Linux系統中，根目錄"/"作為樹的根節點，包含bin、etc、home等子目錄，這些子目錄又可以繼續包含更深層次的子目錄，形成一個典型的樹形層級結構。這種結構使得文件的查找和管理更加高效。
編譯器的語法樹：
在編譯器設計領域，抽象語法樹（AST）是源代碼語法結構的樹狀表示。編譯器前端將源代碼解析后，會生成一棵語法樹，其中每個節點代表一個語法構造。例如對于表達式"3*(4+5)"，編譯器會構建一棵二叉樹，其中"*“作為根節點，數字"3"和”+“作為子節點，”+"節點又包含"4"和"5"兩個子節點。這種樹形結構有助于編譯器進行語義分析和代碼優化。
數據庫索引：
數據庫系統廣泛使用B樹和B+樹作為索引結構，這些數據結構都是多路平衡樹的變種。例如MySQL的InnoDB存儲引擎就使用B+樹索引，樹的高度通常維持在3-4層，這使得即使在上億條記錄中也能快速定位數據。B+樹的所有數據都存儲在葉子節點，并且葉子節點之間通過指針連接，非常適合范圍查詢和磁盤I/O優化。
游戲AI：
在游戲人工智能中，決策樹和博弈樹發揮著重要作用。例如在國際象棋AI中，博弈樹用于評估可能的走法，每個節點代表一個棋盤狀態，分支代表可能的移動。通過Minimax算法和Alpha-Beta剪枝，AI可以高效地搜索最佳策略。決策樹也常用于NPC的行為決策，根據不同條件選擇不同行為分支。
數據壓縮：
霍夫曼編碼是一種經典的無損數據壓縮算法，它通過構建最優二叉樹來實現。頻率高的字符分配較短的編碼，頻率低的字符分配較長的編碼。例如在ZIP壓縮格式中，就使用了霍夫曼編碼的變種。構建霍夫曼樹的過程包括：統計字符頻率、構建優先隊列、合并節點直至形成完整二叉樹，最終生成每個字符的變長編碼。

二、B樹（B-Tree）

2.1 基本概念

B樹（Balance Tree）是一種自平衡的多路搜索樹，由Rudolf Bayer和Edward M. McCreight于1972年提出，常用于文件系統和數據庫索引。與普通的二叉樹不同，B樹的每個節點可以有多個子節點（稱為階數，通常用m表示），這使得B樹在存儲大量數據時能夠保持較小的樹高度，從而提高磁盤I/O效率。

B樹的特點：

多子節點結構：
- 每個內部節點（非根節點）至少有?m/2?個子節點，最多有m個子節點
- 例如，一個4階B樹（m=4）中，每個節點有2到4個子節點
鍵值存儲方式：
- 每個節點存儲k個鍵值（k-1 <= m-1），其中k值滿足?m/2?-1 <= k <= m-1
- 鍵值按升序排列，例如一個節點可能存儲[10, 20, 30]三個鍵值
平衡特性：
- 所有葉子節點都位于同一層，確保樹的絕對平衡
- 每次插入/刪除操作后都會自動進行平衡調整
搜索路徑：
- 對于節點中的鍵值K?, K?,…, K?：
  - 小于K?的鍵值在第一個子樹中
  - 介于K?和K???之間的鍵值在第i+1個子樹中
  - 大于K?的鍵值在最后一個子樹中
- 例如：查找25時，在[10,20,30]節點會進入20和30之間的子樹
實際應用：
- 數據庫系統（如MySQL的InnoDB引擎）
- 文件系統（如NTFS、ReiserFS）
- 需要大量磁盤讀寫的場景，因為B樹可以減少磁盤訪問次數

典型應用示例：在數據庫索引中，一個B樹節點的大小通常設置為磁盤塊大小（如4KB），這樣每次磁盤讀取可以獲取一個完整節點，極大提高了查詢效率。

2.2 B樹的結構與操作

2.2.1 B樹的基本結構

B樹是一種平衡的多路搜索樹，其階數(order)定義為每個節點最多可以擁有的子節點數。一個m階B樹需要滿足以下結構特性：

節點容量限制：
- 每個節點最多包含m-1個鍵值(key)和最多m個子節點指針
- 例如，一個5階B樹的節點最多可存儲4個鍵值，最多有5個子節點
節點填充要求：
- 除根節點外，每個非葉子節點至少有?m/2?-1個鍵值和?m/2?個子節點
- 例如5階B樹(?5/2?=3)的非根節點至少要有2個鍵值和3個子節點
根節點特例：
- 根節點至少要有1個鍵值
- 當不是葉子節點時，至少要有2個子節點
平衡性保證：
- 所有葉子節點都位于同一層級
- 樹的高度保持平衡，確保操作效率

2.2.2 B樹的核心操作

搜索操作：
- 從根節點開始，采用二分查找方式在當前節點查找目標鍵值
- 若找到則返回；否則根據鍵值大小選擇適當的子節點繼續查找
- 示例：在存儲學生成績的B樹中查找學號為2023005的記錄
插入操作：
- 步驟1：找到合適的葉子節點位置
- 步驟2：插入新鍵值，保持節點鍵值有序
- 步驟3：若節點超出容量(m-1個鍵值)，則進行節點分裂：
  - 將中間鍵值提升至父節點
  - 分裂剩余鍵值形成兩個新節點
  - 若導致父節點溢出，遞歸向上分裂
- 應用場景：數據庫索引添加新記錄時觸發的B樹調整
刪除操作：
- 情況1：刪除葉子節點鍵值
  - 直接刪除后檢查是否滿足最少鍵值要求
  - 若不滿足，考慮向兄弟節點借鍵值或與兄弟節點合并
- 情況2：刪除內部節點鍵值
  - 用前驅或后繼鍵值替換被刪鍵值
  - 遞歸處理前驅/后繼鍵值原來的位置
- 合并操作示例：當5階B樹節點鍵值少于2個時，會與相鄰節點合并
維護操作：
- 鍵值重新分配：在相鄰節點間移動鍵值以保持平衡
- 節點合并：將兩個不足的節點合并為一個合法節點
- 樹高調整：當根節點被合并時，樹的高度會降低

這些操作確保了B樹在動態增刪數據時始終保持平衡，為數據庫系統和文件系統提供了高效的索引結構。典型的應用包括MySQL的InnoDB存儲引擎、文件系統如NTFS、HFS+等。

2.3 B樹的應用場景

1. 數據庫索引

B樹及其變種（特別是B+樹）是關系型數據庫中最常用的索引結構。例如：

MySQL：InnoDB存儲引擎默認使用B+樹作為索引結構
Oracle：采用B樹索引作為主要索引類型
PostgreSQL：實現多種索引類型，其中B樹是最基本的形式
SQL Server：同樣大量使用B樹索引

典型應用場景：

處理范圍查詢（如WHERE age BETWEEN 20 AND 30）
支持ORDER BY排序操作
實現主鍵/唯一鍵約束

2. 文件系統

現代文件系統廣泛采用B樹結構來組織文件和目錄：

Ext4：Linux主流文件系統，使用B樹管理目錄項
NTFS：Windows NT文件系統采用B+樹存儲文件索引
ReiserFS：完全基于B*樹設計
HFS+：蘋果文件系統使用B樹存儲目錄

優勢體現：

快速定位文件（O(log n)時間復雜度）
支持大規模目錄（百萬級文件）
高效處理文件元數據操作

3. 高效存儲大量數據

B樹的平衡特性使其特別適合處理海量數據存儲：

磁盤讀寫優化：
- 典型節點大小設置為磁盤頁大小（如4KB）
- 一次I/O可讀取整個節點
- 樹高度通常保持3-4層（可存儲數十億記錄）
性能對比：

操作類型哈希表二叉搜索樹 B樹
查找 O(1) O(n) O(log n)
插入 O(1) O(n) O(log n)
范圍查詢不支持 O(n) O(log n + k)

操作類型	哈希表	二叉搜索樹	B樹
查找	O(1)	O(n)	O(log n)
插入	O(1)	O(n)	O(log n)
范圍查詢	不支持	O(n)	O(log n + k)

典型應用案例：

分布式存儲系統（如Google Bigtable）
時間序列數據庫（如InfluxDB）
鍵值存儲系統（如LevelDB）

三、紅黑樹（Red-Black Tree）

3.1 基本概念

紅黑樹（Red-Black Tree）是一種高效的自平衡二叉搜索樹，由 Rudolf Bayer 在1972年發明。它在普通二叉搜索樹的基礎上增加了顏色屬性（紅色或黑色）和一系列平衡規則，通過顏色約束和旋轉操作來維持樹的相對平衡。

紅黑樹的關鍵特性

顏色屬性：
- 每個節點存儲一個額外的顏色位（通常用1位表示）
- 顏色只能是紅色或黑色
- 新插入的節點默認設置為紅色（可以減少違反規則的情況）
結構規則：
- 根規則：根節點必須為黑色（確保從根節點出發的路徑都滿足黑節點數量要求）
- 葉子規則：所有NIL節點（空節點）被視為黑色（為計算黑高度提供統一的基準）
- 紅色約束：紅色節點的子節點必須為黑色（防止連續紅色節點導致路徑過長）
- 黑高度一致：從任意節點到其子樹中每個NIL節點的路徑必須包含相同數量的黑色節點（稱為該節點的黑高度）

平衡性保證

這些規則確保了紅黑樹的關鍵平衡特性：

最長路徑（紅黑交替）不超過最短路徑（全黑）的兩倍
樹的高度始終保持在O(log n)級別
查找、插入、刪除操作的時間復雜度穩定在O(log n)

應用場景示例

紅黑樹廣泛應用于需要高效查找和動態更新的場景：

Java的TreeMap和TreeSet實現
C++ STL中的map和set容器
Linux內核的進程調度（完全公平調度器使用紅黑樹管理進程）
文件系統的目錄結構管理
數據庫索引的實現

通過嚴格遵守這五條規則，紅黑樹在動態數據集合的管理中提供了優異的性能表現，成為工程實踐中最重要的平衡樹結構之一。

3.2 紅黑樹的操作

紅黑樹的基本操作（插入、刪除、搜索）與二叉搜索樹類似，但在插入和刪除后需要通過旋轉和重新著色來維持紅黑樹的性質。這些維護操作確保了紅黑樹始終保持良好的平衡性，使得其最壞情況下的時間復雜度仍為O(log n)。

旋轉操作

旋轉是紅黑樹維持平衡的關鍵操作，分為兩種基本類型：

左旋：

設當前節點為x，其右子節點為y
將y提升為新的子樹根節點
x成為y的左子節點
y原來的左子節點變為x的右子節點
示例：

    x              y/ \            / \a   y   →      x   c/ \        / \b   c      a   b

右旋：

設當前節點為x，其左子節點為y
將y提升為新的子樹根節點
x成為y的右子節點
y原來的右子節點變為x的左子節點
示例：

      x            y/ \          / \y   c  →     a   x/ \              / \a   b            b   c

插入操作

紅黑樹的插入過程分為兩個階段：

標準插入階段：
- 按照二叉搜索樹的規則找到合適的插入位置
- 創建新節點并初始化為紅色（保持性質5）
- 將新節點插入樹中
修復階段（可能需要遞歸處理）：
- 情況1：新節點是根節點 → 直接染黑
- 情況2：父節點是黑色 → 無需處理
- 情況3：父節點和叔節點都是紅色 → 重新著色
- 情況4：父節點紅色而叔節點黑色 → 需要旋轉
  - 左左或右右情況 → 單旋轉
  - 左右或右左情況 → 雙旋轉

刪除操作

刪除操作更為復雜，需要考慮多種情況：

標準刪除階段：
- 查找要刪除的節點
- 如果節點有兩個子節點，找到其前驅/后繼替換
- 實際刪除該節點（最多一個子節點的情況）
修復階段（當刪除黑色節點時）：
- 情況1：兄弟節點是紅色 → 旋轉并重新著色
- 情況2：兄弟節點是黑色且其子節點都是黑色 → 重新著色
- 情況3：兄弟節點是黑色且近侄子節點是紅色 → 旋轉并重新著色
- 情況4：兄弟節點是黑色且遠侄子節點是紅色 → 旋轉并重新著色

應用場景示例：

Java的TreeMap/TreeSet實現
Linux內核的進程調度
文件系統索引
數據庫索引結構

每次插入/刪除后，最多需要O(log n)次旋轉和重新著色操作即可恢復紅黑樹的性質。

3.3 紅黑樹的應用場景

紅黑樹作為一種自平衡的二叉查找樹，因其出色的性能特性（插入、刪除、查找的時間復雜度均為O(log n)）而被廣泛應用于多個領域：

Java集合框架
- TreeMap：基于紅黑樹實現的有序鍵值對集合，保持鍵的自然排序或自定義排序
- TreeSet：基于TreeMap實現的有序集合，常用于需要元素自動排序的場景
- 典型應用：實現有序字典、優先級隊列等數據結構
C++標準庫
- STL中的map：基于紅黑樹的有序關聯容器，提供高效的鍵值查找
- STL中的set：基于紅黑樹的有序集合容器
- 實現特點：保證元素有序的同時，提供O(log n)的查找性能
Linux內核
- 進程調度：用于管理進程描述符，實現高效的進程選擇
- 內存管理：組織虛擬內存區域(VMA)，快速查找內存區域
- 文件系統：ext3文件系統用于目錄項索引
- 優勢：在系統資源有限的環境下仍能保持穩定性能
高效的動態數據存儲
- 適用于需要頻繁執行以下操作的場景：
  - 動態插入數據（如實時日志處理）
  - 頻繁刪除數據（如緩存系統）
  - 高頻率查找（如數據庫索引）
- 對比優勢：相比AVL樹，紅黑樹的旋轉操作更少，適合寫操作頻繁的場景
- 實際應用示例：
  - 實時競價系統(RTB)中的廣告庫存管理
  - 游戲服務器中的玩家狀態管理
  - 金融系統中的實時報價處理
其他領域應用
- 網絡路由表：快速查找最優路由路徑
- 圖形處理：空間分區數據結構
- 編譯器實現：符號表管理

四、三種常見樹結構的特性對比

特性	二叉樹	B樹	紅黑樹
節點子樹數量	嚴格限制為最多2個子節點（左/右）	節點最多可包含m個子樹（m為B樹階數），典型數據庫實現中m=100-1000	與二叉樹相同，最多2個子節點，但通過顏色標記維持平衡
平衡性	無自動平衡機制，可能退化為鏈表	絕對平衡，通過節點分裂/合并保證所有葉子節點在同一層級	相對平衡，最長路徑長度不超過最短路徑的2倍
搜索效率	無序二叉樹最壞O(n)；有序二叉樹（如BST）平均O(log n)但可能退化	穩定O(log n)，因高度可控且節點存儲多個鍵	穩定O(log n)，平衡因子保證樹高度
插入/刪除效率	無序O(1)；有序BST平均O(log n)但最壞O(n)	穩定O(log n)，需要處理節點分裂/合并	穩定O(log n)，最多需要3次旋轉維護平衡
適用場景	表達式樹、哈夫曼編碼等簡單結構；遞歸算法教學	磁盤存儲系統（MySQL索引）、文件系統（NTFS、ReiserFS）	Java TreeMap/TreeSet、C++ STL map/set
空間開銷	每個節點僅需存儲2個指針（約16字節）	每個節點存儲m-1個鍵和m個指針，空間利用率通常保持在50%-100%	額外1位存儲顏色信息，整體空間與二叉樹相當
實現復雜度	簡單，基礎數據結構課程常見示例	中等，需處理多鍵節點和分裂合并邏輯	較高，需維護顏色屬性和旋轉規則
典型應用實例	編譯器語法分析樹、游戲決策樹	Oracle/MySQL的B+樹索引、MongoDB的B樹索引	Linux內核進程調度器、Epoll事件管理