Трійкове дерево

В інформатиці трійкове дерево — деревоподібна структура даних, у якій кожен вузол має не більше трьох дочірніх вузлів, які зазвичай називають «лівим», «середнім» і «правим». Вузли з дочірніми вузлами є батьківськими, а дочірні вузли можуть містити посилання на своїх батьків. Поза деревом часто є посилання на «кореневий» вузол (предок усіх вузлів), якщо він існує. До будь-якого вузла в структурі даних можна дістатися, починаючи з кореневого вузла та багаторазово переходячи за посиланням на лівий, середній або правий дочірній вузол.

Трійкові дерева використовують для реалізації трійкових дерев пошуку та трійкових куп.

Визначення

Спрямоване ребро — зв'язок від батьківського до дочірнього вузла.
Корінь — вузол без предків. У кореневому дереві є не більше одного кореневого вузла.
Листковий вузол — будь-який вузол, який не має дочірніх елементів.
Батьківський вузол — будь-який вузол, з'єднаний спрямованим ребром із дочірнім або дочірніми вузлами.
Дочірній вузол — будь-який вузол, з'єднаний з батьківським вузлом спрямованим ребром.
Глибина — довжина шляху від кореня до вузла. Набір усіх вузлів на заданій глибині іноді називають рівнем дерева. Кореневий вузол лежить на нульовій глибині.
Висота — довжина шляху від кореня до найглибшого вузла дерева. Дерево (кореневе) лише з одним вузлом (коренем) має висоту нуль. У прикладі на малюнку дерево має висоту 2.
Брати, сестри — вузли зі спільним батьківським вузлом.

Вузол p є предком вузла q, якщо він існує на шляху від q до кореня. Тоді вузол q називають нащадком p.

Розмір вузла — кількість його нащадків, включно з ним самим.

Властивості трійкових дерев

Найбільша кількість вузлів

Нехай $h$ — висота трійкового дерева.

Нехай $M(h)$ — найбільша кількість вузлів у трійковому дереві висотою h.

h	M(h)
0	1
1	4
2	13
3	40

Тоді

$M(h)=1+3+9+\cdots +3^{h}=\sum _{i=0}^{h}3^{i}={\frac {3^{h+1}-1}{2}}$

Отже, кожне дерево висотою h має не більше ${\frac {3^{h+1}-1}{2}}$ вузлів.

Якщо вузол $N$ має в дереві номер $k$ , то:

його лівий дочірній елемент має номер $3k-1$ ;

середній — $3k$ ;
правий — $3k+1$ .

Загальні операції

Вставлення

Вузол можна вставити в трійкове дерево між трьома іншими вузлами або додати після зовнішнього вузла. У трійкових деревах вузол, який вставляється, визначається своїм предком.

Зовнішні вузли

Щоб додати новий вузол після вузла A, для A новий вузол призначають одним із дочірніх, а сам вузол A призначають батьківським для нового вузла.

Внутрішні вузли

Вставлення внутрішніх вузлів складніше, ніж зовнішніх. Нехай, A — внутрішній вузол, а вузол B — його дочірній вузл. (Якщо треба вставити правий дочірній елемент, то B є правим дочірнім вузлом A, і так само зі вставленням лівого дочірнього або середнього дочірнього вузлів.) A призначає новий вузло свім дочірнім вузлом, а новий вузол призначає A своїм батьківським вузлом. Потім новий вузол призначає своїм дочірнім вузлом B, а B призначає новий вузол своїм батьківським вузлом.

Видалення

Видалення — це процес вилучення вузла з дерева. Лише певні вузли з трійкового дерева можна видалити однозначно.

Вузол з нулем або одним дочірнім елементом

Нехай A — вузол, який потрібно видалити. Якщо він не має дочірніх вузлів (зовнішній вузол), то в батьківського щодо A вузла для дочірнього вузла встановлюється значення null, а в A — значення null . Якщо він має один дочірній елемент, в цього дочірнього елемента значення батьківського елемента встановлюється з A, а в батьківського елемента для A — значення дочірнього з A.

Порівняння з іншими деревами

Нижче зображено бінарне дерево пошуку, яке представляє 12 дволітерних слів. Усі вузли в лівому дочірньому елементі мають менші значення, тоді як у правому дочірньому елементі всі вузли мають більші значення. Пошук починається з кореня. Щоб знайти слово «on», порівнюємо його з «in» і беремо праву гілку. За кожного порівняння перевіряється кожен символ обох слів.

        in
      /    \
     be    of
    /  \  /  \
   as  by is  or
    \   \  \  / \
    at  he it on to

Для цифрового пошуку намагаються зберігати рядки символ за символом. Наступне зображення — це дерево, яке представляє той самий набір із 12 слів:

         _ _ _ _ _ _ _ _ _ _ _ _ _ 
        /     /    / \       \     \
       /     /    /   \       \     \
      a     b    h     i       o     t
     / \   / \   |   / | \    /|\    |
    s  t  e   y  e  n  s  t  f n r   o
   as at be  by he in is it of on or to

Кожне вхідне слово показано під вузлом, який йому відповідає. У дереві, що представляє слова з малих літер, кожен вузол має 26 розгалужень. Пошук дуже швидкий: пошук «IS» починається з кореня, переходить до гілки «I», потім гілки «S» і закінчується в потрібному вузлі. У кожному вузлі можна отримати доступ до елемента масиву, перевірити, чи дорівнює він null, і створити гілку.

                    i
              /     |    \
             /      |     \
            b       s      o
         / |  \    / \    |  \
        a  e   h  n   t   n   t
        |   \  |         / \  |
        s    y e        f  r  o
         \
          t

Вище зображено збалансоване трійкове дерево пошуку для того самого набору з 12 слів. Вказівники для більшого й меншого значень показано похилими лініями, тоді як вказівники для рівних значень — вертикальними лініями. Пошук слова «is» починається з кореня, продовжується «рівним» дочірнім елементом до вузла зі значенням «S» і зупиняється на цьому після двох порівнянь. Для пошуку «ax», перш ніж повідомити, що слова немає в дереві, виконується три порівняння з першою літерою «A» і два порівняння з другою літерою «X»^[1].

Приклади трійкових дерев

Трійкове дерево пошуку
Трійкова купа
Два нескінченних трійкових дерева, що містять усі примітивні піфагорові трійки, описано в статтях Дерево примітивних піфагорових трійок^[en] і Формули для генерування піфагорових трійок^[en]. Кореневий вузол обох дерев містить трійку [3,4,5].

Див. також

Примітки

↑ Jon Bentley and Bob Sedgewick (1998), Dr. Dobb's Journal

[1] Jon Bentley and Bob Sedgewick (1998), Dr. Dobb's Journal

[1]