平衡树
平衡树（Balanced Tree）：特殊的二叉树，通过特定机制确保树的左右子树高度差保持在一定范围内（如 AVL 树要求高度差不超过 1），从而保证插入、删除、查找操作的时间复杂度为 O (log n)。
平衡树(Balance Tree，BT) 指的是，任意节点的子树的高度差都小于等于1。常见的符合平衡树的有，B树（多路平衡搜索树）、AVL树（二叉平衡搜索树）等。平衡树可以完成集合的一系列操作, 时间复杂度和空间复杂度相对于“2-3树”要低，在完成集合的一系列操作中始终保持平衡，为大型数据库的组织、索引提供了一条新的途径。
性质：高为h的BT, 其结点的数目在2^(h+1)-1和1/2(3^(h+1)−1)之间,叶的数目在2^h和3^h之间。
平衡树（Balanced Tree）
平衡树是一类特殊的树型数据结构，其核心特点是通过某种规则或算法保持树的高度平衡，避免树退化为链表，从而确保插入、删除、查询等操作的时间复杂度稳定在 *O*(log*n*)（n 为节点数）。平衡树的种类较多，常见的包括 AVL 树、红黑树、伸展树、替罪羊树、Splay 树、Treap 树 等。以下从定义、特点、应用场景等方面详细说明。
一、常见平衡树类型及详解
1. AVL 树（Adelson-Velsky and Landis Tree）
所属类别：属于 二叉搜索树（BST） 的改进型，是最早的自平衡二叉搜索树。
定义： 对于树中的任意节点，其左子树和右子树的高度差（平衡因子，Balance Factor）的绝对值不超过 1。平衡因子 = 左子树高度 - 右子树高度。
特点
：
- 严格平衡：平衡因子必须为
-1、0、1，因此高度严格平衡。 - 旋转调整：插入或删除节点后，若平衡因子超出范围，通过 左旋、右旋、左右旋、右左旋 四种旋转操作恢复平衡。
- 查询效率高：由于高度平衡，查询时间复杂度稳定为 O(logn)，但插入 / 删除时旋转操作较多，效率略低于红黑树。
- 严格平衡：平衡因子必须为
示例
：
（图中每个节点标注平衡因子，插入节点后通过旋转保持平衡）
关键性质
：
- 高度 h≈log2n，节点数 n≥2h−1（接近满二叉树）。
- 旋转操作保证树的平衡，但会增加常数时间开销。
现实应用
：
- 早期数据库索引（如 MySQL 的某些版本）。
- 实现高效的字典结构（如 Java 的
TreeSet早期版本，现用红黑树）。
Java 代码示例
：
java
public class AVLTree { static class Node { int key, height; Node left, right; Node(int key) { this.key = key; height = 1; } } private Node root; // 获取高度 private int height(Node node) { return (node == null) ? 0 : node.height; } // 计算平衡因子 private int getBalance(Node node) { return (node == null) ? 0 : height(node.left) - height(node.right); } // 右旋 private Node rightRotate(Node y) { Node x = y.left; Node T2 = x.right; x.right = y; y.left = T2; y.height = Math.max(height(y.left), height(y.right)) + 1; x.height = Math.max(height(x.left), height(x.right)) + 1; return x; } // 左旋 private Node leftRotate(Node x) { Node y = x.right; Node T2 = y.left; y.left = x; x.right = T2; x.height = Math.max(height(x.left), height(x.right)) + 1; y.height = Math.max(height(y.left), height(y.right)) + 1; return y; } // 插入节点（递归实现） private Node insert(Node node, int key) { if (node == null) return new Node(key); if (key < node.key) node.left = insert(node.left, key); else node.right = insert(node.right, key); node.height = 1 + Math.max(height(node.left), height(node.right)); int balance = getBalance(node); // 左左情况 if (balance > 1 && key < node.left.key) return rightRotate(node); // 右右情况 if (balance < -1 && key > node.right.key) return leftRotate(node); // 左右情况 if (balance > 1 && key > node.left.key) { node.left = leftRotate(node.left); return rightRotate(node); } // 右左情况 if (balance < -1 && key < node.right.key) { node.right = rightRotate(node.right); return leftRotate(node); } return node; } public void insert(int key) { root = insert(root, key); } // 简化查询方法（BST标准查询） public boolean search(int key) { Node curr = root; while (curr != null) { if (key == curr.key) return true; else if (key < curr.key) curr = curr.left; else curr = curr.right; } return false; } }
2. 红黑树（Red-Black Tree）
所属类别：属于 二叉搜索树（BST） 的改进型，是一种 弱平衡树（平衡条件较 AVL 树宽松）。
定义
：
每个节点带有颜色属性（红或黑），通过以下规则保持平衡：
- 根节点和叶子节点（NIL 节点）为黑色。
- 红色节点的两个子节点必须为黑色（红节点不能相邻）。
- 从任一节点到其每个叶子节点的所有路径上包含相同数量的黑色节点（黑高平衡）。
特点
：
- 弱平衡：不要求平衡因子绝对值≤1，而是通过颜色规则保证最长路径不超过最短路径的 2 倍（最长路径为黑 + 红交替，最短路径全为黑）。
- 变色与旋转：插入 / 删除时通过重新着色节点和少量旋转（最多 3 次）恢复平衡，效率高于 AVL 树。
- 查询、插入、删除综合性能更优：适合频繁修改的场景。
示例
：
（图中红色节点用空心表示，黑色用实心表示，路径黑高均为 3）
关键性质
：
- 树的高度 h≤2log2(n+1)，保证操作时间复杂度为 O(logn)。
- 黑高平衡确保最坏情况下性能稳定。
现实应用
：
- Java 集合框架中的
TreeMap和TreeSet（JDK 1.8 后实现）。 - C++ 的
std::map和std::set。 - Linux 内核的进程调度（CFS 调度器）、文件系统索引。
- Java 集合框架中的
Java 代码示例
：
java
public class RedBlackTree { enum Color { RED, BLACK } static class Node { int key; Color color; Node left, right, parent; Node(int key, Color color) { this.key = key; this.color = color; left = right = parent = null; } } private Node root; private static final Node NIL = new Node(0, Color.BLACK); public RedBlackTree() { root = NIL; NIL.left = NIL.right = NIL; } // 左旋 private void leftRotate(Node x) { Node y = x.right; x.right = y.left; if (y.left != NIL) y.left.parent = x; y.parent = x.parent; if (x.parent == null) root = y; else if (x == x.parent.left) x.parent.left = y; else x.parent.right = y; y.left = x; x.parent = y; } // 右旋 private void rightRotate(Node x) { Node y = x.left; x.left = y.right; if (y.right != NIL) y.right.parent = x; y.parent = x.parent; if (x.parent == null) root = y; else if (x == x.parent.right) x.parent.right = y; else x.parent.left = y; y.right = x; x.parent = y; } // 插入后修复红黑树性质 private void fixInsert(Node z) { while (z.parent.color == Color.RED) { if (z.parent == z.parent.parent.left) { Node uncle = z.parent.parent.right; if (uncle.color == Color.RED) { // 情况1：叔叔节点为红色，重新着色 z.parent.color = Color.BLACK; uncle.color = Color.BLACK; z.parent.parent.color = Color.RED; z = z.parent.parent; } else { // 情况2或3：叔叔节点为黑色，旋转处理 if (z == z.parent.right) { // 情况2：左旋转变为情况3 z = z.parent; leftRotate(z); } // 情况3：右旋转并变色 z.parent.color = Color.BLACK; z.parent.parent.color = Color.RED; rightRotate(z.parent.parent); } } else { // 对称情况（父节点为右子树） // 逻辑与上述对称，此处省略 } } root.color = Color.BLACK; // 根节点必须为黑色 } public void insert(int key) { Node z = new Node(key, Color.RED); z.left = z.right = NIL; Node y = null; Node x = root; while (x != NIL) { y = x; if (z.key < x.key) x = x.left; else x = x.right; } z.parent = y; if (y == null) root = z; // 空树时 else if (z.key < y.key) y.left = z; else y.right = z; fixInsert(z); // 修复红黑树性质 } }
3. 伸展树（Splay Tree）
所属类别：属于 二叉搜索树（BST） 的改进型，通过 ** 伸展操作（Splay）** 实现平衡。
定义： 伸展树没有显式的平衡条件，而是将最近访问的节点通过旋转（伸展操作）移动到根节点，使树的结构向频繁访问的节点倾斜，从而在均摊时间复杂度下达到高效。
特点
：
- 自调整：无需维护平衡因子或颜色，完全通过访问频率调整树结构。
- 均摊高效：单次操作时间复杂度可能较高（最坏 O(n)），但连续 n 次操作的均摊时间为 O(logn)。
- 实现简单：仅需两种基本旋转（单旋转和之字形 / 一字形旋转）。
示例
：
访问节点后通过伸展操作将其移至根节点，例如：
（图中访问节点 5 后，通过旋转使其成为根节点）
关键性质
：
- 局部性原理：频繁访问的节点靠近根节点，减少后续访问代价。
- 均摊时间复杂度为 O(logn)，适用于访问具有局部性的场景。
现实应用
：
- Lisp 语言的实现（如 AutoLisp）。
- 编译器的符号表、内存管理中的缓存机制。
Java 代码示例
（简化版，仅实现伸展和插入）：
java
public class SplayTree { static class Node { int key; Node left, right; Node(int key) { this.key = key; } } private Node root; // 右旋（x为当前节点，父节点为y） private Node rightRotate(Node x) { Node y = x.left; x.left = y.right; y.right = x; return y; } // 左旋（x为当前节点，父节点为y） private Node leftRotate(Node x) { Node y = x.right; x.right = y.left; y.left = x; return y; } // 伸展操作：将节点key伸展到根 private Node splay(Node node, int key) { if (node == null || node.key == key) return node; if (key < node.key) { if (node.left == null) return node; // 之字形（Zig-Zag）或一字形（Zig-Zig） if (key < node.left.key) { node.left.left = splay(node.left.left, key); node = rightRotate(node); } else if (key > node.left.key) { node.left.right = splay(node.left.right, key); if (node.left.right != null) node.left = leftRotate(node.left); } return (node.left == null) ? node : rightRotate(node); } else { // key > node.key // 对称处理，与左子树情况镜像 if (node.right == null) return node; if (key < node.right.key) { node.right.left = splay(node.right.left, key); if (node.right.left != null) node.right = rightRotate(node.right); } else if (key > node.right.key) { node.right.right = splay(node.right.right, key); node = leftRotate(node); } return (node.right == null) ? node : leftRotate(node); } } public void insert(int key) { if (root == null) { root = new Node(key); return; } root = splay(root, key); // 先伸展到根（若存在则忽略插入） if (key < root.key) { Node newNode = new Node(key); newNode.left = root.left; newNode.right = root; root.left = null; root = newNode; } else if (key > root.key) { Node newNode = new Node(key); newNode.right = root.right; newNode.left = root; root.right = null; root = newNode; } // 若key已存在，不插入（保持BST性质） } }
4. 替罪羊树（Scapegoat Tree）
所属类别：属于 二叉搜索树（BST） 的改进型，通过重构子树实现平衡。
定义： 设定一个平衡因子 α（通常为 0.5），要求子树的大小至少为其父树大小的 α 倍。若不满足，则标记该子树的根节点为 “替罪羊”，并对该子树进行中序遍历重构（转化为完全二叉树）。
特点
：
- 非实时平衡：不要求每次操作后立即平衡，而是在发现不平衡时批量重构，减少单次操作开销。
- 重构效率高：重构时间为 O(n)，但触发频率低，均摊时间复杂度为 O(logn)。
- 实现简单：无需复杂旋转，适合对实时性要求不高的场景。
关键性质
：
- 树的高度 h=O(logn)，保证均摊性能。
- 平衡条件：子树大小 ≥ α× 父树大小（α 通常取 1/2）。
现实应用
：
- 某些函数式编程库中的有序集合实现。
- 需要简单平衡策略的场景（如教学示例）。
Java 代码示例
（简化重构逻辑）：
java
public class ScapegoatTree { static class Node { int key, size; Node left, right; Node(int key) { this.key = key; size = 1; } } private Node root; private static final double ALPHA = 0.5; // 平衡因子 private int size(Node node) { return (node == null) ? 0 : node.size; } private void updateSize(Node node) { if (node != null) node.size = 1 + size(node.left) + size(node.right); } // 中序遍历重构子树 private Node rebuild(Node[] nodes, int l, int r) { if (l > r) return null; int mid = (l + r) / 2; Node root = nodes[mid]; root.left = rebuild(nodes, l, mid - 1); root.right = rebuild(nodes, mid + 1, r); updateSize(root); return root; } // 检查是否需要重构（替罪羊条件） private boolean isScapegoat(Node node, Node parent) { return parent != null && size(node) < ALPHA * size(parent); } private Node insert(Node node, int key, Node parent, boolean[] scapegoatFound) { if (node == null) { Node newNode = new Node(key); if (parent == null) root = newNode; // 检查父节点是否需要成为替罪羊 if (parent != null && isScapegoat(parent, null)) { // 根节点的父节点为null scapegoatFound[0] = true; } return newNode; } updateSize(node); int cmp = key - node.key; if (cmp < 0) { node.left = insert(node.left, key, node, scapegoatFound); if (scapegoatFound[0] && isScapegoat(node.left, node)) { scapegoatFound[0] = false; // 标记已处理 // 收集子树节点并重构 Node[] nodes = new Node[size(node.left) + 1]; int idx = 0; inorderTraversal(node.left, nodes, idx); // 中序遍历填充数组 node.left = rebuild(nodes, 0, nodes.length - 1); updateSize(node); } } else { node.right = insert(node.right, key, node, scapegoatFound); if (scapegoatFound[0] && isScapegoat(node.right, node)) { scapegoatFound[0] = false; Node[] nodes = new Node[size(node.right) + 1]; int idx = 0; inorderTraversal(node.right, nodes, idx); node.right = rebuild(nodes, 0, nodes.length - 1); updateSize(node); } } return node; } private void inorderTraversal(Node node, Node[] nodes, int idx) { if (node != null) { inorderTraversal(node.left, nodes, idx); nodes[idx++] = node; inorderTraversal(node.right, nodes, idx); } } public void insert(int key) { boolean[] scapegoatFound = {false}; root = insert(root, key, null, scapegoatFound); } }
二、平衡树关键性质对比
| 类型 | 所属 BST | 平衡条件 | 旋转 / 调整方式 | 时间复杂度（均摊） | 实现难度 | 适用场景 |
|---|---|---|---|---|---|---|
| AVL 树 | 是 | 平衡因子绝对值≤1（严格平衡） | 左旋 / 右旋（4 种旋转） | O(logn) | 高 | 查询密集型 |
| 红黑树 | 是 | 黑高平衡，红节点不相邻 | 变色 + 旋转（最多 3 次） | O(logn) | 中 | 频繁修改 + 查询 |
| 伸展树 | 是 | 无显式平衡条件，通过伸展操作使最近访问节点靠近根 | 单旋转 / 之字形旋转 | O(logn) | 低 | 访问局部性明显的场景 |
| 替罪羊树 | 是 | 子树大小≥α× 父树大小（α=0.5） | 子树重构（中序遍历） | O(logn) | 中 | 简单平衡需求，避免复杂旋转 |
| Treap 树 | 是 | 结合 BST 和堆性质（节点有优先级，左子树优先级≥当前节点≤右子树） | 随机旋转 | O(logn) | 中 | 需随机平衡的场景 |
| Splay 树 | 是 | 同伸展树（Splay Tree 即伸展树） | 同上 | 同上 | 低 | 同上 |
三、现实应用场景总结
需要高效查询和修改的场景
：
- 红黑树：Java 集合、C++ 标准库、Linux 内核等。
- AVL 树：早期数据库索引、某些实时系统（需严格平衡）。
访问具有局部性的场景
：
- 伸展树：编译器符号表、缓存系统（如 LRU 优化）。
需要简单实现或批量平衡的场景
：
- 替罪羊树：教学示例、轻量级有序集合。
- Treap 树：游戏开发中的平衡结构（利用随机优先级简化实现）。
四、总结
平衡树通过各种策略（旋转、变色、重构、自调整）避免树退化为链表，确保操作的高效性。其中：
- AVL 树是严格平衡的代表，适合查询优先场景；
- 红黑树是工程中最常用的平衡树，兼顾查询和修改效率；
- 伸展树和替罪羊树则通过不同的非严格平衡策略降低实现复杂度，适用于特定场景。
选择平衡树时，需根据具体需求（如是否允许频繁旋转、是否有局部性访问模式）决定。实际开发中，红黑树因其综合性能成为首选，而 AVL 树和伸展树则在特定领域发挥作用。