12.5 示例：二叉搜索树 (Example: Binary Search Trees)

在某些情况下，使用破坏性操作比使用非破坏性的显得更自然。第 4.7 节中展示了如何维护一个具有二分搜索格式的有序对象集 (或者说维护一个二叉搜索树 (BST))。第 4.7 节中给出的函数都是非破坏性的，但在我们真正使用BST的时候，这是一个不必要的保护措施。本节将展示如何定义更符合实际应用的具有破坏性的插入函数和删除函数。

图 12.8 展示了如何定义一个具有破坏性的 bst-insert (第 72 页「译者注：第 4.7 节」)。相同的输入参数，能够得到相同返回值。唯一的区别是，它将修改作为第二个参数输入的 BST。 在第 2.12 节中说过，具有破坏性并不意味着一个函数调用具有副作用。的确如此，如果你想使用 bst-insert! 构造一个 BST，你必须像调用 bst-insert 那样调用它：

  1. > (setf *bst* nil)
  2. NIL
  3. > (dolist (x '(7 2 9 8 4 1 5 12))
  4. (setf *bst* (bst-insert! x *bst* #'<)))
  5. NIL
  1. (defun bst-insert! (obj bst <)
  2.   (if (null bst)
  3.       (make-node :elt obj)
  4.       (progn (bsti obj bst <)
  5.              bst)))
  7. (defun bsti (obj bst <)
  8.   (let ((elt (node-elt bst)))
  9.     (if (eql obj elt)
  10.         bst
  11.         (if (funcall < obj elt)
  12.             (let ((l (node-l bst)))
  13.               (if l
  14.                   (bsti obj l <)
  15.                   (setf (node-l bst)
  16.                         (make-node :elt obj))))
  17.             (let ((r (node-r bst)))
  18.               (if r
  19.                   (bsti obj r <)
  20.                   (setf (node-r bst)
  21.                         (make-node :elt obj))))))))

图 12.8: 二叉搜索树：破坏性插入

你也可以为 BST 定义一个类似 push 的功能，但这超出了本书的范围。(好奇的话，可以参考第 409 页 「译者注：即备注 204 」 的宏定义。)

与 bst-remove (第 74 页「译者注：第 4.7 节」) 对应，图 12.9 展示了一个破坏性版本的 bst-delete 。同 delete 一样，我们调用它并不是因为它的副作用。你应该像调用 bst-remove 那样调用 bst-delete ：

  1. > (setf *bst* (bst-delete 2 *bst* #'<) )
  2. #<7>
  3. > (bst-find 2 *bst* #'<)
  4. NIL
  1. (defun bst-delete (obj bst <)
  2.   (if bst (bstd obj bst nil nil <))
  3.   bst)
  5. (defun bstd (obj bst prev dir <)
  6.   (let ((elt (node-elt bst)))
  7.     (if (eql elt obj)
  8.         (let ((rest (percolate! bst)))
  9.           (case dir
  10.             (:l (setf (node-l prev) rest))
  11.             (:r (setf (node-r prev) rest))))
  12.       (if (funcall < obj elt)
  13.           (if (node-l bst)
  14.               (bstd obj (node-l bst) bst :l <))
  15.           (if (node-r bst)
  16.               (bstd obj (node-r bst) bst :r <))))))
  18. (defun percolate! (bst)
  19.   (cond ((null (node-l bst))
  20.          (if (null (node-r bst))
  21.              nil
  22.              (rperc! bst)))
  23.         ((null (node-r bst)) (lperc! bst))
  24.         (t (if (zerop (random 2))
  25.                (lperc! bst)
  26.                (rperc! bst)))))
  28. (defun lperc! (bst)
  29.   (setf (node-elt bst) (node-elt (node-l bst)))
  30.   (percolate! (node-l bst)))
  32. (defun rperc! (bst)
  33.   (setf (node-elt bst) (node-elt (node-r bst)))
  34.   (percolate! (node-r bst)))

图 12.9: 二叉搜索树：破坏性删除

译注: 此范例已被回报为错误的，一个修复的版本请造访这里。