Тройное дерево

В информатике троичное дерево — это древовидная структура данных , в которой каждый узел имеет не более трех дочерних узлов , обычно различаемых как «левый», «средний» и «правый». Узлы с дочерними узлами являются родительскими узлами, а дочерние узлы могут содержать ссылки на своих родителей. За пределами дерева часто имеется ссылка на «корневой» узел (предок всех узлов), если он существует. Доступ к любому узлу в структуре данных можно получить, начав с корневого узла и неоднократно следуя ссылкам на левый, средний или правый дочерний узел.

Тернарные деревья используются для реализации троичных деревьев поиска и троичных куч .

Определение

Directed Edge — ссылка от родителя к дочернему элементу.
Корень — узел без родителей. В корневом дереве может быть не более одного корневого узла.
Листовой узел — любой узел, не имеющий дочерних элементов.
Родительский узел — любой узел, соединенный направленным ребром со своим дочерним или дочерними узлами.
Дочерний узел — любой узел, соединенный с родительским узлом направленным ребром.
Глубина — Длина пути от корня до узла. Набор всех узлов на заданной глубине иногда называют уровнем дерева. Корневой узел находится на нулевой глубине.
Высота — длина пути от корня до самого глубокого узла дерева. (Корневое) дерево только с одним узлом (корнем) имеет нулевую высоту. На диаграмме примера высота дерева равна 2.
Одноуровневый узел — узлы, которые имеют один и тот же родительский узел.
Узел p является предком узла q, если он существует на пути от q до корня. Узел q тогда называется потомком p.
Размер узла — это количество его потомков, включая его самого.

Свойства троичных деревьев

Максимальное количество узлов

- Позволять $h$ быть высотой троичного дерева.

- Позволять $M(h)$ — максимальное количество узлов в троичном дереве высоты 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]$ , то его левый дочерний элемент сохраняется в TREE $[3k-1]$ .
Mid Child хранится в TREE. $[3k]$ .
Правый дочерний элемент хранится в TREE. $[3k+1]$ .

Общие операции

Вставка

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

Внешние узлы

Предположим, что добавляемый внешний узел — это узел A. Чтобы добавить новый узел после узла A, A назначает новый узел одним из своих дочерних узлов, а новый узел назначает узел A своим родительским.

Внутренние узлы

Вставка на внутренних узлах более сложна, чем на внешних узлах. Скажем, что внутренний узел — это узел A, а узел B — дочерний узел A. (Если вставка заключается в вставке правого дочернего узла, то B является правым дочерним элементом A, и аналогично с вставкой левого дочернего элемента или средним дочерним элементом.) A назначает своего дочернего элемента новому узлу, а новый узел назначает своего родителя A. Затем новый узел назначает своего дочернего элемента B, а B назначает своего родителя новым узлом.

Удаление

Удаление — это процесс удаления узла из дерева. Только определенные узлы троичного дерева могут быть удалены однозначно.

Узел с нулем или одним дочерним элементом

Предположим, что удаляемый узел — это узел A. Если у узла нет дочерних узлов ( внешний узел ), удаление выполняется путем установки для дочернего элемента родительского элемента A значения null , а для родительского узла A — нулевого значения. Если у него есть один дочерний элемент, установите родительский элемент дочернего элемента A в родительский элемент A и установите дочерний элемент родительского элемента A в дочерний элемент A.

Сравнение с другими деревьями

На рисунке ниже показано двоичное дерево поиска , которое представляет собой 12 двухбуквенных слов. Все узлы левого дочернего элемента имеют меньшие значения, а все узлы правого дочернего элемента имеют большие значения для всех узлов. Поиск начинается с корня. Чтобы найти слово «НА», сравниваем его с «В» и берем правую ветвь. Каждое сравнение может получить доступ к каждому символу обоих слов.

        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» и заканчивается на нужном узле. В каждом узле происходит доступ к элементу массива, проверка на нулевое значение и переход к ветке.

                    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]

Примеры троичных деревьев

Тернарное дерево поиска
Тернарное двоичное дерево
Тройная куча
Два бесконечных троичных дерева, содержащие все примитивные тройки Пифагора, описаны в разделах «Дерево примитивных троек Пифагора» и « Формулы для генерации троек Пифагора» . Корневой узел в обоих деревьях содержит тройку [3,4,5]. ^[2]

См. также

Ссылки

^ Джон Бентли и Боб Седжвик (1998), Журнал доктора Добба
^ Прайс, Х. Ли (2008). «Древо Пифагора: новый вид». arXiv : 0809.4324 [ math.HO ].

[1] Джон Бентли и Боб Седжвик (1998), Журнал доктора Добба

[Price-2] Прайс, Х. Ли (2008). «Древо Пифагора: новый вид». arXiv : 0809.4324 [ math.HO ].

[1]

[2]