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

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

Просте тернарне дерево розміром 10 і висотою 2

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

Визначення

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

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

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

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

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

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

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

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

Тоді

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

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

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

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

• середній — ${\displaystyle 3k}$;
• правий — ${\displaystyle 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».

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

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

Див. також

• Двійкове дерево
• Ієрархічна структура

Примітки

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