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

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

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

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

Определение [ править ]

• Направленный край - ссылка от родителя к ребенку.
• Корень - узел без родителей. В корневом дереве есть не более одного корневого узла.
• Leaf Node - любой узел, у которого нет дочерних узлов.
• Родительский узел - любой узел, связанный направленным ребром со своим дочерним или дочерним узлом.
• Дочерний узел - любой узел, связанный с родительским узлом направленным ребром.
• Глубина - длина пути от корня до узла. Набор всех узлов на заданной глубине иногда называют уровнем дерева. Корневой узел находится на нулевой глубине.
• Высота - длина пути от корня до самого глубокого узла дерева. У (корневого) дерева только с одним узлом (корнем) высота равна нулю. На диаграмме примера дерево имеет высоту 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}}}$

• Если узел занимает ДЕРЕВО , его левый дочерний элемент сохраняется в ДЕРЕВО .${\ displaystyle N}$${\ displaystyle [k]}$${\ displaystyle [3k-1]}$
• Mid Child хранится в TREE .${\ displaystyle [3k]}$
• Правый ребенок хранится в ДЕРЕВЕ .${\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 и переход.

 я / | \ / | \ bso / | \ / \ | \ aehntnt | \ | / \ | Syefro \ т

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

Примеры троичных деревьев [ править ]

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

См. Также [ править ]

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

Ссылки [ править ]