Skip to main content

1 / 4概念

Trees & Heaps

树用层次组织有序数据,堆用部分有序组织优先级。判断标准不是“平衡树更高级”,而是要不要范围查询、最坏情况能否接受、数据在内存还是磁盘、只需要最小/最大还是完整顺序。

1 概念​

1.1 一句话定义​

树是 n 个节点的无环连通层次结构;二叉搜索树(BST)用左小右大维持全序;平衡 BST 通过旋转把高度压在 O(log n);B 树/B+ 树用高扇出把高度压到 O(log_t n);堆是满足父节点优先于子节点的完全二叉树,只保证局部顺序。

1.2 它解决什么问题​

  • 有序查找:BST/平衡树支持查找、前驱后继、范围查询,哈希表做不到。
  • 最坏保证:AVL/红黑树把 O(n) 的退化链压回 O(log n),适合在线服务。
  • 磁盘索引:B+ 树把多个键放进一个页,降低树高和 I/O 次数,是数据库索引的默认结构。
  • 优先级:堆用 O(1) 取最小/最大,O(log n) 插入删除,是调度、Dijkstra、top-k 的基础。

没有树,有序操作只能排序后扫描;没有堆,优先队列只能用有序数组或每次重排。

1.3 不属于本页的内容​

主题去哪
数组、链表、栈、队列、哈希表Linear Structures
图的表示、拓扑排序、并查集Graph Structures
排序算法与二分Sorting & Searching
B+ 树在数据库中的执行计划Indexing & Optimization
堆在 Dijkstra/Prim 中的用法Graph Algorithms

1.4 关键术语​

术语含义容易混淆的点
高度 / 深度到叶子的最长路径 / 到根的路径不同教材对根的高度定义不同
完全二叉树除最后一层外全满,最后一层靠左不是“满二叉树”
平衡因子左右子树高度差AVL 限定为 -1/0/1
旋转不破坏中序的局部重构不是交换键值
黑高红黑树中从节点到叶子的黑节点数不是普通高度
阶 / 扇出B 树每个节点的子节点数范围不同教材用 t 或 m 表示
堆序父节点 ≤ 或 ≥ 子节点不是全局有序
上浮 / 下沉插入/删除后恢复堆序不是排序
建堆从无序数组构造堆不是逐个插入
前驱 / 后继中序下的相邻节点不是父子关系