Ответ 1

Представление left-child, right-sibling (LCRS) является способом кодирования многоуровневого дерева (древовидная структура, в которой каждый node может иметь любое количество детей), используя дерево (a древовидная структура, в которой каждый node может иметь не более двух детей).

Мотивация

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

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

(Извинения за некачественное изображение ASCII!)

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

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

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

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

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

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

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

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

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

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

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

Анализ

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

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

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

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

Следовательно, общее использование пространства

n & middot; (sizeof (Data) + sizeof (Node *) + 2 * sizeof (машинное слово)) + (n - 1) * sizeof (Node *)

= n * sizeof (Data) + (2n - 1) * sizeof (Node *) + 2n * sizeof (машинное слово)

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

n * sizeof (Data) + 2n * sizeof (Node *)

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

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

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

Использовать случаи

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

• Память крайне ограничена или
• Случайный доступ к детям node не требуется.

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

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

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

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

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

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

Мы можем слить деревья вместе следующим образом:

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

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

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