ApX 标志ApX 标志

趋近智

大模型显存计算器硬件课程定价
ApX 标志ApX 标志

趋近智

大模型显存计算器硬件课程定价

所有课程

机器学习的数据结构与算法
章节 1: 入门:机器学习中的数据结构与算法
数据结构对机器学习性能为何重要
机器学习实践者的复杂性分析
Python的内置结构在机器学习工作流中的应用
NumPy 数组:机器学习数值处理的根本
Pandas DataFrame 用于数据准备
机器学习问题与数据结构的对应
实践:分析基本数据操作
第 1 章测验
章节 2: 树结构:搜索、索引与建模
树结构的基本知识
用于高效查找的二叉搜索树
平衡树的重要性
决策树:结构与算法
树集成方法:随机森林与梯度提升
树遍历技术
动手实践:实现树操作
第 2 章测验
章节 3: 散列在特征工程和相似搜索中的应用
哈希函数与哈希表
处理哈希冲突
特征哈希用于降维
局部敏感哈希(LSH)介绍
在 Python 中实现基于哈希的数据结构
散列的性能权衡
实践:哈希技术的实现
第 3 章测验
章节 4: 图:关系数据与网络模型
图的表示方法:邻接列表与邻接矩阵
图遍历:广度优先搜索(BFS)
图遍历:深度优先搜索(DFS)
最短路径算法概述
图嵌入用于节点表示
推荐系统和自然语言处理中的应用
动手实践:图表示与遍历
第 4 章测验
章节 5: 优化任务中的优先队列与堆
堆数据结构属性
堆的核心操作
使用堆实现优先级队列
在选择问题中的应用
复杂算法的支持作用
Python 的 heapq 模块
实践:使用堆进行选择
第 5 章测验
章节 6: 机器学习中的核心算法策略
分治法
动态规划原理
优化中的贪心算法
提升鲁棒性的随机算法
迭代优化算法
算法策略与机器学习模型实现的关联
实践:识别机器学习库中的策略
第 6 章测验

平衡树的重要性

二叉搜索树(BST)对搜索、插入和删除等基本操作提供了 O(log⁡n)O(\log n)O(logn) 的平均时间复杂度。这种效率源于它们在每一步将搜索空间减半的能力,但这个优势依赖于一个重要假设:树保持相对平衡。

当这个假设不成立时会发生什么?考虑按严格升序(例如1、2、3、4、5、6、7)将元素插入到二叉搜索树中。生成的树结构不会是茂密且平衡的;相反,它会退化成一个类似链表的结构。每个新节点都成为前一个节点的右子节点。

通过按顺序插入键 [1, 2, 3, 4, 5, 6, 7] 形成的退化二叉搜索树。

在这种最坏情况下,搜索元素7需要访问树中的每一个节点。树的高度变为节点数 nnn,搜索、插入和删除的时间复杂度会退化到 O(n)O(n)O(n)。这不比在一个未排序的列表中搜索更好!

这表明树的高度与其操作效率之间有直接关联。平衡树旨在使其高度尽可能接近 O(log⁡n)O(\log n)O(logn),无论插入顺序如何。

保持平衡:自平衡树

为了解决标准BST中 O(n)O(n)O(n) 最坏情况性能的可能性,发展出了各种自平衡二叉搜索树。这些结构在插入和删除过程中会自动调整其形状,以确保树保持相对平衡。

它们通过特定的结构限制以及称为旋转的重构操作来实现这一点。当插入或删除违反了平衡标准(不同树类型之间略有差异)时,会局部执行旋转以重新排列节点并恢复平衡特性。

常见的自平衡树类型包括:

  • AVL 树: 以其发明者(Adelson-Velsky 和 Landis)的名字命名,AVL 树通过确保任何节点的左右子树高度差至多为1来保持平衡。这种严格的条件确保了 O(log⁡n)O(\log n)O(logn) 的高度。
  • 红黑树: 这些树使用节点着色(红色或黑色)以及一组管理这些颜色的规则,以确保从根节点到任何叶节点的最长路径不超过最短路径的两倍。这也保证了 O(log⁡n)O(\log n)O(logn) 的高度,尽管它们在实际中可能比AVL树的平衡程度略低,但通常因为所需的旋转次数较少而导致更快的插入和删除操作。Python的内置字典(3.6版本之前)以及C++和Java中许多标准库的有序映射实现通常使用红黑树。

下图展示了同一组键 [1, 2, 3, 4, 5, 6, 7] 如何在平衡树(例如AVL树或红黑树,尽管没有展示具体的平衡逻辑)中构建。

包含键 [1, 2, 3, 4, 5, 6, 7] 的平衡二叉搜索树。其高度远小于退化树。

尽管AVL树和红黑树的内部机制涉及更复杂的实现细节(旋转、颜色翻转),但重要的是它们提供的保障:搜索、插入和删除等操作在最坏情况下仍保持 O(log⁡n)O(\log n)O(logn) 的时间复杂度。

这种有保障的性能使得平衡树在需要对动态数据集进行可靠、高效的搜索和更新操作时不可或缺,避免了简单BST在遇到非随机插入模式时的性能问题。尽管决策树等机器学习 (machine learning)模型不直接依赖BST的平衡特性(它们的结构是由特征分割而非键顺序决定的),但了解树平衡的重要性对于理解用于索引、搜索或作为算法和库内部组成部分的数据结构的效率是必要的。

  • Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, 2022 (MIT Press) - 这本经典教材全面涵盖了二叉搜索树、其不平衡时的性能问题,以及像红黑树这类自平衡结构的详细算法。
  • An algorithm for the organization of information, G. M. Adelson-Velsky and E. M. Landis, 1962 Soviet Mathematics - Doklady, Vol. 3 (Soviet Mathematics - Doklady) - 首次介绍AVL树的原始学术论文,AVL树是第一个自平衡二叉搜索树,概述了其基本结构和平衡机制。
  • Data Structures and Algorithms in Python, Michael T. Goodrich, Roberto Tamassia, and Michael H. Goldwasser, 2013 (John Wiley & Sons) - 清晰易懂地解释了二叉搜索树和各种自平衡树结构,包括AVL树和红黑树,并提供了实用实现见解。

© 2026 ApX Machine Learning