BST：二叉搜索树¶
基础概念¶
BST定义¶
- 每个父节点(parent)最多两个子节点(child)
- leftchild ≤ parent < rightchild
深度(Depth) - 根->节点¶
- 某节点的深度 = root到该节点经过的边数
- 根节点深度 = 0
- 空树不存在深度
高度(Height) - 节点->最远叶子节点¶
- 某节点的高 = 该节点到最远叶子节点经过的边数
- 叶子节点高度 = 0
- 树高(height of tree) = 根节点高度
- 空树高为-1
基本操作¶
搜索(Search)¶
- 找key在树里的位置
- 使用递归(recursion)
- if node == null -> 不存在
- if key == node.value -> 找到
- if key < node.value -> 去左子树
- if key > node.value -> 去右子树
- 时间复杂度
- 通用: O(h)
- 平均: O(log n) - 平衡状态
- 最好: O(1) - 1次就搜索到
- 最坏: O(n) - 退化成链表
插入(Insert)¶
- 类似搜索，找到合适位置并插入key
- 从root开始比较
- if key ≤ current -> 去左子树
- if key > current -> 去右子树
- if key = null -> 插入
- 时间复杂度
- 通用: O(h)
- 平均: O(log n) — 大致平衡（随机插入，期望高度 Θ(log n)）
- 最好: O(1) — 树为空；或1次比较后插入
- 最坏: O(n) — 退化成链表
删除(Delete)¶
- 情况1: 删除叶子节点
- 直接删除
- 情况2: 删除只有一个子节点的节点
- 让子节点代替他
- 情况3: 删除有两个子节点的节点
- 找到该节点的右子树的最小值(即右子树最左边) - 中序后继(successor)或中序前驱(predecessor) -用这个值替换掉要删除的节点
- 时间复杂度
- 通用: O(h)
- 平均: O(log n) — 大致平衡
- 最好: O(1)
- 最坏: O(n) — 退化成链表；或删除最底层节点；或删除有两个子节点且需走到最深 successor
遍历(traversal) - 3种 DFS 深度优先搜索¶
- 中序遍历(Inorder)
- 左 - 根 - 右
- 前序遍历(Preorder)
- 根 - 左 - 右
- 后序遍历(Postorder)
- 左 - 右 - 根
- 时间复杂度
- 三种都是O(n) - 因为每个节点都访问一次
时间复杂度总结¶
| 操作 | 通用复杂度 | 平均复杂度 | 最好情况 | 最坏情况 | 具体情况说明 |
|---|---|---|---|---|---|
| Search | O(h) | O(log n) | O(1) | O(n) | 最好：目标是 root；平均：随机插入形成近似平衡树；最坏：树退化成链表，目标在最底层或不存在 |
| Insert | O(h) | O(log n) | O(1) | O(n) | 最好：树为空或成为 root 的直接子节点；平均：树近似平衡；最坏：退化链表，一路走到底 |
| Delete | O(h) | O(log n) | O(1) | O(n) | 最好：删除 root 且为叶子或只有一个子节点；平均：树近似平衡；最坏：退化链表，删除最底层节点或 successor 在最深处 |
| Traversal | O(n) | O(n) | O(n) | O(n) | 必须访问每个节点一次，与树形无关 |
旋转(Rotation)¶
目标¶
- 在BST中，插入或删除可能会导致树失衡，从而使时间复杂度退化
- 使用旋转在不破坏BST有序性的同时使树更加平衡
基本要求¶
只能旋转有父子关系的节点
类型¶
-
左旋
- 当子节点为右子节点时进行
- 左旋后，右子节点变父节点，父节点变左子节点
A B \ -> / B A
-
右旋
- 当子节点为左子节点进行
- 右旋后，左子节点变父节点，父节点变右子节点
B A / -> \ A B
-
左右旋 - 解决AVL的LR失衡，先不细讲
- 对左子节点左旋
- 再对当前节点右旋
-
右左旋 - 解决AVL的RL失衡，先不细讲
- 对右子节点右旋
- 再对当前节点左旋
作用 - 后续 AVL & RBT 细讲¶
- 恢复AVL平衡因子(-1,0,1)
- 维护RBT红黑性质
时间复杂度¶
- 单次旋转: O(1)
- 插入调整
- AVL: 最多O(log n)次旋转
- RBT: 最多2次旋转