4.7 示例：二叉搜索树 (Example: Binary Search Tree)

由于 sort 本身系统就有了，极少需要在 Common Lisp 里编写排序程序。本节将演示如何解决一个与此相关的问题，这个问题尚未有现成的解决方案：维护一个已排序的对象集合。本节的代码会把对象存在二叉搜索树里（ binary search tree ）或称作 BST。当二叉搜索树平衡时，允许我们可以在与时间成 log n 比例的时间内，来寻找、添加或是删除元素，其中 n 是集合的大小。

../_images/Figure-4.4.png

图 4.4: 二叉搜索树

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

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

  1. (defstruct (node (:print-function
  2.                   (lambda (n s d)
  3.                     (format s "#<~A>" (node-elt n)))))
  4.   elt (l nil) (r nil))
  6. (defun bst-insert (obj bst <)
  7.   (if (null bst)
  8.       (make-node :elt obj)
  9.       (let ((elt (node-elt bst)))
  10.         (if (eql obj elt)
  11.             bst
  12.             (if (funcall < obj elt)
  13.                 (make-node
  14.                    :elt elt
  15.                    :l (bst-insert obj (node-l bst) <)
  16.                    :r (node-r bst))
  17.                 (make-node
  18.                    :elt elt
  19.                    :r (bst-insert obj (node-r bst) <)
  20.                    :l (node-l bst)))))))
  22. (defun bst-find (obj bst <)
  23.   (if (null bst)
  24.       nil
  25.       (let ((elt (node-elt bst)))
  26.         (if (eql obj elt)
  27.             bst
  28.             (if (funcall < obj elt)
  29.                 (bst-find obj (node-l bst) <)
  30.                 (bst-find obj (node-r bst) <))))))
  32. (defun bst-min (bst)
  33.   (and bst
  34.        (or (bst-min (node-l bst)) bst)))
  36. (defun bst-max (bst)
  37.   (and bst
  38.        (or (bst-max (node-r bst)) bst)))

图 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 #'<)))
  5. NIL

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

我们可以使用 bst-find 来找到二叉搜索树中的对象，它与 bst-insert 接受同样的参数。先前叙述所提到的 node 结构，它像是一个具有两个 cdr 的 cons 核。如果我们把 16 页的 our-member 拿来与 bst-find 比较的话，这样的类比更加明确。

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

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

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

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

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

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

  1. (defun bst-remove (obj bst <)
  2.   (if (null bst)
  3.       nil
  4.       (let ((elt (node-elt bst)))
  5.         (if (eql obj elt)
  6.             (percolate bst)
  7.             (if (funcall < obj elt)
  8.                 (make-node
  9.                    :elt elt
  10.                    :l (bst-remove obj (node-l bst) <)
  11.                    :r (node-r bst))
  12.                 (make-node
  13.                    :elt elt
  14.                    :r (bst-remove obj (node-r bst) <)
  15.                    :l (node-l bst)))))))
  17. (defun percolate (bst)
  18.   (cond ((null (node-l bst))
  19.          (if (null (node-r bst))
  20.              nil
  21.              (rperc bst)))
  22.         ((null (node-r bst)) (lperc bst))
  23.         (t (if (zerop (random 2))
  24.                (lperc bst)
  25.                (rperc bst)))))
  27. (defun rperc (bst)
  28.   (make-node :elt (node-elt (node-r bst))
  29.              :l (node-l bst)
  30.              :r (percolate (node-r bst))))

图 4.6 二叉搜索树：移除

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

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

  1. > (setf nums (bst-remove 2 nums #'<))
  2. #<5>
  3. > (bst-find 2 nums #'<)
  4. NIL

此时 nums 的结构应该如图 4.7 所示。 （另一个可能性是 1 取代了 2 的位置。）

../_images/Figure-4.7.png

图 4.7: 二叉搜索树

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

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

  1. (defun bst-traverse (fn bst)
  2.   (when bst
  3.     (bst-traverse fn (node-l bst))
  4.     (funcall fn (node-elt bst))
  5.     (bst-traverse fn (node-r bst))))

图 4.8 二叉搜索树：遍历

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

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

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

本节所给出的代码，提供了一个二叉搜索树实现的脚手架。你可能想根据应用需求，来充实这个脚手架。举例来说，这里所给出的代码每个节点只有一个 elt 字段；在许多应用里，有两个字段会更有意义， key 与 value 。本章的这个版本把二叉搜索树视为集合看待，从这个角度看，重复的插入是被忽略的。但是代码可以很简单地改动，来处理重复的元素。

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