搜索树

搜索树以分层结构存储有序键，以便搜索、插入和删除操作遵循从根到叶的路径；自平衡变体通过保持该路径较短来保证对数时间复杂度的操作。

Definition

搜索树是一种树形数据结构，根据每个节点的排序不变式以排序顺序维护键，支持高效的搜索、插入、删除和基于顺序的查询；平衡搜索树还限制其形状，使高度保持为键数量的对数。

Scope

本主题涵盖基于树的有序字典结构：二叉搜索树及其排序不变式、限制高度的自平衡方案（AVL树、红黑树等），以及为外部存储设计的B树等多路平衡树。它讨论了这些结构除了简单查找之外还支持的操作——前驱、后继、范围查询和有序遍历——并将其与不保留顺序的哈希表进行对比。

Core questions

• 二叉搜索树的排序不变式如何使搜索成为从根到叶的遍历？
• 为什么非平衡树会退化到线性时间，以及平衡如何防止这种情况发生？
• 哪些旋转或结构规则能保持AVL树和红黑树的平衡？
• 为什么B树比二叉树更适合磁盘和数据库存储？
• 与哈希表相比，何时值得为保持顺序的操作付出额外成本？

Key concepts

• 二叉搜索树不变式
• 树旋转
• AVL树
• 红黑树
• B树
• 树高与平衡
• 中序遍历
• 范围和后继查询

Key theories

高度平衡保证对数操作

通过旋转或结构规则保持平衡不变式，自平衡树将高度保持在O(log n)，无论输入顺序如何，都能保证最坏情况下O(log n)的搜索、插入和删除操作。

用于外部存储的多路树

B树每个节点存储多个键以匹配磁盘块大小，从而最大限度地减少缓慢的外部内存访问次数；这使得它们成为数据库和文件系统的标准结构。

Clinical relevance

搜索树对于需要有序访问的系统至关重要：红黑树在标准库中实现了有序映射和集合，B树及其变体是关系数据库和文件系统中的主要索引结构，平衡树支持范围查询、区间调度和几何搜索结构。

History

AVL树是第一个自平衡二叉搜索树，由Adelson-Velsky和Landis于1962年引入。Bayer和McCreight于1972年为大型有序索引引入了B树，Guibas和Sedgewick于1978年开发了红黑树作为一种实用的平衡方案，成为许多标准库实现的基础。

Key figures

• Georgy Adelson-Velsky
• Evgenii Landis
• Rudolf Bayer
• Robert Sedgewick
• Robert Tarjan

Seminal works

• bayer1972
• cormen2009

Frequently asked questions

为什么不总是使用哈希表而不是搜索树？

哈希表提供更快的平均查找速度，但没有排序功能。搜索树保持键的排序，支持范围查询、有序迭代以及O(log n)时间复杂度的前驱/后继查找，这是哈希表无法高效完成的。选择取决于顺序是否重要。

为什么数据库使用B树而不是二叉搜索树？

B树将许多键打包到每个节点中，以匹配磁盘块的大小，因此相同键数量的二叉树相比，B树的搜索触及的缓慢外部内存块要少得多。这最大限度地减少了I/O，而I/O在数据库和文件系统中是影响性能的主要因素。