下载掌阅APP，畅读海量书库
立即打开
二分搜索树（BST）是一种有序的内存数据结构，可以用来高效地进行键值查找。二分搜索树由多个节点组成，每个树节点由一个键、一个与该键关联的值以及两个子节点指针（因此称为二分）组成。二分搜索树从称为根节点的单一节点开始。一棵二分搜索树中只能有一个根节点。图2-1展示了一个二分搜索树的示例。
每个节点将搜索空间分为左子树和右子树，如图2-2所示：一个节点的键大于其左子树中存储的任何键，且小于其右子树中存储的任何键[SEDGEWICK11]。
图2-1：二分搜索树
图2-2：二分树节点的约束条件
在图2-2中，从根节点开始一直沿着节点的左指针向下可以到达叶子层（该层的节点没有子节点）的一个节点，此节点持有树中最小键以及与其关联的值。类似地，沿着右指针往下可以找到持有树中最大键以及与其关联的值的节点。另外，这种结构允许将值存储在树中的所有节点中。对于从根节点开始的搜索，如果在更高的层上找到了搜索到的键，则搜索可能在到达树的底部之前终止。
插入操作并不会遵循任何特定模式，元素插入可能导致树不平衡的情况（即它的一个分支比另一个分支长）。最差的情况如图2-3b所示，我们最终得到一棵病态树（pathological tree），它看起来更像一个链表，此时我们得到的不是期望的对数时间复杂度（图2-3a），而是线性时间复杂度。
图2-3：平衡树（a）和不平衡或病态树（b）示例
这个例子可能稍微有点夸张，但它说明了为什么树需要平衡：尽管所有的数据项不太可能最终都存放在了树的一侧，但至少其中一些数据项肯定会放在树的某一侧，而这便会显著降低搜索速度。
平衡树指的是高度为log
2
N的树（其中N是树中数据项的总数），并且两个子树之间的高度差不大于1[KNUTH98]
。如果不进行平衡，我们将失去二分搜索树结构的性能优势，使得树的最终形状由插入和删除的顺序来确定。
在平衡树中，沿着左指针或右指针移动会将搜索空间平均减少一半，因此查找复杂度是对数的：O(log 2 N)。如果树不平衡，则最差情况的时间复杂度就会上升到O(N)，因为我们可能会处于所有元素都在树的一侧的情况。
为了防止在一个分支保持为空的时候还在另一个分支上增加新的元素使之变得更长（如图2-3b所示），我们可以在每次操作之后对树进行平衡。树的平衡是通过以最小化树高并将每一边的节点数保持在界限内的方式重新组织节点来完成的。
保持树的平衡的方法之一是在添加或删除节点后执行旋转：如果插入操作使分支不平衡（分支中的两个连续节点只有一个子节点），则可以围绕中间节点旋转树。在图2-4所示的示例中，旋转后中间节点（3）（称为旋转轴）被提升了一层，这样一来其父节点就成为其右子节点。
图2-4：旋转步骤的示例
如前所述，不平衡树的最差情况的时间复杂度为O(N)。平衡树的平均时间复杂度是O(log 2 N)。同时，由于扇出较低（扇出是指每个节点允许拥有的最大子节点数），我们必须相当频繁地执行平衡操作、重新定位节点并更新指针。维护成本的增加使得二分搜索树作为存储在磁盘上的数据结构变得不切实际[NIEVERGELT74]。
如果我们想在磁盘上维护二分搜索树，则将面临如下几个问题。一个问题是局部性：由于元素是以随机顺序添加的，所以不能保证新创建的节点是在其父节点附近写入的，这意味着节点子指针可能跨越多个磁盘页。通过修改树的布局和使用分页二分树，我们可以在一定程度上改善这种情况（参见2.2.3节）。
另一个与游历子指针的开销密切相关的问题是树高。由于二分树的扇出为2，所以树的高度是树中元素个数的以2为底的对数。我们必须执行O(log 2 N)次查找以定位要搜索的元素，这就要求执行相同数量的磁盘传输。2-3树和其他低扇出树具有类似的限制：虽然它们作为内存数据结构是有用的，但是较小的节点大小使得它们在外部存储上并不实用[COMER79]。
一个在磁盘上存储二分搜索树的简单方法所需的磁盘寻道次数与比较次数一样多，因为这样的结构原生不具备数据局部性。这使得我们踏上一条寻找某个可以提供数据局部性的数据结构的道路。
考虑到这些因素，更适合磁盘实现的树必须具有以下属性：
·高扇出，以改善邻近键的数据局部性。
·低高度，以减少遍历期间的寻道次数。
扇出与高度呈负相关：扇出越高，高度便越低。如果扇出高，则每个节点可以容纳更多子节点，这降低了节点数量，进而降低了高度。