11. 二叉搜索树¶
11.1. 二叉搜索树的定义¶
二叉搜索树 （ BST ）是一种满足下列条件（称为 二叉搜索树性质 ）的 二叉树 ：所有存储在 键 值为 \(K\) 的结点的左子树中的 结点 ，其键值均小于或等于 \(K\) ；所有存储在键值为 \(K\) 的结点的右子树中的结点，其键值均大于 \(K\) 。图 7.11.1 展示了针对同一组值的两个 BST。二叉搜索树性质的一个推论是：若使用 中序遍历 输出 BST 的结点，所得到的枚举将按从小到大的顺序排列。
下面是 BST 的类声明。
回想一下，处理 键 以及
记录的比较 有多种方式，
三种典型做法分别是：采用 键值对 、
使用诸如 Comparator 类之类的特殊比较方法，
或者传入一个 比较器函数 。
我们的 BST 实现要求记录实现 Comparable 接口。
// Binary Search Tree implementation
class BST {
private BSTNode root; // Root of the BST
private int nodecount; // Number of nodes in the BST
// constructor
BST() { root = null; nodecount = 0; }
// Reinitialize tree
public void clear() { root = null; nodecount = 0; }
// Insert a record into the tree.
// e: The record to insert.
public void insert(int e) {
root = inserthelp(root, e);
nodecount++;
}
// Remove a record from the tree
// key: The key value of record to remove
// Returns the record removed, null if there is none.
public int remove(int key) {
int temp = findhelp(root, key); // First find it
if (temp != -1) {
root = removehelp(root, key); // Now remove it
nodecount--;
}
return temp;
}
// Return the record with key value k, null if none exists
// key: The key value to find
public int find(int key) { return findhelp(root, key); }
// Return the number of records in the dictionary
public int size() { return nodecount; }
// Binary Search Tree implementation
class BST<E extends Comparable<E>> {
private BSTNode<E> root; // Root of the BST
private int nodecount; // Number of nodes in the BST
// constructor
BST() { root = null; nodecount = 0; }
// Reinitialize tree
public void clear() { root = null; nodecount = 0; }
// Insert a record into the tree.
// Records can be anything, but they must be Comparable
// e: The record to insert.
public void insert(E e) {
root = inserthelp(root, e);
nodecount++;
}
// Remove a record from the tree
// key: The key value of record to remove
// Returns the record removed, null if there is none.
public E remove(E key) {
E temp = findhelp(root, key); // First find it
if (temp != null) {
root = removehelp(root, key); // Now remove it
nodecount--;
}
return temp;
}
// Return the record with key value k, null if none exists
// key: The key value to find
public E find(E key) { return findhelp(root, key); }
// Return the number of records in the dictionary
public int size() { return nodecount; }
11.1.1. 二叉搜索树的查找¶
我们要详细讨论的第一个操作，是查找与给定键匹配的记录。
注意，在 BST 类中，公有成员函数 find 调用私有成员函数
findhelp 。
方法 find 以查找键为显式参数、以其 BST 为隐式参数，
返回与该键匹配的记录。
不过，查找操作最容易实现为一个递归函数，
其参数是某棵子树的根和查找键。
成员 findhelp 正是这种递归子例程所需的形式，
其实现如下。
11.2. 二叉搜索树的插入¶
下面来看如何在 BST 中插入一个新结点。
注意，除了路径上的最后一个结点，
inserthelp 实际上不会改变所访问的任何结点的子结点指针。
从这个意义上说，其中许多赋值看似多余。
但是，为保持插入过程简单，
这些额外赋值的代价是值得付出的。
另一种做法是检查某次赋值是否必要，
而这很可能比赋值本身代价更高！
当要插入的结点的键值与树中已有某结点的键相同时， 我们必须决定如何处理。 如果在插入过程中发现了与待插入键值重复的结点， 那么有两个选择。 如果应用不允许键相同的结点， 那么这次插入应被视为错误（或者忽略）。 如果允许键重复， 我们的约定是把重复的结点插入左子树。
BST 的形状取决于元素插入的次序。 新元素作为新的叶结点加入 BST， 可能增大树的深度。 图 7.11.1 展示了一组数值对应的两棵 BST。 含 \(n\) 个结点的 BST 也可能成为一条高度为 \(\Theta(n)\) 的结点链。 例如，如果所有元素都按排序后的次序插入， 就会出现这种情况。 一般而言，BST 越浅越好， 这样能使 BST 操作的平均代价保持在较低水平。
11.3. 二叉搜索树的删除¶
从 BST 中删除结点比插入结点要麻烦一些， 但只要把各种可能情况逐一考虑，它并不复杂。 在着手处理一般的结点删除过程之前， 我们先来看如何从给定子树中删除键值最大的结点。 这个例程稍后将由一般的结点删除函数使用。
deletemax 方法的返回值是当前结点的子树，
其中值最大的结点已被移除。
与 inserthelp 方法类似，
回溯到根的路径上的每个结点，
其右子结点指针都被重新赋值为它调用 deletemax 方法
所产生的子树。
一个有用的配套方法是 getmax ，
它返回指向子树中包含最大值的结点的指针。
// Get the maximum valued element in a subtree
private BSTNode getmax(BSTNode rt) {
if (rt.right() == null) return rt;
return getmax(rt.right());
}
// Get the maximum valued element in a subtree
private BSTNode<E> getmax(BSTNode<E> rt) {
if (rt.right() == null) { return rt; }
return getmax(rt.right());
}
现在可以来看 removehelp 方法了。
从 BST 中删除给定键值为 \(R\) 的结点，
需要先找到 \(R\) ，然后把它从树中删除。
因此，删除操作的第一部分是查找 \(R\) 。
找到 \(R\) 之后，有几种可能的情况。
如果 \(R\) 没有子结点，
那么 \(R\) 的父结点的指针被置为 NULL。
如果 \(R\) 只有一个子结点，
那么 \(R\) 的父结点的指针被置为指向 \(R\) 的子结点
（与 deletemax 类似）。
问题出在 \(R\) 有两个子结点的时候。
一个简单但代价高昂的做法是，
让 \(R\) 的父结点指向 \(R\) 的某棵子树，
然后把另一棵子树的结点逐一重新插入。
更好的替代方案是，
在其中一棵子树里找一个能替代 \(R\) 中值的值。
于是，问题就变成： 哪个值可以替代被删除的值？ 任取一个值是不行的， 因为我们必须在不大幅改变树结构的前提下保持 BST 性质。 哪个值与被删除的值最相近？ 答案是比被删除值大的最小键值， 或者是比被删除值小（或相等）的最大键值。 用这两个值中的任何一个替换被删除的值， 都能保持 BST 性质。
当树中不出现重复的结点值时， 替换值取自左子树的最大值还是右子树的最小值并没有区别。 如果重复值存储在左子树中， 那么就必须从 左 子树中选取替换值。 [1] 要弄清原因，设右子树中的最小值为 \(L\) 。 如果右子树中有多个结点的值为 \(L\) ， 选取 \(L\) 作为该子树根的替换值， 将使树中在现在包含 \(L\) 的结点的右侧出现相等的值。 选取左子树中的最大值则没有类似问题， 因为左子树中出现相等的值并不违反二叉搜索树性质。
11.4. 二叉搜索树的分析¶
findhelp 和 inserthelp 的代价是被找到或被插入结点的
深度。
removehelp 的代价是被删除结点的深度；
当该结点有两个子结点时，
代价是其右子树中值最小结点的深度。
因此，在最坏情况下，
这些操作中任何一个的代价都是树中最深结点的深度。
这正是我们希望 BST 保持 平衡 的原因，
也就是说，高度尽可能小。
如果二叉树是平衡的，
那么含 \(n\) 个结点的树的高度约为 \(\log n\) 。
然而，如果树完全不平衡（例如呈链表形状），
那么含 \(n\) 个结点的树的高度可以高达 \(n-1\) 。
因此，平衡的 BST 在平均情况下的操作代价为
\(\Theta(\log n)\) ，
而严重不平衡的 BST 在最坏情况下的操作代价可达
\(\Theta(n)\) 。
考虑这样的情形：我们逐条插入记录，
构造一棵含 \(n\) 个结点的 BST。
如果幸运，记录到达的次序恰好使树保持平衡
（"随机"的次序对这一目的很可能就足够好了），
那么每次插入的平均代价为 \(\Theta(\log n)\) ，
总代价为 \(\Theta(n \log n)\) 。
然而，如果记录按值递增的次序插入，
那么得到的树将是一条高度为 \(n-1\) 的链。
这种情况下插入的代价将是
\(\sum_{i=1}^{n} i = \Theta(n^2)\) 。
无论树的形状如何，遍历一棵 BST 的代价都是 \(\Theta(n)\) 。 每个结点恰好被访问一次， 每条子结点指针恰好被跟随一次。
下面是一个名为 printhelp 的遍历示例。
它对 BST 执行中序遍历，按值升序打印各结点的值。
private void printhelp(BSTNode rt) {
if (rt == null) return;
printhelp(rt.left());
printVisit(rt.value());
printhelp(rt.right());
}
private void printhelp(BSTNode<E> rt) {
if (rt == null) { return; }
printhelp(rt.left());
printVisit(rt.value());
printhelp(rt.right());
}
BST 实现简单，在树平衡时也很高效， 但树可能失衡这一点是它的严重隐患。 有一些组织 BST 的技术可以保证良好的性能， 例如 AVL 树 和 伸展树 。 此外还存在其他一些保证保持平衡的搜索树， 例如 2-3 树 。
