（固定代码）racket——从树中删除一个节点

Question

所以我目前卡在racket的中级水平，看了各种代码，但大部分都看不懂我正在尝试从二叉搜索树中删除一个节点

到目前为止，我已经想出了这个，其中包括一个空节点以及错误顺序的第一个和最后一个节点

    (define-struct node (key value left right))

    (define (delete bst k)
  (local [(define empty-l (empty? (node-left bst)))
          (define empty-r (empty? (node-right bst)))
          (define full-l (not empty-l))
          (define full-r (not empty-r))]

    (local [(define (replace bst) 
              ;;takes node and takes it away, finding the next part that should take over its spot
              (cond
                [(empty? bst) empty]
                [(and empty-l empty-r) empty]
                [(and empty-l full-r) (node-right bst)]
                [(and full-l empty-r) (node-left bst)]
                [(and full-l full-r) (make-node                                  
                                      (if (**empty? (node-right bst)) "MAKE_THIS_KEY_GO_AWAY"**  (node-key (node-right bst)))
                                      (if (**empty? (node-right bst)) "MAKE_THIS_VALUE_GO_AWAY"** (node-value (node-right bst)))
                                      ;(node-value (node-right bst))
                                      (node-left bst)
                                      (replace (node-right bst)))]))]

      ;(local ((define (find k bst)
      ;;if finds k, puts it through replace to replace it
      (cond
        [(empty? bst) empty]
        [(= k (node-key bst)) (replace bst)]
        [(< k (node-key bst)) (make-node (node-key bst)
                                         (node-value bst)
                                         (delete k (node-left bst))
                                         (node-right bst))]
        [else (make-node (node-key bst)
                         (node-value bst)
                         (node-left bst)
                         (delete k (node-right bst)))]))))

;; Example binary search tree for check-expect
(define t (make-node 5 "" (make-node 3 "" (make-node 2 "" (make-node 1 "" empty empty)
                                                     empty)
                                     (make-node 4 "" empty empty))
                     (make-node 7 "" (make-node 6 "" empty empty) empty)))



(check-expect (delete t 5)
              (**make-node 6 ""** (make-node 3 "" (make-node 2 "" (make-node 1 "" empty empty)
                                                         empty)
                                         (make-node 4 "" empty empty))
                         (**make-node 7 ""** empty empty)))


;;What I actually get
(**make-node
 7
 ""**
 (make-node
  3
  ""
  (make-node
   2
   ""
   (make-node 1 "" empty empty)
   empty)
  (make-node 4 "" empty empty))
 (**make-node
  "MAKE_THIS_KEY_GO_AWAY"
  "MAKE_THIS_VALUE_GO_AWAY"**
  (**make-node 6 ""** empty empty)
  empty))

Answer 1

(full-l full-r)案子一团糟。要处理这种情况，您需要选择维基百科所谓的 "in-order predecessor" 或 replace 处理的 bst 实例的 "in-order successor"，然后从 replace 的 bst 并使其成为替代品。这些函数可用于按顺序查找 predecessor/successor:

(define (in-order-predecessor tree)
  (right-bottom (node-left tree)))

(define (in-order-successor tree)
  (left-bottom (node-right tree)))

(define (left-bottom tree)
  (if (empty? (node-left tree))
      tree
      (left-bottom (node-left tree))))

(define (right-bottom tree)
  (if (empty? (node-right tree))
      tree
      (right-bottom (node-right tree))))

所以你会这样做：

[(and full-l full-r)
 (local [(define successor (in-order-successor bst))
         (define old-right (node-right bst))
         (define new-right (delete old-right (node-key successor)))]
     (make-node (node-key successor) (node-value successor)
                (node-left bst) new-right))]

由于此版本的 replace 不再是递归的，因此不需要接收 bst 作为参数。

此外，您混淆了 delete 的参数顺序。您将其定义为 (delete node k) 但在两个地方您将其称为 (delete k node).

（固定代码）racket——从树中删除一个节点

(fixing a code for) racket-- deleting a node from a tree

racket

binary-search-tree