图 4.4: 二叉搜索树

    二叉搜索树是一种二叉树，给定某个排序函数，比如 < ，每个元素的左子树都 < 该元素，而该元素 < 其右子树。图 4.4 展示了根据 < 排序的二叉树。

    图 4.5 包含了二叉搜索树的插入与寻找的函数。基本的数据结构会是 node （节点），节点有三个部分：一个字段表示存在该节点的对象，以及各一个字段表示节点的左子树及右子树。可以把节点想成是有一个 car 和两个 cdr 的一个 cons 核（cons cell）。

    图 4.5 二叉搜索树：查询与插入

    一棵二叉搜索树可以是 nil 或是一个左子、右子树都是二叉搜索树的节点。如同列表可由连续调用 cons 来构造，二叉搜索树将可以通过连续调用 bst-insert 来构造。这个函数接受一个对象，一棵二叉搜索树及一个排序函数，并返回将对象插入的二叉搜索树。和 cons 函数一样， bst-insert 不改动做为第二个实参所传入的二叉搜索树。以下是如何使用这个函数来构造一棵叉搜索树：

    1. > (setf nums nil)
    2. NIL
    3. > (dolist (x '(5 8 4 2 1 9 6 7 3))
    4.     (setf nums (bst-insert x nums #'<)))

    图 4.4 显示了此时 的结构所对应的树。

    与 member 相同， bst-find 不仅返回要寻找的元素，也返回了用寻找元素做为根节点的子树：

    这使我们可以区分出无法找到某个值，以及成功找到 nil 的情况。

    要找到二叉搜索树的最小及最大的元素是很简单的。要找到最小的，我们沿着左子树的路径走，如同 bst-min 所做的。要找到最大的，沿着右子树的路径走，如同 bst-max 所做的：

    1. > (bst-min nums)
    2. #<1>
    3. > (bst-max nums)
    4. #<9>

    要从二叉搜索树里移除元素一样很快，但需要更多代码。图 4.6 演示了如何从二叉搜索树里移除元素。

    图 4.6 二叉搜索树：移除

    勘误: 此版 bst-remove 的定义已被汇报是坏掉的，请参考 获得修复版。

    函数 bst-remove 接受一个对象，一棵二叉搜索树以及排序函数，并返回一棵与本来的二叉搜索树相同的树，但不包含那个要移除的对象。和 remove 一样，它不改动做为第二个实参所传入的二叉搜索树：

    2. > (bst-find 2 nums #'<)
    3. NIL

    ../_images/Figure-4.7.png

    图 4.7: 二叉搜索树

    移除需要做更多工作，因为从内部节点移除一个对象时，会留下一个空缺，需要由其中一个孩子来填补。这是 percolate 函数的用途。当它替换一个二叉搜索树的树根（topmost element）时，会找其中一个孩子来替换，并用此孩子的孩子来填补，如此这般一直递归下去。

    为了要保持树的平衡，如果有两个孩子时， perlocate 随机择一替换。表达式 (random 2) 会返回 0 或 1 ，所以 (zerop (random 2)) 会返回真或假。

    图 4.8 二叉搜索树：遍历

    一旦我们把一个对象集合插入至二叉搜索树时，中序遍历会将它们由小至大排序。这是图 4.8 中， bst-traverse 函数的用途：

    1. > (bst-traverse #'princ nums)
    2. NIL

    （函数 princ 仅显示单一对象）

    二叉搜索树不仅是维护一个已排序对象的集合的方法。他们是否是最好的方法，取决于你的应用。一般来说，二叉搜索树最适合用在插入与删除是均匀分布的情况。有一件二叉搜索树不擅长的事，就是用来维护优先队列（priority queues）。在一个优先队列里，插入也许是均匀分布的，但移除总是在一个另一端。这会导致一个二叉搜索树变得不平衡，而我们期望的复杂度是 插入与移除操作，将会变成 O(n) 。如果用二叉搜索树来表示一个优先队列，也可以使用一般的列表，因为二叉搜索树最终会作用的像是个列表。