Бинарное дерево с левым потомком и правым братом

6-арное дерево в виде двоичного дерева

Каждое многостороннее или k-арное дерево структура, изучаемая в информатике, допускает представление в виде двоичного дерева, которое es под разными именами, включая представление дочернего брата, левое дочернее дерево, двоичное дерево правого брата, дерево с двойной цепочкой или дочерняя цепочка .

В двоичном дереве, представляющем многостороннее дерево T, каждый узел соответствует узлу в T и имеет два указателя : один на первого дочернего элемента узла, а другой - на его следующего брата в T. Таким образом, дочерние элементы узла образуют односвязный список . Чтобы найти k-го потомка узла n, необходимо пройти по этому списку:

procedure kth-child (n, k): child ← n.child while k ≠ 0 и child ≠ nil: child ← child.next-sibling k ← k - 1 return child // может возвращать nil

A trie, реализованное как дерево с двойной цепью: вертикальные стрелки - дочерние указатели, пунктирные горизонтальные стрелки - указатели на следующего брата. Попытки помечаются меткой ребер, и в этом представлении метки ребер становятся метками узлов на двоичных узлах.

Процесс преобразования из k-арного дерева в двоичное дерево LC-RS иногда называют преобразование Кнута. Чтобы сформировать двоичное дерево из произвольного k-арного дерева этим методом, корень исходного дерева становится корнем двоичного дерева. Затем, начиная с корня, крайний левый дочерний узел каждого узла в исходном дереве становится его левым дочерним элементом в двоичном дереве, а его ближайший родственник справа в исходном дереве становится его правым дочерним элементом в двоичном дереве.

Двуцепные деревья были описаны Сассенгутом в 1963 году.

При обработке k-арного дерева в двоичное дерево LC-RS каждый узел связывается и выравнивается с левым дочерним элементом, а следующий ближайший является родным братом. Например, у нас есть троичное дерево ниже:

1 / | \ / | \ / | \ 2 3 4 / \ | 5 6 7 / \ 8 9

Мы можем переписать его, поместив левый дочерний узел на один уровень ниже его родителей и поместив брата рядом с дочерним на том же уровне - он будет линейным ( та же линия).

1 / / / 2 --- 3 --- 4 / / 5 --- 6 7/8 --- 9

Мы можем преобразовать это дерево в двоичное, повернув каждый из братьев и сестер на 45 ° по часовой стрелке.

1/2 / \ 5 3 \ \ 6 4/7/8 \ 9

Представление LCRS более пространственно - эффективен, чем традиционное многопутевое дерево, но за счет того, что поиск дочерних узлов по индексу становится медленнее. Следовательно, представление LCRS предпочтительнее, если

1. эффективность памяти вызывает беспокойство и / или
2. Произвольный доступ к дочерним узлам не требуется.

Случай (1) применяется, когда большие многосторонние деревья необходимы, особенно когда деревья содержат большой набор данных. Например, при хранении филогенетического дерева может оказаться подходящим представление LCRS.

Случай (2) возникает в специализированных структурах данных, в которых древовидная структура используется очень специфическим образом. Например, многие типы структур данных кучи, использующие многосторонние деревья, можно оптимизировать по пространству с помощью представления LCRS. (Примеры включают кучи Фибоначчи, кучи соединения и слабые кучи.) Основная причина этого заключается в том, что в структурах данных кучи наиболее распространенными операциями являются

1. Удалите корень дерева и обработайте каждого из его дочерних элементов, или
2. Соедините два дерева вместе, сделав одно дерево дочерним для другого.

Операция (1) очень эффективна. В представлении LCRS он организует дерево так, чтобы у него был правый дочерний элемент, потому что у него нет родного брата, поэтому легко удалить корень.

Операция (2) также эффективна. Два дерева легко объединить.