1. 简介
树是一种基础的数据结构，具备许多优良特性。它像有序数组一样支持快速查找，又像链表一样支持快速插入和删除。
本文将回顾常见的树结构类型，并重点讲解它们之间的主要差异。
2. 什么是树？
说到树，我们通常会想到根、枝干和叶子。在计算机科学中，树结构的构造也是如此。
树由一系列节点（vertices）通过边（edges）连接组成。这些边是无向的：
边不能形成环路。如果结构中存在环路，则它就不是树：
树是一种层次结构，这意味着存在父节点和子节点。树只有一个根节点。
每个节点只能有一个父节点，但可以有多个子节点。没有子节点的节点称为叶子节点，子节点也可以为空：
树的其他重要概念包括：
- 路径（Path）：一系列顺序连接的边
- 高度（Height）：节点到最远叶子节点之间的边数；整棵树的高度是根节点的高度
- 深度（Depth）：节点到根节点之间的边数
3. 二叉树（Binary Tree）
二叉树是一种每个节点最多只能有两个子节点的树结构。
每个节点通常包含一个值、一个左子节点、一个右子节点以及父节点引用。左、右子节点可以为空：
4. 二叉搜索树（Binary Search Tree）
二叉搜索树（BST）是一种有序的二叉树，它具备特定的排序性质。
判断一个二叉树是否是 BST 的标准是：对它进行中序遍历（In-order Traversal）时，输出的序列是有序的。
在 BST 的任意子树中，左子节点的值小于父节点，右子节点的值大于父节点：
平均时间复杂度：
- 查找：O(log n)
- 插入：O(log n)
- 删除：O(log n)
4.1 BST 插入逻辑
以下是 BST 的插入伪代码：
algorithm BSTInsert(n, t):
// INPUT
// n = 待插入的节点
// t = 二叉搜索树
// OUTPUT
// 将节点 n 插入 BST 中
temp <- null
current <- t.root
while current != null:
temp <- current
if n.val < current.val:
current <- current.left
else:
current <- current.right
n.parent <- temp
if temp = null:
t.root <- n
else if n.val < temp.val:
temp.left <- n
else:
temp.right <- n
4.2 非平衡 BST
当数据分布不均时，就会形成非平衡 BST。如果插入顺序基本是递增或递减的，树的节点会集中在一侧，另一侧几乎为空。
比如从一个已排序数组插入节点：
data = [8, 12, 29, 43, 65]
这种情况下，BST 退化成链表结构，查找、插入、删除效率都变为 O(n)，性能大打折扣。
时间复杂度退化为：
- 查找：O(n)
- 插入：O(n)
- 删除：O(n)
4.3 平衡 BST
如果插入顺序是随机的，BST 会自然保持相对平衡。
一种简单做法是插入前对数据进行随机化处理：
data = [12, 43, 65, 8, 29]
此时时间复杂度恢复为：
- 查找：O(log n)
- 插入：O(log n)
- 删除：O(log n)
接下来我们介绍几种维持平衡的树结构。
5. 红黑树（Red-Black Tree）
红黑树是一种自平衡二叉搜索树。除了 BST 的特性外，每个节点还有一个颜色属性（红色或黑色），并通过一组规则（红黑规则）来维持树的平衡：
- 每个节点要么是红色，要么是黑色
- 根节点必须是黑色
- 如果一个节点是红色，则它的子节点必须是黑色
- 所有叶子节点（null）都是黑色
- 从根节点到任何叶子节点的所有路径中，黑色节点的数量必须相同
我们称从某个节点到其叶子节点路径上的黑色节点数为该节点的黑高（black height）。
红黑树示意图如下：
时间复杂度：
- 查找：O(log n)
- 插入：O(log n)
- 删除：O(log n)
6. AVL 树
AVL 树是最早提出的自平衡二叉搜索树，得名于发明者 Adelson-Velskii 和 Landis。
AVL 树的每个节点包含一个平衡因子（Balance Factor），表示左右子树的高度差。
AVL 树中任意节点的平衡因子绝对值不能超过 1。
插入或删除节点后，如果导致失衡，需要通过旋转操作恢复平衡。
时间复杂度：
- 查找：O(log n)
- 插入：O(log n)
- 删除：O(log n)
7. B 树（B-Tree）
B 树是一种多路搜索树，每个节点可以拥有两个以上的子节点，适用于处理大量数据的场景。
多路树的每个节点需要存储多个键值和多个子节点指针，因此节点体积通常较大。
B 树与红黑树类似，但更适用于磁盘等外部存储的索引结构。
每个 B 树节点包含 n 个键，有 n+1 个子节点，所有叶子节点处于同一深度。
B 树具有以下特点：
✅ 高度低
✅ 节点至少半满
✅ 搜索效率高
示意图如下：
时间复杂度：
- 查找：O(log n)
- 插入：O(log n)
- 删除：O(log n)
8. 总结
本文介绍了多种常见的树结构及其主要特性：
| 树类型 | 是否自平衡 | 特点描述 |
|---|---|---|
| Binary Tree | ❌ | 每个节点最多两个子节点 |
| BST | ❌ | 有序结构，查找效率高 |
| Red-Black Tree | ✅ | 使用颜色规则平衡树 |
| AVL Tree | ✅ | 使用高度差平衡，旋转次数多 |
| B Tree | ✅ | 多路树，适合磁盘索引 |
选择合适的树结构取决于具体应用场景。对于内存中频繁插入/删除且需要快速查找的场景，红黑树和 AVL 树是不错的选择；对于磁盘数据索引，B 树更为合适。