3.1 树（上）
3.1 树（下）
3.1.5 平衡二叉搜索树
平衡二叉搜索树是一种特殊的二叉搜索树，它通过某种机制保证树的高度平衡，从而保证操作的时间复杂度为O(log n)。当一棵普通的二叉搜索树变得不平衡时（例如，一侧的子树明显比另一侧深），搜索效率会大大降低。
为什么需要平衡二叉搜索树？
想象一下，如果我们按照以下顺序向一棵空的二叉搜索树中插入数据：1, 2, 3, 4, 5
我们会得到这样一棵树：
1
\
2
\
3
\
4
\
5
这棵树已经退化成了一个链表，此时查找、插入和删除操作的时间复杂度都变为O(n)，失去了二叉搜索树的优势。
平衡二叉搜索树通过自动调整树的结构，确保树的高度保持在O(log n)，从而保证操作的效率。
常见的平衡二叉搜索树
1. AVL树
AVL树是最早被发明的自平衡二叉搜索树之一，由G.M. Adelson-Velsky和E.M. Landis在1962年提出。
特点：
- 每个节点的左右子树高度差不超过1
- 每次插入或删除操作后，会通过旋转操作来恢复平衡
- 查找、插入和删除操作的时间复杂度都是O(log n)
平衡因子：
- 定义为右子树高度减去左子树高度
- 对于AVL树，每个节点的平衡因子只能是-1、0或1
旋转操作：
- 左旋（Left Rotation）
- 右旋（Right Rotation）
- 左-右旋（Left-Right Rotation）
- 右-左旋（Right-Left Rotation）
生活例子：
想象一个杂技演员在平衡木上保持平衡。当他感觉一侧重量过大时，会通过移动身体来重新分配重量，使两侧保持平衡。AVL树也是如此，通过旋转操作来保持左右子树的高度差不超过1。
AVL树的Java实现示例：
class AVLNode {
int data;
AVLNode left, right;
int height; // 节点的高度
public AVLNode(int data) {
this.data = data;
this.height = 1; // 新节点的高度为1
}
}
class AVLTree {
AVLNode root;
// 获取节点的高度
int height(AVLNode node) {
if (node == null)
return 0;
return node.height;
}
// 获取节点的平衡因子
int getBalance(AVLNode node) {
if (node == null)
return 0;
return height(node.right) - height(node.left);
}
// 右旋转
AVLNode rightRotate(AVLNode y) {
AVLNode x = y.left;
AVLNode 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;
}
// 左旋转
AVLNode leftRotate(AVLNode x) {
AVLNode y = x.right;
AVLNode 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;
}
// 插入节点
public void insert(int data) {
root = insertNode(root, data);
}
private AVLNode insertNode(AVLNode node, int data) {
// 1. 执行标准BST插入
if (node == null)
return new AVLNode(data);
if (data < node.data)
node.left = insertNode(node.left, data);
else if (data > node.data)
node.right = insertNode(node.right, data);
else // 重复值不插入
return node;
// 2. 更新当前节点的高度
node.height = Math.max(height(node.left), height(node.right)) + 1;
// 3. 获取平衡因子
int balance = getBalance(node);
// 4. 如果节点不平衡，则有四种情况
// 左左情况 - 右旋
if (balance < -1 && data < node.left.data)
return rightRotate(node);
// 右右情况 - 左旋
if (balance > 1 && data > node.right.data)
return leftRotate(node);
// 左右情况 - 先左旋后右旋
if (balance < -1 && data > node.left.data) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
// 右左情况 - 先右旋后左旋
if (balance > 1 && data < node.right.data) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
// 返回未更改的节点指针
return node;
}
// 中序遍历
public void inOrder() {
inOrderTraversal(root);
System.out.println();
}
private void inOrderTraversal(AVLNode node) {
if (node != null) {
inOrderTraversal(node.left);
System.out.print(node.data + " ");
inOrderTraversal(node.right);
}
}
}
2. 红黑树
红黑树是另一种常用的自平衡二叉搜索树，它在许多编程语言的标准库中被广泛使用（如Java的TreeMap和TreeSet，C++的map和set）。
特点：
- 每个节点要么是红色，要么是黑色
- 根节点是黑色
- 所有叶子节点（NIL节点）是黑色
- 如果一个节点是红色，则它的两个子节点都是黑色
- 对于每个节点，从该节点到其所有后代叶子节点的简单路径上，均包含相同数目的黑色节点
优势：
- 插入和删除操作的平均时间复杂度为O(log n)
- 相比AVL树，红黑树在插入和删除操作时需要的旋转次数更少
- 虽然红黑树的平衡条件不如AVL树严格，但对于大多数应用来说已经足够好
生活例子：
想象一个交通信号灯系统，红灯表示停止，黑灯表示通行。红黑树中的红色和黑色节点就像这样的信号灯，通过一系列规则来控制树的结构，确保树的高度保持在O(log n)。
红黑树的应用：
- Java集合框架中的TreeMap和TreeSet
- Linux内核中的完全公平调度器
- C++ STL中的map和set
- 许多数据库的实现
3. 其他平衡二叉搜索树
伸展树（Splay Tree）：
- 一种自调整的二叉搜索树
- 每次访问一个节点后，通过旋转操作将该节点移动到根节点位置
- 适合于频繁访问相同元素的场景
B树和B+树：
- 多路搜索树，每个节点可以有多个子节点
- 广泛应用于数据库和文件系统
- 特别适合磁盘等外部存储设备的数据结构
平衡二叉搜索树的应用场景
- 数据库索引：B树和B+树是数据库索引的标准实现
- 内存管理：用于跟踪内存块的分配和释放
- 文件系统：用于组织和快速访问文件
- 地图和导航系统：用于存储地理位置数据
- 网络路由：用于路由表的实现
平衡二叉搜索树的选择
- AVL树：当查询操作远多于插入和删除操作时，选择AVL树
- 红黑树：当插入和删除操作频繁时，选择红黑树
- B树/B+树：当数据量非常大，无法全部加载到内存时，选择B树或B+树
3.1.6 树的应用场景
树是一种非常实用的数据结构，在计算机科学和日常生活中有广泛的应用。下面我们通过生活中的例子来理解树的各种应用场景。
1. 文件系统的目录结构
生活例子：想象你的电脑文件管理器或手机相册。文件夹可以包含子文件夹，形成一个层次结构。
/根目录
├── 文档
│ ├── 工作
│ │ ├── 报告.docx
│ │ └── 演示.pptx
│ └── 个人
│ └── 简历.pdf
├── 图片
│ ├── 假期
│ └── 家人
└── 音乐
├── 流行
└── 古典
这种结构本质上是一棵树，其中：
- 根目录是树的根节点
- 每个文件夹是一个内部节点
- 每个文件是一个叶子节点
应用：所有现代操作系统的文件系统都使用树结构来组织文件和目录。
2. 组织结构图
生活例子：一个公司的组织架构，从CEO开始，下面是各个部门的副总裁，再下面是经理，然后是普通员工。
CEO
/ | \
/ | \
/ | \
VP1 VP2 VP3
/ | | | \
经理 经理 经理 经理 经理
/ | | | | | \
员工 员工 员工 员工 员工 员工
应用：人力资源管理系统、公司通讯录、权限管理系统。
3. 数据库索引
生活例子：图书馆的图书分类系统。图书按照主题、作者、出版日期等进行分类，使读者能够快速找到所需的书籍。
技术实现：数据库使用B树或B+树来实现索引，加速数据查询。
应用：几乎所有的关系型数据库（如MySQL、Oracle、SQL Server）都使用树结构来实现索引。
4. 决策树
生活例子：医生诊断疾病的过程。医生会问一系列问题，根据患者的回答来缩小可能的疾病范围，最终做出诊断。
发烧吗？
/ \
是 否
/ \
咳嗽吗？ 头痛吗？
/ \ / \
是 否 是 否
/ \ / \
可能是感冒 可能是其他 可能是偏头痛 可能是其他
应用：
- 医疗诊断系统
- 客户服务中的问题分类
- 机器学习中的分类算法
- 专家系统
5. 游戏中的AI决策
生活例子：下棋时，棋手会思考"如果我走这步，对方可能会怎么走，然后我应该怎么应对…"，这种思考过程可以用一棵树来表示。
技术实现：游戏AI使用决策树或极小化极大算法（Minimax）来评估不同的行动方案。
应用：
- 国际象棋、围棋等棋类游戏的AI
- 策略游戏中的电脑对手
- 角色扮演游戏中的NPC行为决策
6. HTML/XML文档的DOM树
生活例子：网页的结构，从最外层的HTML标签开始，包含头部、主体等部分，每个部分又包含更小的元素。
<html>
<head>
<title>我的网页</title>
</head>
<body>
<h1>欢迎</h1>
<p>这是一个<a href="#">链接</a></p>
</body>
</html>
这段HTML代码可以表示为以下树结构：
html
/ \
head body
| / \
title h1 p
| \
"欢迎" a
/
"链接"
应用：
- 网页浏览器的渲染引擎
- 前端JavaScript框架（如React、Vue）
- XML解析器
7. 家谱树
生活例子：家族的血缘关系图，从祖先开始，分支到子女，再到孙辈等。
应用：
- 家谱研究软件
- 遗传学研究
- 社交网络中的关系图
8. 编译器的语法分析树
生活例子：理解一个复杂的句子，我们会分析其主语、谓语、宾语等成分，这个过程类似于编译器构建语法树。
技术实现：编译器将源代码解析为语法树，然后进行语义分析和代码生成。
应用：
- 各种编程语言的编译器
- 自然语言处理
- 表达式求值
9. 路由算法
生活例子：导航软件寻找从起点到终点的最佳路线，考虑各种可能的路径。
技术实现：路由算法使用树结构来表示可能的路径，并使用诸如Dijkstra或A*等算法来找到最短路径。
应用：
- GPS导航系统
- 网络路由
- 游戏中的寻路算法
10. 压缩算法
生活例子：摩尔斯电码根据字符出现的频率分配不同长度的编码，常用字符使用较短的编码。
技术实现：霍夫曼编码使用二叉树来为字符分配变长编码，实现数据压缩。
应用：
- 文件压缩软件（如ZIP、GZIP）
- 图像压缩（如JPEG）
- 视频压缩（如MPEG）