Как написать функцию удаления (из двоичного дерева) просто и понятно? - PullRequest
Новая
       59

Как написать функцию удаления (из двоичного дерева) просто и понятно?

0 голосов
/ 07 июня 2018

Это задание.Но это было [уже] должным образом, и я думаю, что я решил это.Я новичок в ракетке.Я чувствую, что мой код немного утомителен.Есть ли лучший способ улучшить его?

Требование предполагает дать ключ 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])]))

1 Ответ

0 голосов
/ 07 июня 2018

Вы должны использовать предикаты структуры, в частности emp?: вместо (equal? lt emp) (что также ошибочно, emp должно быть в скобках), используйте просто (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-elem1018 * и действительное дерево, которое осталось после его удаления (см. values и call-with-values, для этого; если это поначалу слишком сложно / запутанно, выможет действительно реализовать это, как вы показали в вопросе, с get-min и рекурсивным использованием delete, просто так будет менее эффективно ... update: добавлена ​​более простая реализация в код ).

Минимальным элементом будет крайний левый элемент в дереве (который гарантированно не будет пустым).Есть только два случая: ли левый дочерний элемент дерева пуст или нет.Вам не нужно обрабатывать все случаи явно, как вы.Это излишне многословно.

Кроме того, в вашем описании (и в коде) у вас есть перевернутые ветки в местах: left is всегда происходитслева, рекурсия или нет рекурсии.Должно быть:

Если x рекурсию на левом поддереве + k + на правом поддереве .Если x> k, вернуть левое поддерево + k + рекурсию на правое поддерево .Если x = k, (a) верните правое поддерево , если left пусто, (b) верните left поддерево , если right пусто, или (c) в противном случае верните left поддерево + правильное минимальное значение + (правое поддерево - минимальное значение) .

...