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

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

Визначення

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

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

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

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

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

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

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


h

 M(h)


 0

 1


 1

 4


 2

 13


 3

 40

Тоді



Отже, кожне дерево висотою h має не більше  вузлів.

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

* його лівий дочірній елемент має номер ;

* середній — ;
* правий — .

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

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

Зовнішні вузли
Щоб додати новий вузол після вузла 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».

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

Див. також
* Двійкове дерево
* Ієрархічна структура

Примітки


