为什么我的 Common Lisp 二进制搜索树功能不能正常工作？
Why is my Common Lisp Binary search tree function not working properly?
我必须创建一个能够检查二叉搜索树是否实际上是 BST 的 lisp 程序。
这是我做的：
(defun BST (lst)
(if (null lst) nil
(let ((curr (car lst)) (left (car (cdr lst))) (right (cdr (cdr lst))))
(cond
((and (null left) (null right)) t)
((and (numberp (car left)) (> (car left) curr)) nil)
((and (numberp (car right)) (<= (car right) curr)) nil)
((null right) (BST left))
((null left) (BST right))
(t (and (BST right) (BST left)))))))
(print (BST '(8 (3 (1 () ()) (6 (4 () ())(7 () ()))) (10 () (14 (13) ())))))
结果是 t，但是如果我将 10 编辑为小于 8 的值，结果仍然是 true。事实上，我的函数似乎完全忽略了树的右侧，只对 8 -> 3 -> 1 路径的变化做出反应。如有任何帮助，我们将不胜感激。
您的问题在于抽象。有none。
通过查看 let 解构，我猜节点是这样制作的：
(defun node (value &optional left right)
(list* value left right))
(node 1 (node 2) (node 4))
; ==> (1 (2 nil) 4 nil)
但是你路过的树似乎是用这个做的：
(defun node (value &optional left right)
(list value left right))
(node 1 (node 2) (node 4))
; ==> (1 (2 nil nil) (4 nil nil))
如何为二叉树建模并不重要。重要的是你所有的代码都使用相同的模型而不是不同的模型。这可以通过制作构造函数和吸气剂来完成。
首先，总是在 consy 结构上定义抽象，除非你明确地谈论 consy 结构。这真的很重要。
在 BST 的情况下，您需要一个函数来创建一个节点，然后是一些访问器。访问器可以完全通用。
(defgeneric make-bst-node-for-node (node value left right)
;; Make a node to serve as a child of NODE
)
(defgeneric bst-node-value (node))
(defmethod bst-node-value ((node cons))
(car node))
(defgeneric bst-node-left (node))
(defgeneric (setf bst-node-left) (new node))
(defgeneric bst-node-right (node))
(defgeneric (setf bst-node-right) (new node))
(defgeneric plausible-bst-node-p (maybe-node)
;; Is MAYBE-NODE basically plausible?
(:method (maybe-node)
(declare (ignorable maybe-node))
nil))
(defgeneric bst-node-components (node)
;; Return the components of a node as multiple values
(:method (node)
(values (bst-node-value node)
(bst-node-left node)
(bst-node-right node))))
;;; Consy BST nodes
;;;
(defun make-consy-bst-node (value left right)
;; A consy BST looks like (val . (left . right)), where left & right
;; are either BSTs or null.
`(,value . (,left . ,right)))
(defmethod make-bst-node-for-node ((node cons) value left right)
(make-consy-bst-node value left right))
(defmethod bst-node-left ((node cons))
(car (cdr node)))
(defmethod (setf bst-node-left) (new (node cons))
(setf (car (cdr node)) new))
(defmethod bst-node-right ((node cons))
(cdr (cdr node)))
(defmethod (setf bst-node-right) (new (node cons))
(setf (cdr (cdr node)) new))
(defmethod plausible-bst-node-p ((maybe-node cons))
(consp (cdr maybe-node)))
(defmethod bst-node-components ((node cons))
;; Efficiency hack (probably not worth it)
(let ((lr (cdr node)))
(values (car node) (car lr) (cdr lr))))
请注意，无法更改节点的值，因为我认为您永远不需要这样做。
有了这样的抽象，任何真正走 BST 的东西都可以用它们来做，而不是用我们都不得不费力研究的所有可怕的 1960 年代 Lisp 代码的风格，它完全由 (CAR (CDDR (CAR (CDAADR ...))))，其中大部分是最近 20 年写的。
此外，构建 BSTs 的大部分代码不需要知道它们的表示：一旦你创建了一个根节点，你就可以使用 make-bst-node-for-node为它制作children。
正是因为你没有定义抽象，结果从来没有理清结构应该是什么，你运行陷入了麻烦我认为：您的代码隐含地使用了与上面类似的表示，但是您为其提供的树隐含地使用了 (value left right) 的结构：不同的 表示。
为了让生活更轻松，我将定义几个采用 (value left right) 表示的函数，这种表示更具可读性但效率较低，并将其转换为 (value . (left . right)) 表示（注意这不使用 make-bst-node-for-node，因为它早于它而且我很懒）：
(defun make-consy-bst (value lb rb)
;; LB and RB are either null or are recursively processed
(make-consy-bst-node value
(if lb
(make-consy-bst (first lb) (second lb) (third lb))
nil)
(if rb
(make-consy-bst (first rb) (second rb) (third rb))
nil)))
(defun make-consy-bst* (thing)
(apply #'make-consy-bst thing))
现在你想要的是一个函数，给定一些声称是 BST 的东西来检查它是否是。嗯，这里有这样一个功能。请注意，这个函数本身使用了上面的抽象：这里没有明确的 car/cdr 追逐。这意味着它适用于任何类型的 BST。另请注意，此函数的实现有点曲折：它使用递归函数的一个有点肮脏的技巧，如果它发现不好的东西，returns 直接从它的 parent.
最后还请注意，此函数对于值是什么是不可知的：您可以将一个谓词告诉您这些值是否合法，以及一个排序谓词。
(defun bst-p (maybe-bst &key
(value-predicate #'realp)
(comparison-predicate #'<))
;; Return two values: either T and the BST, or NIL and the first
;; object which failed to be a BST.
(labels ((maybe-bst-value (thing)
;; Return the value of THING if it is a good BST.
;; If it's not give up at once
(unless (plausible-bst-node-p thing)
;; It not even slightly plausible
(return-from bst-p (values nil thing)))
(multiple-value-bind (value left right)
(bst-node-components thing)
(unless (funcall value-predicate value)
;; Value is not legal
(return-from bst-p (values nil thing)))
;; check the ordering if the children are not null,
;; giving up promptly if they are not
(when (not (null left))
(unless (funcall comparison-predicate
(maybe-bst-value left)
value)
(return-from bst-p (values nil thing))))
(when (not (null right))
(unless (funcall comparison-predicate
value
(maybe-bst-value right))
(return-from bst-p (values nil thing))))
value)))
;; It is slightly odd that the value is not used, but there is
;; nothing that says the value is not NIL
(maybe-bst-value maybe-bst)
(values t maybe-bst)))
我们可以试试这个：
> (bst-p (make-consy-bst* '(8 (3 (1 () ())
(6 (4 () ())
(7 () ())))
(10 ()
(14 (13 () ())
())))))
t
(8 (3 (1 nil) 6 (4 nil) 7 nil) 10 nil 14 (13 nil))
> (bst-p (make-consy-bst* '(8 (3 (1 () ())
(6 (4 () ())
(7 () ())))
(10 ()
(14 (13 () ())
(12 () ()))))))
nil
(14 (13 nil) 12 nil)
你可以看到它在第二种情况下失败了，因为 14 节点的两个 children 没有排序。
注意这段代码没有经过测试，真的，根本没有——我只是输入了大部分：可能有错误。
另请注意，在第一个版本中，我实际上实现了一种与我所说的不同的表示。
我认为问题是(let ((right (cdr (cdr lst)) ...)。与 car 不同，cdr 一个适当的列表保证 return 个列表。它 return 是缺点的第二个单元格，而不是列表的第二个项目。要仅使用 car 和 cdr，您需要将其更改为 (let ((right (car (cdr (cdr lst))))) ...)（写在纯文本框中，不确定括号是否匹配）。最好使用 first、second 和 third，将其重写为：
(let ((curr (first lst)) (left (second lst) (right (third lst)) ....
而且我确实认为有更好的方法来编写关于 BST 的代码，通过创建更合理的实用函数。
请研究这段代码：
(defun binary-search-tree-p (tree)
(if (null tree)
t
(destructuring-bind (value &optional left right) tree
(let ((left-val (car left))
(right-val (car right)))
(and (binary-search-tree-p left)
(binary-search-tree-p right)
(numberp value)
(or (null left)
(<= left-val value))
(or (null right)
(< value right-val)))))))
命名：函数命名清晰，使用-p约定表明它是一个谓词：one-argument布尔值来检验一些道理。参数是tree，不是list。顺便说一下，在 Common Lisp 中，list 是一个有效的变量名，它不会影响 list 函数。
null 大小写是 T 而不是 NIL。我们非常有必要声明一个空的 BST 是有效的，而不是无效的。如果一个空的 BST 是无效的，那么如果我们想要 one-node BST (42 nil nil) 是有效的，那么我们必须添加丑陋的任意规则，如果 BST 有空 children（这本身无效！）那么它本身就是有效的。
destructuring-bind 和 &optional 简化了用于分离树节点片段的代码。
我们首先验证 children 是 binary-search-tree-p。下一个检查是 (numberp value)。因此，如果一棵树为空，则它是有效的，但如果它不为空，则它必须具有数值。
解决了上面（4）中的一些重要问题，我们不必再使用numberp。如果我们知道 left 是有效的 BST，那么如果 left 不为空，则 (numberp left) 必须为真，因为这是递归检查的！我们在剩下的两个测试中利用了这一点：(or (null left) (<= (car left) value)): "Either the left tree is empty, or else we can trust that left tree's value to be number, and that number must not exceed the value at this node" 和类似的权利。
left 是 nil，(car left) 是安全的；但是，重要的是要承认我们的代码会由于访问 (car "abc") 而在 (42 "abc") 这样的树节点上崩溃。如果需要对这种情况具有鲁棒性，则需要一些额外的逻辑。
我假设由于您使用的是 <=，树中显然允许重复值。我进一步假设重复值 运行 向左。那么也就是说，在二分查找中，当遇到top-most个重复值时，剩下的那个值的重复值都在左子树中。如果需要，这很容易调整，使副本落在另一个方向。但是，请注意，在任何一种选择下，我们的测试都不必要地严格。也就是说，这其实是一个有效的二叉查找树，有重复项，被拒绝了，因为(< 5 5)右边失败：
5
5 5
4 5 7
6 8
合适的条件应该是：
...
(or (null left)
(<= left-val value))
(or (null right)
(<= value right-val))
我必须创建一个能够检查二叉搜索树是否实际上是 BST 的 lisp 程序。
这是我做的：
(defun BST (lst)
(if (null lst) nil
(let ((curr (car lst)) (left (car (cdr lst))) (right (cdr (cdr lst))))
(cond
((and (null left) (null right)) t)
((and (numberp (car left)) (> (car left) curr)) nil)
((and (numberp (car right)) (<= (car right) curr)) nil)
((null right) (BST left))
((null left) (BST right))
(t (and (BST right) (BST left)))))))
(print (BST '(8 (3 (1 () ()) (6 (4 () ())(7 () ()))) (10 () (14 (13) ())))))
结果是 t，但是如果我将 10 编辑为小于 8 的值，结果仍然是 true。事实上，我的函数似乎完全忽略了树的右侧，只对 8 -> 3 -> 1 路径的变化做出反应。如有任何帮助，我们将不胜感激。
您的问题在于抽象。有none。
通过查看 let 解构，我猜节点是这样制作的：
(defun node (value &optional left right)
(list* value left right))
(node 1 (node 2) (node 4))
; ==> (1 (2 nil) 4 nil)
但是你路过的树似乎是用这个做的：
(defun node (value &optional left right)
(list value left right))
(node 1 (node 2) (node 4))
; ==> (1 (2 nil nil) (4 nil nil))
如何为二叉树建模并不重要。重要的是你所有的代码都使用相同的模型而不是不同的模型。这可以通过制作构造函数和吸气剂来完成。
首先，总是在 consy 结构上定义抽象，除非你明确地谈论 consy 结构。这真的很重要。
在 BST 的情况下，您需要一个函数来创建一个节点，然后是一些访问器。访问器可以完全通用。
(defgeneric make-bst-node-for-node (node value left right)
;; Make a node to serve as a child of NODE
)
(defgeneric bst-node-value (node))
(defmethod bst-node-value ((node cons))
(car node))
(defgeneric bst-node-left (node))
(defgeneric (setf bst-node-left) (new node))
(defgeneric bst-node-right (node))
(defgeneric (setf bst-node-right) (new node))
(defgeneric plausible-bst-node-p (maybe-node)
;; Is MAYBE-NODE basically plausible?
(:method (maybe-node)
(declare (ignorable maybe-node))
nil))
(defgeneric bst-node-components (node)
;; Return the components of a node as multiple values
(:method (node)
(values (bst-node-value node)
(bst-node-left node)
(bst-node-right node))))
;;; Consy BST nodes
;;;
(defun make-consy-bst-node (value left right)
;; A consy BST looks like (val . (left . right)), where left & right
;; are either BSTs or null.
`(,value . (,left . ,right)))
(defmethod make-bst-node-for-node ((node cons) value left right)
(make-consy-bst-node value left right))
(defmethod bst-node-left ((node cons))
(car (cdr node)))
(defmethod (setf bst-node-left) (new (node cons))
(setf (car (cdr node)) new))
(defmethod bst-node-right ((node cons))
(cdr (cdr node)))
(defmethod (setf bst-node-right) (new (node cons))
(setf (cdr (cdr node)) new))
(defmethod plausible-bst-node-p ((maybe-node cons))
(consp (cdr maybe-node)))
(defmethod bst-node-components ((node cons))
;; Efficiency hack (probably not worth it)
(let ((lr (cdr node)))
(values (car node) (car lr) (cdr lr))))
请注意，无法更改节点的值，因为我认为您永远不需要这样做。
有了这样的抽象，任何真正走 BST 的东西都可以用它们来做，而不是用我们都不得不费力研究的所有可怕的 1960 年代 Lisp 代码的风格，它完全由 (CAR (CDDR (CAR (CDAADR ...))))，其中大部分是最近 20 年写的。
此外，构建 BSTs 的大部分代码不需要知道它们的表示：一旦你创建了一个根节点，你就可以使用 make-bst-node-for-node为它制作children。
正是因为你没有定义抽象，结果从来没有理清结构应该是什么，你运行陷入了麻烦我认为：您的代码隐含地使用了与上面类似的表示，但是您为其提供的树隐含地使用了 (value left right) 的结构：不同的 表示。
为了让生活更轻松，我将定义几个采用 (value left right) 表示的函数，这种表示更具可读性但效率较低，并将其转换为 (value . (left . right)) 表示（注意这不使用 make-bst-node-for-node，因为它早于它而且我很懒）：
(defun make-consy-bst (value lb rb)
;; LB and RB are either null or are recursively processed
(make-consy-bst-node value
(if lb
(make-consy-bst (first lb) (second lb) (third lb))
nil)
(if rb
(make-consy-bst (first rb) (second rb) (third rb))
nil)))
(defun make-consy-bst* (thing)
(apply #'make-consy-bst thing))
现在你想要的是一个函数，给定一些声称是 BST 的东西来检查它是否是。嗯，这里有这样一个功能。请注意，这个函数本身使用了上面的抽象：这里没有明确的 car/cdr 追逐。这意味着它适用于任何类型的 BST。另请注意，此函数的实现有点曲折：它使用递归函数的一个有点肮脏的技巧，如果它发现不好的东西，returns 直接从它的 parent.
最后还请注意，此函数对于值是什么是不可知的：您可以将一个谓词告诉您这些值是否合法，以及一个排序谓词。
(defun bst-p (maybe-bst &key
(value-predicate #'realp)
(comparison-predicate #'<))
;; Return two values: either T and the BST, or NIL and the first
;; object which failed to be a BST.
(labels ((maybe-bst-value (thing)
;; Return the value of THING if it is a good BST.
;; If it's not give up at once
(unless (plausible-bst-node-p thing)
;; It not even slightly plausible
(return-from bst-p (values nil thing)))
(multiple-value-bind (value left right)
(bst-node-components thing)
(unless (funcall value-predicate value)
;; Value is not legal
(return-from bst-p (values nil thing)))
;; check the ordering if the children are not null,
;; giving up promptly if they are not
(when (not (null left))
(unless (funcall comparison-predicate
(maybe-bst-value left)
value)
(return-from bst-p (values nil thing))))
(when (not (null right))
(unless (funcall comparison-predicate
value
(maybe-bst-value right))
(return-from bst-p (values nil thing))))
value)))
;; It is slightly odd that the value is not used, but there is
;; nothing that says the value is not NIL
(maybe-bst-value maybe-bst)
(values t maybe-bst)))
我们可以试试这个：
> (bst-p (make-consy-bst* '(8 (3 (1 () ())
(6 (4 () ())
(7 () ())))
(10 ()
(14 (13 () ())
())))))
t
(8 (3 (1 nil) 6 (4 nil) 7 nil) 10 nil 14 (13 nil))
> (bst-p (make-consy-bst* '(8 (3 (1 () ())
(6 (4 () ())
(7 () ())))
(10 ()
(14 (13 () ())
(12 () ()))))))
nil
(14 (13 nil) 12 nil)
你可以看到它在第二种情况下失败了，因为 14 节点的两个 children 没有排序。
注意这段代码没有经过测试，真的，根本没有——我只是输入了大部分：可能有错误。
另请注意，在第一个版本中，我实际上实现了一种与我所说的不同的表示。
我认为问题是(let ((right (cdr (cdr lst)) ...)。与 car 不同，cdr 一个适当的列表保证 return 个列表。它 return 是缺点的第二个单元格，而不是列表的第二个项目。要仅使用 car 和 cdr，您需要将其更改为 (let ((right (car (cdr (cdr lst))))) ...)（写在纯文本框中，不确定括号是否匹配）。最好使用 first、second 和 third，将其重写为：
(let ((curr (first lst)) (left (second lst) (right (third lst)) ....
而且我确实认为有更好的方法来编写关于 BST 的代码，通过创建更合理的实用函数。
请研究这段代码：
(defun binary-search-tree-p (tree)
(if (null tree)
t
(destructuring-bind (value &optional left right) tree
(let ((left-val (car left))
(right-val (car right)))
(and (binary-search-tree-p left)
(binary-search-tree-p right)
(numberp value)
(or (null left)
(<= left-val value))
(or (null right)
(< value right-val)))))))
命名：函数命名清晰，使用
-p约定表明它是一个谓词：one-argument布尔值来检验一些道理。参数是tree，不是list。顺便说一下，在 Common Lisp 中，list是一个有效的变量名，它不会影响list函数。null 大小写是
T而不是NIL。我们非常有必要声明一个空的 BST 是有效的，而不是无效的。如果一个空的 BST 是无效的，那么如果我们想要 one-node BST(42 nil nil)是有效的，那么我们必须添加丑陋的任意规则，如果 BST 有空 children（这本身无效！）那么它本身就是有效的。destructuring-bind和&optional简化了用于分离树节点片段的代码。我们首先验证 children 是
binary-search-tree-p。下一个检查是(numberp value)。因此，如果一棵树为空，则它是有效的，但如果它不为空，则它必须具有数值。解决了上面（4）中的一些重要问题，我们不必再使用
numberp。如果我们知道left是有效的 BST，那么如果left不为空，则(numberp left)必须为真，因为这是递归检查的！我们在剩下的两个测试中利用了这一点：(or (null left) (<= (car left) value)): "Either the left tree is empty, or else we can trust that left tree's value to be number, and that number must not exceed the value at this node" 和类似的权利。
如果 (car left)是安全的；但是，重要的是要承认我们的代码会由于访问(car "abc")而在(42 "abc")这样的树节点上崩溃。如果需要对这种情况具有鲁棒性，则需要一些额外的逻辑。我假设由于您使用的是
<=，树中显然允许重复值。我进一步假设重复值 运行 向左。那么也就是说，在二分查找中，当遇到top-most个重复值时，剩下的那个值的重复值都在左子树中。如果需要，这很容易调整，使副本落在另一个方向。但是，请注意，在任何一种选择下，我们的测试都不必要地严格。也就是说，这其实是一个有效的二叉查找树，有重复项，被拒绝了，因为(< 5 5)右边失败：5 5 5 4 5 7 6 8合适的条件应该是：
... (or (null left) (<= left-val value)) (or (null right) (<= value right-val))
left 是 nil，