第14章平衡树理论

本章导读

平衡树是保证操作复杂度为 $O(\log n)$ 的自平衡二叉搜索树。本章从形式化角度深入分析平衡树的数学基础，包括AVL树的高度平衡性质与旋转正确性证明、红黑树的红黑性质与高度上界证明，以及两种平衡树的性能对比分析。

学习目标

完成本章学习后，读者将能够：

掌握平衡树的数学定义与平衡条件
理解AVL树旋转操作的正确性证明
掌握红黑树高度上界的数学推导
理解红黑树插入修复的正确性
掌握平衡树的选择标准与应用场景

14.1 平衡树的形式化定义

14.1.1 平衡性的数学定义

定义 14.1（平衡因子） 节点 $v$ 的平衡因子定义为：

$$BF(v) = h(left(v)) - h(right(v))$$

其中 $h(v)$ 表示节点 $v$ 的高度。

定义 14.2（高度平衡） 二叉树 $T$ 是高度平衡的，当且仅当：

$$\forall v \in T: |BF(v)| \leq 1$$

定义 14.3（平衡二叉搜索树） 平衡二叉搜索树是同时满足BST性质和平衡性质的二叉搜索树。

定理 14.1（平衡树高度上界） $n$ 个节点的平衡二叉搜索树的高度 $h$ 满足：

$$h = O(\log n)$$

证明：设 $N_h$ 为高度为 $h$ 的平衡二叉搜索树的最少节点数。

高度为 $h$ 的平衡树由根节点和两棵子树组成，其中一棵高度为 $h-1$，另一棵高度至少为 $h-2$（由平衡条件）。

因此：

$$N_h = 1 + N_{h-1} + N_{h-2}$$

这与斐波那契数列的递推关系相同。解得：

$$N_h \geq \phi^h$$

其中 $\phi = \frac{1+\sqrt{5}}{2}$ 是黄金比例。

因此 $h \leq \log_\phi n = O(\log n)$。∎

14.1.2 平衡树ADT

ADT 14.1（BalancedBST）

ADT BalancedBST[K: Ordered]
  Types: BalancedBST[K]
  
  Operations:
    所有BST操作
    rebalance: BalancedBST[K] → BalancedBST[K]
  
  Axioms:
    所有BST公理
    (A1) rebalance后树满足平衡条件
    (A2) rebalance后中序遍历不变

14.2 AVL树理论

14.2.1 AVL树的数学定义

定义 14.4（AVL树） AVL树是满足以下性质的二叉搜索树：

$$\forall v \in T: |BF(v)| \leq 1$$

定理 14.2（AVL树高度上界） $n$ 个节点的AVL树的高度 $h$ 满足：

$$h < 1.44 \log_2(n+2) - 0.328$$

证明：设 $N_h$ 为高度为 $h$ 的AVL树的最少节点数。

$$N_h = N_{h-1} + N_{h-2} + 1$$

边界条件：$N_0 = 1$，$N_1 = 2$。

解此递推关系，设 $N_h = \alpha \phi^h + \beta \hat{\phi}^h - 1$，其中 $\phi = \frac{1+\sqrt{5}}{2}$，$\hat{\phi} = \frac{1-\sqrt{5}}{2}$。

由于 $|\hat{\phi}| < 1$，当 $h$ 足够大时：

$$N_h \approx \alpha \phi^h$$

因此 $h \approx \log_\phi N_h = \frac{\ln N_h}{\ln \phi} \approx 1.44 \log_2 n$。∎

14.2.2 旋转操作的正确性

定义 14.5（右旋） 对节点 $y$ 进行右旋：

    y                x
   / \              / \
  x   T3    →     T1   y
 / \                  / \
T1  T2              T2  T3

定理 14.3（旋转保持BST性质） 旋转操作保持BST性质。

证明：右旋前，$x < y$，$T1 < x < T2 < y < T3$。

右旋后：

$T1$ 在 $x$ 的左子树，满足 $T1 < x$
$T2$ 在 $y$ 的左子树，满足 $T2 < y$
$T3$ 在 $y$ 的右子树，满足 $y < T3$
$x < y$（$x$ 是 $y$ 的父节点）

因此BST性质保持。左旋类似。∎

定理 14.4（旋转保持中序遍历） 旋转操作不改变树的中序遍历序列。

证明：右旋前的中序遍历：$inorder(T1) \cdot x \cdot inorder(T2) \cdot y \cdot inorder(T3)$

右旋后的中序遍历：$inorder(T1) \cdot x \cdot inorder(T2) \cdot y \cdot inorder(T3)$

两者相同。∎

14.2.3 AVL树插入修复

定理 14.5（AVL插入修复正确性） 插入后通过最多一次双旋或两次单旋可恢复平衡。

证明：设插入后第一个失衡节点为 $z$，其较高子节点为 $y$，$y$ 的较高子节点为 $x$。

分四种情况：

LL型（$y$ 是 $z$ 的左子，$x$ 是 $y$ 的左子）：对 $z$ 右旋
RR型（$y$ 是 $z$ 的右子，$x$ 是 $y$ 的右子）：对 $z$ 左旋
LR型（$y$ 是 $z$ 的左子，$x$ 是 $y$ 的右子）：先对 $y$ 左旋，再对 $z$ 右旋
RL型（$y$ 是 $z$ 的右子，$x$ 是 $y$ 的左子）：先对 $y$ 右旋，再对 $z$ 左旋

每种情况修复后，子树高度恢复到插入前，因此无需继续向上修复。∎

14.2.4 AVL树实现

python

from typing import TypeVar, Generic, Optional, List, Iterator

T = TypeVar('T')

class AVLNode(Generic[T]):
    """AVL树节点"""
    __slots__ = ['key', 'left', 'right', 'height']
    
    def __init__(self, key: T):
        self.key = key
        self.left: Optional['AVLNode[T]'] = None
        self.right: Optional['AVLNode[T]'] = None
        self.height: int = 1


class AVLTree(Generic[T]):
    """
    AVL树实现
    
    时间复杂度：
    - 查找：O(log n)
    - 插入：O(log n)
    - 删除：O(log n)
    
    空间复杂度：O(n)
    
    特点：
    - 严格平衡：高度差 ≤ 1
    - 查找效率最高
    - 插入删除可能需要多次旋转
    """
    
    def _height(self, node: Optional[AVLNode[T]]) -> int:
        return node.height if node else 0
    
    def _balance_factor(self, node: Optional[AVLNode[T]]) -> int:
        if not node:
            return 0
        return self._height(node.left) - self._height(node.right)
    
    def _update_height(self, node: AVLNode[T]) -> None:
        node.height = 1 + max(self._height(node.left), self._height(node.right))
    
    def _rotate_right(self, y: AVLNode[T]) -> AVLNode[T]:
        """右旋"""
        x = y.left
        T2 = x.right
        
        x.right = y
        y.left = T2
        
        self._update_height(y)
        self._update_height(x)
        
        return x
    
    def _rotate_left(self, x: AVLNode[T]) -> AVLNode[T]:
        """左旋"""
        y = x.right
        T2 = y.left
        
        y.left = x
        x.right = T2
        
        self._update_height(x)
        self._update_height(y)
        
        return y
    
    def _rebalance(self, node: AVLNode[T]) -> AVLNode[T]:
        """重新平衡"""
        self._update_height(node)
        balance = self._balance_factor(node)
        
        if balance > 1:
            if self._balance_factor(node.left) < 0:
                node.left = self._rotate_left(node.left)
            return self._rotate_right(node)
        
        if balance < -1:
            if self._balance_factor(node.right) > 0:
                node.right = self._rotate_right(node.right)
            return self._rotate_left(node)
        
        return node
    
    def insert(self, root: Optional[AVLNode[T]], key: T) -> AVLNode[T]:
        """插入 - O(log n)"""
        if not root:
            return AVLNode(key)
        
        if key < root.key:
            root.left = self.insert(root.left, key)
        elif key > root.key:
            root.right = self.insert(root.right, key)
        else:
            return root
        
        return self._rebalance(root)
    
    def delete(self, root: Optional[AVLNode[T]], key: T) -> Optional[AVLNode[T]]:
        """删除 - O(log n)"""
        if not root:
            return None
        
        if key < root.key:
            root.left = self.delete(root.left, key)
        elif key > root.key:
            root.right = self.delete(root.right, key)
        else:
            if not root.left:
                return root.right
            if not root.right:
                return root.left
            
            successor = self._min_node(root.right)
            root.key = successor.key
            root.right = self.delete(root.right, successor.key)
        
        return self._rebalance(root)
    
    def search(self, root: Optional[AVLNode[T]], key: T) -> Optional[AVLNode[T]]:
        """查找 - O(log n)"""
        if not root:
            return None
        if key == root.key:
            return root
        if key < root.key:
            return self.search(root.left, key)
        return self.search(root.right, key)
    
    def _min_node(self, node: Optional[AVLNode[T]]) -> Optional[AVLNode[T]]:
        while node and node.left:
            node = node.left
        return node
    
    def inorder(self, root: Optional[AVLNode[T]]) -> List[T]:
        """中序遍历"""
        result = []
        def _traverse(node: Optional[AVLNode[T]]):
            if node:
                _traverse(node.left)
                result.append(node.key)
                _traverse(node.right)
        _traverse(root)
        return result
    
    def is_balanced(self, root: Optional[AVLNode[T]]) -> bool:
        """验证平衡性"""
        if not root:
            return True
        
        if abs(self._balance_factor(root)) > 1:
            return False
        
        return self.is_balanced(root.left) and self.is_balanced(root.right)


def demonstrate_avl():
    """演示AVL树"""
    tree = AVLTree[int]()
    root = None
    
    keys = [10, 20, 30, 40, 50, 25]
    for key in keys:
        root = tree.insert(root, key)
        print(f"插入 {key} 后: {tree.inorder(root)}")
    
    print(f"\n平衡验证: {tree.is_balanced(root)}")
    print(f"树高度: {tree._height(root)}")


if __name__ == '__main__':
    demonstrate_avl()

14.3 红黑树理论

14.3.1 红黑树的数学定义

定义 14.6（红黑树） 红黑树是满足以下五条性质的二叉搜索树：

颜色性质：每个节点是红色或黑色
根性质：根节点是黑色
叶子性质：所有叶子（NIL）节点是黑色
红色性质：红色节点的两个子节点都是黑色
黑高性质：从任一节点到其每个叶子的所有路径包含相同数量的黑色节点

定义 14.7（黑高） 节点 $v$ 的黑高 $bh(v)$ 定义为从 $v$ 到叶子（不含 $v$）的路径上黑色节点的数量。

定理 14.6（红黑树高度上界） $n$ 个节点的红黑树的高度 $h$ 满足：

$$h \leq 2\log_2(n+1)$$

证明：首先证明以节点 $x$ 为根的子树至少包含 $2^{bh(x)} - 1$ 个内部节点。

归纳基础：若 $x$ 是叶子，子树包含 $0 = 2^0 - 1$ 个节点。

归纳步骤：设 $x$ 有两个子节点，每个子节点的黑高至少为 $bh(x) - 1$（若子节点是红色）或 $bh(x)$（若子节点是黑色）。因此每个子树至少有 $2^{bh(x)-1} - 1$ 个节点。

总节点数：$n \geq 2(2^{bh(x)-1} - 1) + 1 = 2^{bh(x)} - 1$。

由红色性质，从根到叶子的路径上至少一半节点是黑色（根是黑色，红色节点后必须是黑色）。

因此 $bh(root) \geq h/2$。

代入：$n \geq 2^{h/2} - 1$，即 $h \leq 2\log_2(n+1)$。∎

14.3.2 红黑树插入修复

定理 14.7（红黑树插入修复正确性） 插入后通过最多两次旋转可恢复红黑性质。

证明：设新插入的节点为 $z$，初始着为红色。可能违反红色性质。

分三种情况（设 $z$ 的父节点是祖父节点的左子）：

情况1：叔节点是红色

将父节点和叔节点着为黑色，祖父节点着为红色
将 $z$ 上移到祖父节点
可能继续向上修复

情况2：叔节点是黑色，$z$ 是右子

对父节点左旋
转化为情况3

情况3：叔节点是黑色，$z$ 是左子

将父节点着为黑色，祖父节点着为红色
对祖父节点右旋
修复完成

情况2和3最多需要一次旋转，情况1可能向上传播但最多 $O(\log n)$ 次。∎

14.3.3 红黑树实现

python

from typing import TypeVar, Generic, Optional, List
from enum import Enum

T = TypeVar('T')

class Color(Enum):
    RED = True
    BLACK = False


class RBNode(Generic[T]):
    """红黑树节点"""
    __slots__ = ['key', 'left', 'right', 'parent', 'color']
    
    def __init__(self, key: T, color: Color = Color.RED):
        self.key = key
        self.left: Optional['RBNode[T]'] = None
        self.right: Optional['RBNode[T]'] = None
        self.parent: Optional['RBNode[T]'] = None
        self.color = color
    
    def is_red(self) -> bool:
        return self.color == Color.RED
    
    def is_black(self) -> bool:
        return self.color == Color.BLACK


class RedBlackTree(Generic[T]):
    """
    红黑树实现
    
    时间复杂度：
    - 查找：O(log n)
    - 插入：O(log n)
    - 删除：O(log n)
    
    空间复杂度：O(n)
    
    特点：
    - 近似平衡：h ≤ 2log(n+1)
    - 插入删除旋转次数少（最多2次）
    - 工程应用广泛
    """
    
    NIL = RBNode(None, Color.BLACK)
    
    def __init__(self):
        self._root: Optional[RBNode[T]] = None
        self._size: int = 0
    
    def _left_rotate(self, x: RBNode[T]) -> None:
        """左旋"""
        y = x.right
        x.right = y.left
        
        if y.left:
            y.left.parent = x
        
        y.parent = x.parent
        
        if not x.parent:
            self._root = y
        elif x == x.parent.left:
            x.parent.left = y
        else:
            x.parent.right = y
        
        y.left = x
        x.parent = y
    
    def _right_rotate(self, y: RBNode[T]) -> None:
        """右旋"""
        x = y.left
        y.left = x.right
        
        if x.right:
            x.right.parent = y
        
        x.parent = y.parent
        
        if not y.parent:
            self._root = x
        elif y == y.parent.left:
            y.parent.left = x
        else:
            y.parent.right = x
        
        x.right = y
        y.parent = x
    
    def _insert_fixup(self, z: RBNode[T]) -> None:
        """插入修复"""
        while z.parent and z.parent.is_red():
            if z.parent == z.parent.parent.left:
                y = z.parent.parent.right
                
                if y and y.is_red():
                    z.parent.color = Color.BLACK
                    y.color = Color.BLACK
                    z.parent.parent.color = Color.RED
                    z = z.parent.parent
                else:
                    if z == z.parent.right:
                        z = z.parent
                        self._left_rotate(z)
                    
                    z.parent.color = Color.BLACK
                    z.parent.parent.color = Color.RED
                    self._right_rotate(z.parent.parent)
            else:
                y = z.parent.parent.left
                
                if y and y.is_red():
                    z.parent.color = Color.BLACK
                    y.color = Color.BLACK
                    z.parent.parent.color = Color.RED
                    z = z.parent.parent
                else:
                    if z == z.parent.left:
                        z = z.parent
                        self._right_rotate(z)
                    
                    z.parent.color = Color.BLACK
                    z.parent.parent.color = Color.RED
                    self._left_rotate(z.parent.parent)
        
        if self._root:
            self._root.color = Color.BLACK
    
    def insert(self, key: T) -> bool:
        """插入 - O(log n)"""
        z = RBNode(key)
        y = None
        x = self._root
        
        while x:
            y = x
            if z.key < x.key:
                x = x.left
            elif z.key > x.key:
                x = x.right
            else:
                return False
        
        z.parent = y
        
        if not y:
            self._root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z
        
        z.left = None
        z.right = None
        z.color = Color.RED
        
        self._insert_fixup(z)
        self._size += 1
        return True
    
    def search(self, key: T) -> Optional[RBNode[T]]:
        """查找 - O(log n)"""
        current = self._root
        while current:
            if key == current.key:
                return current
            elif key < current.key:
                current = current.left
            else:
                current = current.right
        return None
    
    def _transplant(self, u: RBNode[T], v: Optional[RBNode[T]]) -> None:
        """替换子树"""
        if not u.parent:
            self._root = v
        elif u == u.parent.left:
            u.parent.left = v
        else:
            u.parent.right = v
        
        if v:
            v.parent = u.parent
    
    def _minimum(self, node: Optional[RBNode[T]]) -> Optional[RBNode[T]]:
        while node and node.left:
            node = node.left
        return node
    
    def _delete_fixup(self, x: Optional[RBNode[T]]) -> None:
        """删除修复"""
        while x and x != self._root and x.is_black():
            if x == x.parent.left:
                w = x.parent.right
                
                if w and w.is_red():
                    w.color = Color.BLACK
                    x.parent.color = Color.RED
                    self._left_rotate(x.parent)
                    w = x.parent.right
                
                if (not w.left or w.left.is_black()) and \
                   (not w.right or w.right.is_black()):
                    w.color = Color.RED
                    x = x.parent
                else:
                    if not w.right or w.right.is_black():
                        if w.left:
                            w.left.color = Color.BLACK
                        w.color = Color.RED
                        self._right_rotate(w)
                        w = x.parent.right
                    
                    w.color = x.parent.color
                    x.parent.color = Color.BLACK
                    if w.right:
                        w.right.color = Color.BLACK
                    self._left_rotate(x.parent)
                    x = self._root
            else:
                w = x.parent.left
                
                if w and w.is_red():
                    w.color = Color.BLACK
                    x.parent.color = Color.RED
                    self._right_rotate(x.parent)
                    w = x.parent.left
                
                if (not w.right or w.right.is_black()) and \
                   (not w.left or w.left.is_black()):
                    w.color = Color.RED
                    x = x.parent
                else:
                    if not w.left or w.left.is_black():
                        if w.right:
                            w.right.color = Color.BLACK
                        w.color = Color.RED
                        self._left_rotate(w)
                        w = x.parent.left
                    
                    w.color = x.parent.color
                    x.parent.color = Color.BLACK
                    if w.left:
                        w.left.color = Color.BLACK
                    self._right_rotate(x.parent)
                    x = self._root
        
        if x:
            x.color = Color.BLACK
    
    def delete(self, key: T) -> bool:
        """删除 - O(log n)"""
        z = self.search(key)
        if not z:
            return False
        
        y = z
        y_original_color = y.color
        
        if not z.left:
            x = z.right
            self._transplant(z, z.right)
        elif not z.right:
            x = z.left
            self._transplant(z, z.left)
        else:
            y = self._minimum(z.right)
            y_original_color = y.color
            x = y.right
            
            if y.parent == z:
                if x:
                    x.parent = y
            else:
                self._transplant(y, y.right)
                y.right = z.right
                y.right.parent = y
            
            self._transplant(z, y)
            y.left = z.left
            y.left.parent = y
            y.color = z.color
        
        if y_original_color == Color.BLACK and x:
            self._delete_fixup(x)
        
        self._size -= 1
        return True
    
    def inorder(self) -> List[T]:
        """中序遍历"""
        result = []
        
        def _traverse(node: Optional[RBNode[T]]):
            if node:
                _traverse(node.left)
                result.append(node.key)
                _traverse(node.right)
        
        _traverse(self._root)
        return result
    
    def _check_properties(self, node: Optional[RBNode[T]], black_count: int, 
                          path_black_count: List[int]) -> bool:
        """验证红黑性质"""
        if not node:
            path_black_count.append(black_count)
            return True
        
        if node.is_red():
            if (node.left and node.left.is_red()) or \
               (node.right and node.right.is_red()):
                return False
        
        new_black_count = black_count + (1 if node.is_black() else 0)
        
        return (self._check_properties(node.left, new_black_count, path_black_count) and
                self._check_properties(node.right, new_black_count, path_black_count))
    
    def is_valid_rbtree(self) -> bool:
        """验证红黑树性质"""
        if not self._root:
            return True
        
        if self._root.is_red():
            return False
        
        path_black_count = []
        if not self._check_properties(self._root, 0, path_black_count):
            return False
        
        return len(set(path_black_count)) == 1
    
    def __len__(self) -> int:
        return self._size
    
    def __contains__(self, key: T) -> bool:
        return self.search(key) is not None


def demonstrate_rbtree():
    """演示红黑树"""
    tree = RedBlackTree[int]()
    
    keys = [10, 20, 30, 15, 25, 5, 1, 35]
    for key in keys:
        tree.insert(key)
        print(f"插入 {key}: 有效={tree.is_valid_rbtree()}")
    
    print(f"\n中序遍历: {tree.inorder()}")
    print(f"树大小: {len(tree)}")
    
    tree.delete(20)
    print(f"\n删除 20 后: {tree.inorder()}")
    print(f"有效: {tree.is_valid_rbtree()}")


if __name__ == '__main__':
    demonstrate_rbtree()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361

14.4 平衡树对比分析

14.4.1 AVL树 vs 红黑树

定理 14.8（AVL树vs红黑树查找效率） AVL树的查找效率略高于红黑树。

证明：

AVL树高度：$h_{AVL} \leq 1.44 \log_2 n$
红黑树高度：$h_{RB} \leq 2 \log_2 n$

因此AVL树更平衡，查找路径更短。∎

定理 14.9（AVL树vs红黑树修改效率） 红黑树的插入删除效率高于AVL树。

证明：

AVL树插入：最多 $O(\log n)$ 次旋转
红黑树插入：最多 2 次旋转
AVL树删除：最多 $O(\log n)$ 次旋转
红黑树删除：最多 3 次旋转

红黑树修改操作更稳定。∎

14.4.2 选择指南

特性	AVL树	红黑树
高度上界	$1.44 \log n$	$2 \log n$
查找效率	更高	略低
插入旋转	最多 $O(\log n)$	最多 2 次
删除旋转	最多 $O(\log n)$	最多 3 次
实现复杂度	中等	较高
典型应用	数据库索引	C++ STL、Java TreeMap

定理 14.10（平衡树选择原则）

查找密集型应用：选择AVL树
修改密集型应用：选择红黑树
需要稳定性能：选择红黑树

14.5 其他平衡树结构

14.5.1 伸展树

定义 14.8（伸展树） 伸展树是一种自调整二叉搜索树，每次访问后将访问节点移动到根。

定理 14.11（伸展树均摊复杂度） 伸展树操作的均摊复杂度为 $O(\log n)$。

证明：使用势能方法。定义势能函数 $\Phi(T) = \sum_{x \in T} \log(size(x))$。

分析伸展操作的均摊代价，可证明为 $O(\log n)$。∎

14.5.2 B树

定义 14.9（B树） B树是多路平衡搜索树，满足：

根节点至少有2个子节点
每个内部节点有 $\lceil m/2 \rceil$ 到 $m$ 个子节点
所有叶子在同一层

定理 14.12（B树高度） $n$ 个键、最小度数为 $t$ 的B树高度：

$$h \leq \log_t \frac{n+1}{2}$$

14.6 本章小结

14.6.1 核心定理总结

定理	内容	应用
定理 14.1	平衡树高度 $O(\log n)$	复杂度保证
定理 14.2	AVL树高度上界	性能分析
定理 14.3	旋转保持BST性质	正确性验证
定理 14.6	红黑树高度上界	性能分析
定理 14.7	红黑树插入修复	算法设计

14.6.2 平衡树复杂度对比

操作	AVL树	红黑树	伸展树
查找	$O(\log n)$	$O(\log n)$	$O(\log n)$ 均摊
插入	$O(\log n)$	$O(\log n)$	$O(\log n)$ 均摊
删除	$O(\log n)$	$O(\log n)$	$O(\log n)$ 均摊
旋转次数	$O(\log n)$	最多 3 次	$O(\log n)$ 均摊

14.6.3 应用场景

场景	推荐结构	原因
数据库索引	B+树	磁盘友好
语言标准库	红黑树	修改稳定
内存数据库	AVL树	查找高效
缓存系统	伸展树	局部性好

14.7 习题

理论题

证明：AVL树的高度上界为 $1.44 \log_2 n$。
证明：红黑树的高度上界为 $2 \log_2(n+1)$。
分析AVL树删除操作的最坏情况旋转次数。
证明：旋转操作保持BST性质和中序遍历。

设计题

设计一个支持范围查询的平衡树。
实现一个支持持久化的红黑树。

实现题

实现AVL树的完整删除操作。
实现B树的插入和删除操作。

14.8 参考文献

Adelson-Velsky, G., & Landis, E. M. (1962). An algorithm for the organization of information. Proceedings of the USSR Academy of Sciences, 146, 263-266.
Bayer, R. (1972). Symmetric binary B-trees: Data structure and maintenance algorithms. Acta Informatica, 1(4), 290-306.
Guibas, L. J., & Sedgewick, R. (1978). A dichromatic framework for balanced trees. FOCS, 8-21.
Sleator, D. D., & Tarjan, R. E. (1985). Self-adjusting binary search trees. Journal of the ACM, 32(3), 652-686.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.). MIT Press. Chapters 13-14.
Knuth, D. E. (1998). The Art of Computer Programming, Volume 3: Sorting and Searching (2nd ed.). Addison-Wesley. Section 6.2.3.

下一章：第15章图论基础理论

第14章 平衡树理论 ​

本章导读 ​

学习目标 ​

14.1 平衡树的形式化定义 ​

14.1.1 平衡性的数学定义 ​

14.1.2 平衡树ADT ​

14.2 AVL树理论 ​

14.2.1 AVL树的数学定义 ​

14.2.2 旋转操作的正确性 ​

14.2.3 AVL树插入修复 ​

14.2.4 AVL树实现 ​

14.3 红黑树理论 ​

14.3.1 红黑树的数学定义 ​

14.3.2 红黑树插入修复 ​

14.3.3 红黑树实现 ​

14.4 平衡树对比分析 ​

14.4.1 AVL树 vs 红黑树 ​

14.4.2 选择指南 ​

14.5 其他平衡树结构 ​

14.5.1 伸展树 ​

14.5.2 B树 ​

14.6 本章小结 ​

14.6.1 核心定理总结 ​

14.6.2 平衡树复杂度对比 ​

14.6.3 应用场景 ​

14.7 习题 ​

理论题 ​

设计题 ​

实现题 ​

14.8 参考文献 ​