时间戳

首页 > 解决方案 > 如何简单明了地编写删除函数（从二叉树）？

data-structures - 如何简单明了地编写删除函数（从二叉树）？

问题描述

这是一个任务。但它[已经]到期了，我想我解决了。我是新来的球拍。我觉得我的代码有点乏味。有没有更好的改进方法？

该要求假设给出一个 key x，并且k是根节点的值。如果，则返回左子树 + + 右子x < k树上的递归。k如果，则返回右子树 + + 左子x > k树上的递归。k如果x=k，（a）如果左为空则返回右子树，（b）如果右为空则返回左子树，否则（c） 返回右最小值+左子树+（右子树-最小值）：

(define (delete x tree)
  (match tree
    [(emp) (emp)]
    [(node k lt rt)
     (cond
       [(< x k) (node k (delete x lt) rt)]
       [(> x k) (node k lt (delete x rt))]
       [else
        (cond
          [(equal? lt emp) rt]
          [(equal? rt emp) lt]
          [else
           (define (get-min tree)
             (match tree
               [(emp) (emp)]
               [(node k (emp) (emp)) k]
               [(node k lt (emp)) (get-min lt)]
               [(node k (emp) rt) k]             
               [(node k lt rt) (get-min lt)]))
           (node (get-min rt) lt (delete (get-min rt) rt))])])]))

以下是给定的树结构。我们不应该修改它。

; The empty tree is represented by an "emp" record of 0 fields.
(struct emp () #:transparent)

; A node is represented by a "node" record of key, left child, right child.
(struct node (key left right) #:transparent)

; BST insert.
(define (insert x tree)
  (match tree
    [(emp) (node x (emp) (emp))]
    [(node k lt rt)
     (cond
       [(< x k) (node k (insert x lt) rt)]
       [(< k x) (node k lt (insert x rt))]
       [else tree])]))

标签： data-structuresfunctional-programmingpattern-matchingbinary-search-treeracket

解决方案

您应该使用结构谓词，特别是emp?: 而不是(equal? lt emp)（这也是错误的，emp应该在括号中），使用 just (emp? lt)。

当一个函数太长时，这是一个明确的迹象，它应该被分解成更小的函数。

最后，树的最小元素的删除和报告应该在一个函数中完成，一次遍历树。delete太宽泛了，它正在搜索给定的元素；但是在这里我们已经知道元素将在最左边的位置：

(define (delete x tree)
  (define (join lt rt)        ; all values that are in lt 
    (cond                     ;   are less than those in rt
      [(emp? lt) rt]
      [(emp? rt) lt]
      [else (call-with-values             ; use rt's minimum value  
              (lambda () (min-elem rt))   ;  as the new top node's
              (lambda (k tree)
                (node k lt tree) ))])) 

  (define (min-elem tree)     ; tree is guaranteed to be non-empty
     ; a less efficient mock-up; better if done with one traversal
     (let ([minval (get-min tree)])
       (values minval (delete minval tree))))

  (define (get-min tree)      ; leftmost value in a non-empty tree
    (match tree
      [(node k (emp) _) k]           
      [(node _ lt _) (get-min lt)])) 

  (match tree
    [(emp) (emp)]
    [(node k lt rt)
     (cond
       [(< x k) (node k (delete x lt) rt)]
       [(> x k) (node k lt (delete x rt))]
       [else    (join lt rt)])]))            ; removing the top

min-elem返回最小元素和删除后剩余的有效树 是有责任的 （请参阅和和递归使用，那样效率会降低......更新：在代码中添加了更简单的实现）。valuescall-with-valuesget-mindelete

最小元素将是树中最左边的元素（保证非空）。只有两种情况需要考虑：树的左孩子是否为空。你不需要像你一样明确地处理所有的情况。它是不必要的冗长。

此外，在您的描述（和代码中）中，您已经在某些地方翻转了分支：left总是在左边，递归或不递归。它应该是：

如果 x < k，则返回左子树+ k +右子树上的递归。如果 x > k，则返回左子树+ k +右子树上的递归。如果 x=k，（a）如果左为空则返回右子树，（b）如果右为空则返回左子树，或者（c）否则返回左子树+ 右最小值 + （右子树 - 最小值）。

推荐阅读