How to write a remove function (from a binary tree) simply and clearly?

Question

This is an assignment. But it was [already] due and I think I worked it out. I'm new to Racket. I feel my code is a bit tedious. Is there any better way to improve it?

The requirement supposes to give a key x, and k is the value of the root node. If x < k, return recursion on left subtree + k + right subtree. If x > k, return recursion on right subtree + k + left subtree. If x=k, (a) return right subtree if left is empty, (b) return left subtree if right is empty, or otherwise (c) return right min value + left subtree + (right subtree - min value):

(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 following is the given tree structure. We should not modify it.

; 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])]))

Will Ness Will Ness · Accepted Answer · 2018-06-07T08:19:57

You should use the structure predicates, in particular emp?: instead of (equal? lt emp) (which is also erroneous, emp should be in parens), use just (emp? lt).

When a function is too long, it's a sure sign it should be broken into smaller functions.

Lastly, the removal and reporting of the minimum element of a tree should be done in one function, with one tree traversal. delete is too broad, it is searching for the element it was given; but here we already know the element will be at the leftmost position:

(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

It is the responsibility of min-elem to return both the minimal element and the valid tree that's left after its removal (see values, and call-with-values, for that; if that's too taxing / confusing at first, you can indeed implement it as you showed in the question, with get-min and the recursive use of delete, it's just will be less efficient that way ... update: added the simpler implementation to the code).

The minimal element is going to be the leftmost one in the tree (which is guaranteed to be non-empty). There are only two cases to consider: whether the tree's left child is empty, or not. You don't need to handle all the cases explicitly as you do. It is unnecessarily verbose.

Also, in your description (and in the code), you've got the branches flipped at places: left is always going on the left, recursion or no recursion. It should be:

If x < k, return recursion on left subtree + k + right subtree. If x > k, return left subtree + k + recursion on right subtree. If x=k, (a) return right subtree if left is empty, (b) return left subtree if right is empty, or (c) otherwise return left subtree + right min value + (right subtree - min value).

How to write a remove function (from a binary tree) simply and clearly?

1 Answers