LINUX.ORG.RU
Форум — Development  

[Lisp] [binary tree] [remove-node] как?

 


0

0 

Все доброго времени суток всем.

Что-то решил поиграться с двоичными деревьями, и возник у меня вопрос...

что насчёт удаления определённой ноды (листа)... ясное дело, можно
сделать это в стиле C или любого другого императивного ЯП, но меня
интересует, можно ли это сделать как-либо красивее, применив,
возможно, функциональную парадигму?

сейчас у меня есть вот такие функции:

;; добавление листа/ноды
(defun insert-node (tree new-node)
  (if (not tree) new-node
      (if (>= (first tree) (first new-node))
          (list (first tree) 
                (insert-node (second tree) new-node) 
                (third tree))
          (list (first tree) 
                (second tree) 
                (insert-node (third tree) new-node)))))

;; создание листа/ноды
(defun make-node (element)
  (list element nil nil))

;; собственно построение дерева
(defun make-tree (elements)
  (reduce #'insert-node 
          (map 'list #'make-node elements)))

сразу скажу, я не заморачивался о сбалансированности, и строил дерево в лоб,
самым простым способом...

ну а теперь собственно буду ждать, может кто-нить подскажет,
как удалить некий лист, самым красивым способом? :)

Ответ на: комментарий от anonymous

Ты думаешь я гуглом пользоваться не умею? :)

в этом примере реализована как раз обычная имеративная функция удаления ноды... и это выглядит так каряво, что даже на C это меньше строк занимает... так что не вариант... хочу другого чего-нить :)

Cy6erBr4in ★★★
() автор топика

поищи книжицу purely functional data structures - там как раз все написано, правда не на лиспе

ott ★★★★★
()
Ответ на: комментарий от ott 

Довольно быстро нашёл книжку, спасибо, очень интересно, почитаю на досуге,
но при беглом просмотре не нашёл того чего искал :(

вообщем, после недолгого размышления, мой разум порадил нечто следующее :)

(defun move-it (from to)
  (if (second to)
      (list (first to)
            (move-it from (second to))
            (third to))
      (list (first to)
            from
            (third to))))

(defun remove-it (node)
  (cond ((and (second node) (third node)) (move-it (second node) (third node)))
        ((second node) (second node))
        ((third node) (third node))
        (t nil)))

(defun remove-node (tree key)
  (if (not tree) 
      nil
      (cond ((< key (first tree)) (list (first tree)
                                        (remove-node (second tree) key)
                                        (third tree)))
            ((> key (first tree)) (list (first tree)
                                        (second tree)
                                        (remove-node (third tree) key)))
            ((= key (first tree)) (remove-it tree)))))

Cy6erBr4in ★★★
() автор топика
Ответ на: комментарий от Cy6erBr4in

как не крути, тут сплошная имеративщина :) прямо изо всех сторон торчит...

у меня уже закрадываются сомнения... а можно ли красивее? если кто-нить знает как, с удовольствием посмотрю :)

Cy6erBr4in ★★★
() автор топика
Ответ на: комментарий от Cy6erBr4in

то что быстро ищется, это диссертация, а не книжка. книжка должна быть 220 страниц насколько я помню. В книге больше примеров и более подробно написано

ott ★★★★★
()
Ответ на: комментарий от ott

Да не, я и книгу нашёл... там как-то интересно, он-лайн просмотр гугловский сделан какой-то... но что-то я там не нашёл нужного мне.. надо будет посмотреть подробнее :)

Cy6erBr4in ★★★
() автор топика
Ответ на: комментарий от Vadim_Z

Кстати посмотрел ссылку, в принципе там примерно то же что я написал тут, просто написано немного иначе :) там используется дополнительная "структура" для ноды, поэтому код выглядит несколько иначе... но в целом то же самое...

наверное диструктивныые действия с данными - не совсем функциональный подход :) поэтому всё это решается как и везде :)

Cy6erBr4in ★★★
() автор топика
Ответ на: комментарий от Cy6erBr4in

За книгу спасибо.

Ну да, похоже. Функциональный подход работает с неизменяемыми структурами. Поэтому показалось странным, что Вы узрели императивщину в своём коде.

Vadim_Z ★
()
Ответ на: комментарий от Vadim_Z

Да всегда пожалуйста :)

и кстати да... если посмотреть на код, то вроде всё "функционально" :) только ветвления и рекурсия :))

P.S.: нинада на ВЫ, очень прошу ;)

Cy6erBr4in ★★★
() автор топика
Ответ на: комментарий от Cy6erBr4in

Об том и речь. Рекурсия и ветвления вполне функциональны, если, конечно, не считать что ФП=Unlambda :-D

Vadim_Z ★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
Development