Вікіпідручник

Common Lisp/Дерева

< Common Lisp

Дерева

ред.

Означення. Деревом називається граф без циклів, в якому виділено окрему вершину, яку називають коренем дерева.

Структурою типу дерева будемо називати або NIL (порожнє дерево), або структуру (Значення . (Лівий син . Правий син)), де лівий та правий сини є структурами типа дерево. Наприклад, дерево яке складається з єдиного елемента, буде мати вигляд: (Element . (NIL . NIL)).

Функція TREE-INSERT вставляє елемент n в дерево tree за наступним правилом: Якщо дерево порожнє, то створити дерево (n . (NIL . NIL)). Інакше вставити елемент в ліве піддерево якщо n менше за значення поточної вершини або в праве піддерево, якщо більше. Функція INSL створює за списком сортуюче дерево, вершинами якого будуть всі елементи списка. Дерево називається сортуючим (або бінарне дерево пошуку), оскільки при обході його зліва направо ми отримаємо відсортований список елементів у зростаючому порядку.

Перед цим визначимо, задля зручності, допоміжні функції доступу до елементів дерева (його кореня, лівого та правого піддерева)[1]:CL(+) 

(defun tree-root (tree)  ;; повертає корінь дерева
  (if (atom tree) tree
    (first tree)))

(defun tree-left (tree)  ;; повертає ліве піддерево
  (if (atom tree) nil
    (second tree)))

(defun tree-right (tree) ;; повертає праве піддерево
  (if (atom tree) nil
    (third tree)))

(DEFUN tree-insert (n tree)
  (cond
   ((null tree) n)
   ((eql n (tree-root tree)) tree)
   ((< n (tree-root tree)) ;; якщо n менший за поточний елемент
    (list (tree-root tree)
	  (tree-insert n (tree-left tree))
	  (tree-right tree)))
   (t (list (tree-root tree) ;; в іншому випадку
	    (tree-left tree)
	    (tree-insert n (tree-right tree))))))

(DEFUN INSL (lst tree)
  (if (NULL lst)
      tree
    (progn
      (SETQ tree (tree-insert (first lst) tree))
      (INSL (CDR lst) tree))))

Наступні дві функції виконують обхід дерева: PUD (Print Up-Down) — обхід згори вниз, PLR (Print Left-Right) — обхід зліва направо.CL(+) 

(DEFUN PUD (tree)
  (when (not (NULL tree))
    (PRIN1 (tree-root tree))
    (PRINC #\Space)
    (PUD (tree-left tree))
    (PUD (tree-right tree))))

(DEFUN PLR (tree)
  (when (not (NULL tree))
    (PLR (tree-left tree))
    (PRIN1 (tree-root tree))
    (PRINC #\Space)
    (PLR (tree-right tree))))

Функція REVT (Reverse Tree) обертає дерево: кожне праве піддерево стає лівим піддеревом і навпаки.CL(+) 

(DEFUN REVT (tree)
  (if (null tree)
      NIL
      (list (tree-root tree)
	    (REVT (tree-right tree))
	    (REVT (tree-left tree)))))

Приклади

ред. 
$ (defvar a (INSL '(5 1 7 3 9 2 4 8 10) NIL))
$ (PLR a)
1 2 3 4 5 7 8 9 10 T

$ (defvar b (REVT a))
$ (PLR b)
10 9 8 7 5 4 3 2 1

Функція TREE-HEIGHT обчислює висоту дерева. Вважатимемо, що висота порожнього дерева дорівнює 0. Висота непорожнього дерева дорівнює максимумові між висотами лівого та правого піддерев плюс одиниця. (TREE-HEIGHT a) = 4, де a взято з попереднього прикладу.CL(+) 

(DEFUN TREE-HEIGHT (tree)
  (if (NULL tree)
      0 ;; це висота порожнього дерева, інакше:
      (+ (MAX (TREE-HEIGHT (tree-left tree))
              (TREE-HEIGHT (tree-right tree)))
         1)))

Функції модифікатора

ред.

Функції модифікатора виконують переадресацію вказівників в структурах даних мови програмування Лісп.

RPLACA об'єкт1 об'єкт2[2]
Відбувається заміна CAR-елемента об’єкта1 вказівником на об’єкт2, повертається модифікований об’єкт. Якщо об’єкт1 — список, то перший елемент списка замінюється на об’єкт2. Якщо об’єкт1 — бінарне дерево, то його лівий син замінюється на об’єкт2. Якщо об’єкт1 — символ (aле не NIL), то символ приймає значення об’єкт2. 
$ (SETQ a '(a b c d))
$ (RPLACA a '(11 12))
((11 12) b c d)

$ (SETQ b '((1 . 2) . (3 . 4)))
$ (RPLACA b 5)
(5 . (3 . 4))

$ (SETQ s 'd)
$ (RPLACA s 'g)
;; Val(s)=d,Val(d) = g
RPLACD об’єкт1 об’єкт2[2]
Відбувається заміна CDR-елемента об’єкта1 вказівником на об’єкт2, повертається модифікований об’єкт. RPLACA та RPLACD є основними функціями, які змінюють фізичну структуру списків. Їх можна представити через узагальнену функцію присвоєння SETF:
  • (RPLACA x y)– це (SETF (CAR x) y)
  • (RPLACD x y)– це (SETF (CDR x) y)
NSUBSTITUTE новий старий список тест[3]
Модифікуються конси найвищого рівня списку. Старі елементи замінюються на нові на нульовому рівні вкладеності, для яких перевірка по тесту не дорівнює NIL[4]. Якщо тест не вказано, то по замовченню тест = EQL. 
$ (NSUBSTITUTE 1 3 '(4 5 6 (3 3 4 5) 3 4 1))
(4 5 6 (3 3 4 5) 1 4 1)

$ (NSUBSTITUTE 10 5 '(4 5 6 3 4 1) :test #'>)
(10 5 6 10 10 10)

$ (NSUBSTITUTE 10 5 '(4 5 6 3 4 1) :test #'<)
(4 5 10 3 4 1)
NSUBST новий старий список <тест>[5]
Функція працює як і NSUBSTITUTE, але модифікуються конси всіх рівнів списку. 
$ (NSUBST 1 3 '(4 5 6 (3 3 4 5) 3 4 1))
(4 5 6 (1 1 4 5) 1 4 1)
DELETE елемент список тест[6]
Вилучає зі списку всі елементи, для яких ознака перевірки за тестом не дорівнює NIL. 
$ (DELETE 3 '(1 2 3 4 3 2 1))
(1 2 4 2 1)
NREVERSE список об’єкт[7]
Обертає елементи списку, зчеплених з об’єктом. 
$ (NREVERSE '(a b c d))
(d c b a)

$ (NREVERSE '(1 2 3 (1 2 3) 4 5 6) '(1 2 3))
(6 5 4 (1 2 3) 3 2 1 1 2 3)
NBUTLAST список n[8]
Якщо n — нуль або додатне ціле, то функція NBUTLAST повертає список без n останніх елементів (відбувається заміна n-го конса, взятого з кінця списку на NIL). Якщо другий аргумент не вказано, то за замовченням n=1. 
$ (NBUTLAST '(a b c d e))
(a b c d)

$ (NBUTLAST '(a b c d e) 3)
(a b)
NCONC список1 список2 ... списокN[9]
Повертається список, який складається з елементів списків — аргументів у вказаному порядку. Відбувається модифікація останніх CDR-елементів списків. Якщо виконати команду (NCONC list list), де list — будь-який список, то результатом буде циркулянтний список, процес побудови якого буде нескінченним. 
$ (NCONC '(1 2) '(3 4) '(5 6 7)) 
(1 2 3 4 5 6 7)
SPLIT списокCL(−)
Розбиває список на два списки посередині. Значенням списку стає його перша половина. Функція SPLIT повертає другу половину списку. 
$ (SETQ a '(1 2 3 4 5 6))
$ (SPLIT a)
(4 5 6)

$ a
(1 2 3)
SORT список тест[10]
Сортуються елементи списку на основі тесту. Вихідний тест може бути знищено внаслідок виконання операції сортування (впорядкування). Дивіться також алгоритми сортування на Вікіпедії. 
$ (SORT '(2 5 3 4 1 6 8 9 7) '>)
(9 8 7 6 5 4 3 2 1)

Завдання

ред.
  1. Знайти кількість листів в заданому дереві.
  2. Знайти середнє арифметичне чисел, які знаходяться у вершинах дерева.
  3. Написати функцію швидкого сортування QSORT.

Відповіді

ред.

Примітки

ред.
  1. ↑ Дякі із функцій містять спрощений код із Stuart C. Shapiro, «Common Lisp - An Interactive Approach», W. H. Freeman and Company • New York, розділ 18, ст. 117.
  2. ↑ 2,0 2,1 Common Lisp HyperSpec, Function RPLACA, RPLACD.
  3. ↑ Common Lisp HyperSpec, Function SUBSTITUTE,....
  4. ↑ Коммон Лісп вимгає явно вказувати що переданий параметр в тест є функція. Зазвичай, це робиться додаванням #' перед назвою функції: #'<
  5. ↑ Common Lisp HyperSpec, Function SUBST,....
  6. ↑ Common Lisp HyperSpec, Function REMOVE,....
  7. ↑ Common Lisp HyperSpec, Function REVERSE, NREVERSE.
  8. ↑ Common Lisp HyperSpec, Function BUTLAST, NBUTLAST.
  9. ↑ Common Lisp HyperSpec, Function NCONC.
  10. ↑ Common Lisp HyperSpec, Function SORT, STABLE-SORT.
Отримано з https://uk.wikibooks.org/w/index.php?title=Common_Lisp/Дерева&oldid=34120