Бинарное дерево левого дочернего элемента и правого родственного элемента
Любая многопутевая или k-арная древовидная структура, изучаемая в информатике, допускает представление в виде двоичного дерева , которое носит разные названия, включая представление дочерних элементов , [1] двоичное дерево левого дочернего элемента, правого дочернего элемента , [2] дерево с двойной цепью или цепь дочерних наследников . [3]
которое представляет многопутевое дерево T , каждый узел соответствует узлу в T и имеет два указателя : один на первого дочернего узла узла, а другой на его следующего брата в T. В двоичном дереве , Таким образом, дочерние элементы узла образуют односвязный список . Чтобы найти узел n ' k' -й дочерний, необходимо пройти по этому списку:
процедура kth-child(n, k):
ребенок ← н.ребенок
в то время как k ≠ 0 и ребенок ≠ ноль:
ребенок ← ребенок.следующий-родной брат
к ← к - 1
вернуть дочерний элемент // может вернуть ноль
Процесс преобразования k-арного дерева в двоичное дерево LC-RS иногда называют Кнута преобразованием . [4] Чтобы сформировать двоичное дерево из произвольного k-арного дерева этим методом, корень исходного дерева делается корнем двоичного дерева. Затем, начиная с корня, самый левый дочерний элемент каждого узла в исходном дереве становится его левым дочерним элементом в двоичном дереве, а его ближайший справа дочерний узел в исходном дереве становится его правым дочерним элементом в двоичном дереве.
Деревья с двойной цепью были описаны Эдвардом Х. Сассенгутом в 1963 году. [5]
При преобразовании k-арного дерева в двоичное дерево LC-RS каждый узел связывается и выравнивается по левому дочернему элементу, а следующим ближайшим является родственный узел. Например, у нас есть троичное дерево ниже:
1
/|\
/ | \
/ | \
2 3 4
/ \ |
5 6 7
/ \
8 9
Мы можем переписать его, поместив левый дочерний узел на один уровень ниже его родителей и поместив родственного узла рядом с дочерним элементом на том же уровне — он будет линейным (та же строка).
1
/
/
/
2---3---4
/ /
5---6 7
/
8---9
Мы можем преобразовать это дерево в бинарное, повернув каждого брата на 45° по часовой стрелке. [6]
1
/
2
/ \
5 3
\ \
6 4
/
7
/
8
\
9
Варианты использования [ править ]
Представление LCRS более эффективно использует пространство, чем традиционное многопутевое дерево, но за это приходится платить за то, что поиск дочерних узлов по индексу становится медленнее. Следовательно, представление LCRS предпочтительнее, если
- Эффективность памяти вызывает беспокойство и/или
- Произвольный доступ к дочерним узлам не требуется.
Случай (1) применяется, когда необходимы большие многопутевые деревья, особенно если деревья содержат большой набор данных. Например, при хранении филогенетического дерева может подойти представление LCRS.
Случай (2) возникает в специализированных структурах данных, в которых древовидная структура используется весьма специфическим образом. Например, многие типы структур данных кучи, использующие многопутевые деревья, можно оптимизировать по пространству с помощью представления LCRS. (Примеры включают кучи Фибоначчи , парные кучи и слабые кучи .) Основная причина этого заключается в том, что в структурах данных кучи наиболее распространенными операциями являются
- Удалить корень дерева и обработать каждого его потомка, или
- Объедините два дерева вместе, сделав одно дерево дочерним по отношению к другому.
Операция (1) очень эффективна. В представлении LCRS дерево организуется так, чтобы у него был правильный дочерний элемент, поскольку у него нет родственного элемента, поэтому корень легко удалить.
Операция (2) также эффективна. Соединить два дерева вместе легко. [7]
Ссылки [ править ]
- ^ Фредман, Майкл Л .; Седжвик, Роберт ; Слитор, Дэниел Д .; Тарьян, Роберт Э. (1986). «Парная куча: новая форма саморегулирующейся кучи» (PDF) . Алгоритмика . 1 (1): 111–129. дои : 10.1007/BF01840439 .
- ^ Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001) [1990]. Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. стр. 214–217. ISBN 0-262-03293-7 .
- ^
В этой статье использованы общедоступные материалы из Пол Э. Блэк. «Двоичное представление деревьев» . Словарь алгоритмов и структур данных . НИСТ .
- ^ Компьютерные структуры данных. Джон Л. Пфальц.
- ^ Сассенгут, Эдвард Х. (май 1963 г.). «Использование древовидных структур для обработки файлов» . Коммуникации АКМ . 6 (5): 272–279. дои : 10.1145/366552.366600 .
- ^ «двоичное представление деревьев» . xlinux.nist.gov . Проверено 24 ноября 2015 г.
- ^ «Каково представление дерева для левого дочернего и правого дочернего элементов? Зачем вам его использовать?» . stackoverflow.com . Проверено 12 декабря 2016 г.
