零基础数据结构与算法——第三章：高级数据结构-树（下）
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）
