Удалить наименьший элемент в BST (перевод C на Lisp) - PullRequest
Новая
       33

Удалить наименьший элемент в BST (перевод C на Lisp)

1 голос
/ 09 июля 2019

Я более часа пытался перевести следующий код C на Lisp, чтобы исправить функцию bst-remove в коде BST в книге Пола Грэма ANSI Common Lisp (которая, как объяснено в исправлениях к этой книге, сломан) и я полностью в тупике.

Я пытался написать это деструктивно (также неразрушающе) и столкнулся с проблемой обнаружения фактического наименьшего узла, с которым я хочу работать, не из конечного узла, а на один уровень выше, так что Я могу переназначить это. Это как раз то, где указатели появляются в C-версии, и я не знаю, что я делаю в Lisp, чтобы попытаться достичь аналогичного результата.

Вы, возможно, уже знаете это, поскольку оно является частью стандартной функции удаления bst, но, как указано ниже, требуется replace the smallest node with its right child.

Я не слишком беспокоюсь о возврате мин. На самом деле, если мы напишем это неразрушающим образом, то, что мы хотим вернуть, это новое дерево минус элемент min, а не min (не говоря уже о возвращении нескольких значений).

Итак, я полностью озадачен этим и сдался. 

ETYPE deletemin(TREE *pT) 
{
    ETYPE min;

    if ((*pT)->leftChild == NULL) { 
        min = (*pT)->element; 
        (*pT) = (*pT)->rightChild; 
        return min;
    } 
    else
        return deletemin(&((*pT)->leftChild));
}

Источник выше: p264 в этот pdf .

Вот структура, относящаяся к версии Lisp 

(defstruct (node 
  elt (l nil) (r nil))

Дайте мне знать, если вы хотите, чтобы я опубликовал больше кода BST.

Идея (нерабочая) (см. Обсуждение в комментариях): 

(defun delete-min (bst)
  (if (null (node-l bst))
      (if (node-r bst)
          (progn
            (setf (node-elt bst) (node-elt (node-r bst)))
            (setf (node-l   bst) (node-l   (node-r bst)))
            (setf (node-r   bst) (node-r   (node-r bst))))
          (setf bst nil))   ; <- this needs to affect the var in the calling fn
      (delete-min (node-l bst))))

Хотя мне бы очень хотелось, чтобы это была неразрушающая версия

1 Ответ

3 голосов
/ 10 июля 2019

Неизменяемая и функциональная версия, очень похожая на версию в книге, но удаляет только самое низкое значение: 

(defun bst-remove-min (bst)
  (cond ((null bst) nil)
        ((null (node-l bst)) (node-r bst))
        (t (make-node :elt (node-elt bst)
                      :l (bst-remove-min (node-l bst)) 
                      :r (node-r bst)))))

Версия, которая может изменять дерево. Как и в случае с аналогичными функциями CL, вы должны использовать возвращаемое значение. 

(defun n-bst-remove-min (bst)
  (when bst
    (loop :for p := c
          :for c := bst :then child
          :for child := (node-l c)
          :unless child
            :if p
              :do (setf (node-l p) (node-r c))
                  (return bst)
            :else
              :do (return (node-r c)))))
...