Троичное дерево

Простое тернарное дерево размера 10 и высоты 2.

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

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

Определение

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

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

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

– Пусть – высота тернарного дерева. ${\displaystyle h}$

– Пусть – максимальное число узлов в троичном дереве высоты h ${\displaystyle M(h)}$

– ${\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}}}$

• Если узел занимает TREE , то его левый потомок хранится в TREE . ${\displaystyle N}$ ${\displaystyle [k]}$ ${\displaystyle [3k-1]}$
• Средний дочерний элемент хранится в TREE . ${\displaystyle [3k]}$
• Правый потомок хранится в TREE . ${\displaystyle [3k+1]}$

Обычные операции

Вставка

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

Внешние узлы

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

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

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

Удаление

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

Узел с нулевым или одним дочерним узлом

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

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

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

 в / \ быть из / \ / \ как есть или \ \ \ / \ в он это на

Цифровой поиск пытается хранить строки посимвольно. Следующая картинка — это дерево, представляющее тот же набор из 12 слов;

 _ _ _ _ _ _ _ _ _ _ _ _ _ / / / \ \ \ / / / \ \ \ абхиот / \ / \ | / | \ /|\ | steyenstfnro как в быть он в это из на или к

каждое входное слово показано под узлом, который его представляет. В дереве, представляющем слова из строчных букв, каждый узел имеет 26-путевое ветвление. Поиск очень быстрый: поиск "IS" начинается с корня, берет ветвь "I", затем ветвь "S" и заканчивается в нужном узле. В каждом узле осуществляется доступ к элементу массива, проверка на null и берет ветвь.

 я / | \ / | \ бсо / | \ / \ | \ aehntnt | \ | / \ | сиефро \ т

На рисунке выше показано сбалансированное троичное дерево поиска для того же набора из 12 слов. Низкие и высокие указатели показаны в виде наклонных линий, а равные указатели показаны в виде вертикальных линий. Поиск слова «IS» начинается с корня, продолжается вниз по равному дочернему элементу до узла со значением «S» и останавливается там после двух сравнений. Поиск «AX» делает три сравнения с первой буквой «A» и два сравнения со второй буквой «X», прежде чем сообщить, что слова нет в дереве. ^[1]

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

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

Смотрите также

• Двоичное дерево
• Древовидная структура

Ссылки

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