Что такое левое, правое и родное представление дерева? Зачем тебе это использовать?

Question

Многие структуры данных хранят многоходовые деревья в виде двоичных деревьев, используя представление, называемое представлением "левый потомок, правый брат". Что это значит? Зачем тебе это использовать?

Answer 1

Представление "левый-дочерний" и "правый-младший" (LCRS) - это способ кодирования многоходового дерева (древовидная структура, в которой каждый узел может иметь любое количество дочерних элементов) с использованием двоичного дерева (древовидная структура, в которой каждый узел может иметь не более двух детей).

мотивация

Чтобы мотивировать, как работает это представление, давайте начнем с рассмотрения простого дерева с несколькими путями, например, здесь:

                   A
                 //|\ \
               / / | \  \
              B C  D  E  F
              |   /|\   / \
              G  H I J K   L

(Приношу извинения за некачественную работу в формате ASCII!)

В этой древовидной структуре мы можем перемещаться вниз от любого узла в дереве к любому из его дочерних элементов. Например, мы можем мигрировать из А в В, от А до С, от А до D и т. Д.

Если бы мы хотели представить узел в дереве, подобном этому, мы обычно использовали бы здесь какую-то структуру / класс узлов, например, здесь (написанный на C++):

struct Node {
    DataType value;
    std::vector<Node*> children;
};

В представлении LCRS мы представляем многоходовое дерево таким образом, что для каждого узла требуется не более двух указателей. Для этого мы немного изменим дерево. Вместо того чтобы каждый узел в дереве сохранял указатели на все его дочерние элементы, мы будем структурировать дерево немного по-другому, так как каждый узел хранит указатель только на один из его дочерних элементов (в LCRS, самый левый дочерний элемент). Затем каждый узел будет хранить указатель на своего правого брата, следующий узел в дереве, который является дочерним по отношению к тому же родительскому узлу. В случае вышеприведенного дерева мы могли бы представить дерево следующим образом:

            A
           /
          /
         /
        B -> C -> D -> E -> F
       /         /         /
      G         H->I->J   K->L

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

• Спуск в левый потомок текущего узла. (Это первый узел в списке его дочерних элементов).
• Следуйте указателю правого брата этого ребенка k раз. (Это приведет вас к k-му дочернему узлу).
• Верните этот узел.

Например, чтобы найти третий (нулевой индексированный дочерний элемент) корневого узла A, мы должны спуститься к крайнему левому дочернему элементу (B), а затем перейти по трем правым ссылкам (посещение B, C, D и, наконец, E). Затем мы приходим к узлу для E, который содержит третий дочерний элемент узла A.

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

struct Node {
    DataType data;
    Node* leftChild;
    Node* rightSibling;
};

Эта структура узла имеет точно такую ​​же форму узла в двоичном дереве (данные плюс два указателя). В результате, представление LCRS позволяет представлять произвольное многолучевое дерево, используя только два указателя на узел.

Анализ

Давайте теперь посмотрим на временную и пространственную сложность двух разных представлений многомерного дерева и некоторые основные операции над ним.

Давайте начнем с рассмотрения общего использования пространства, необходимого для начального представления "динамический массив детей". Сколько общего использования памяти будет для дерева с n узлами? Ну, мы знаем следующее:

1. Каждый узел, независимо от количества его дочерних элементов, выделяет пространство для сохраненных необработанных данных (sizeof(data)) и служебных данных пространства динамического массива. Динамический массив (обычно) имеет один сохраненный указатель (который указывает на выделенный массив), одно машинное слово для общего числа элементов в динамическом массиве и (необязательно) одно машинное слово для выделенной емкости массива. Это означает, что каждый узел занимает размер (Data) + sizeof(Node *) + 2 * sizeof(машинное слово) пространства.

2. Во всех динамических массивах в дереве будет n - 1 указатель на потомков, так как из n узлов в дереве n - 1 из них имеют родителей. Это добавляет дополнительный (n - 1) * sizeof(Node *) фактор.

Таким образом, общее использование пространства

n · (sizeof(Данные) + sizeof (Узел *) + 2 * sizeof (машинное слово)) + (n - 1) * sizeof(Узел *)

= n * sizeof(Данные) + (2n - 1) * sizeof(Узел *) + 2n * sizeof(машинное слово)

Теперь давайте сопоставим это с деревом LCRS. Каждый узел в дереве LCRS хранит два указателя (2 * sizeof(Node*)) и один элемент данных (sizeof(Data)), поэтому его общее пространство

n * sizeof(данные) + 2n * sizeof(узел *)

И здесь мы видим выигрыш: обратите внимание, что мы не храним 2n * sizeof(машинное слово) дополнительной памяти для отслеживания выделенных размеров массива. Это означает, что представление LCRS использует значительно меньше памяти, чем обычное многоканальное дерево.

Однако базовые операции над структурой дерева LCRS, как правило, занимают больше времени, чем их соответствующие операции в обычном многоканальном дереве. В частности, в многоходовом дереве, представленном в стандартной форме (каждый узел хранит массив дочерних указателей), время, необходимое для перехода от одного узла к его k-му дочернему элементу, дается временем, требуемым для следования по одиночным указателям. С другой стороны, в представлении LCRS время, необходимое для этого, определяется временем, требуемым для следования k + 1 указателям (один левый дочерний указатель, затем k правый дочерний указатель). В результате, если дерево имеет большой коэффициент ветвления, поиск в структуре дерева LCRS может быть намного медленнее, чем в соответствующей структуре дерева с несколькими путями.

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

Случаи применения

Из-за пространственно-временного компромисса, связанного с представлением LCRS, представление LCRS обычно не используется, если не выполняется один из двух критериев:

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

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

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

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

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

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

    R1             R2
   /               /
 (children 1)    (children 2)

Мы можем объединить деревья таким образом:

             R1
            /
           R2
          /  \
(children 2) (children 1)

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

Надеюсь это поможет!