Как изобразить биномиальное дерево в памяти

Question

У меня есть такая структура, описывается как "биномиальное дерево".Давайте посмотрим на рисунок:

Как лучше всего представить это в памяти?Просто для пояснения, это не простое двоичное дерево, так как узел N4 является и левым, и правым потомками N1, такое же разделение происходит для N7 и N8 и т. Д. Мне нужен алгоритм построения, который легко избежатьдублировать такие узлы, но просто ссылаться на них.

ОБНОВЛЕНИЕ Многие из нас не согласны с "определением биномиального дерева", но это исходит из финансов (особенно производных цен), посмотрите здесь: http://http.developer.nvidia.com/GPUGems2/gpugems2_chapter45.html например.Поэтому я использовал определение «Домен принят».

Answer 1

Вы можете генерировать структуру уровня за уровнем.На каждой итерации создайте один уровень узлов, поместите их в массив и подключите к ним предыдущий уровень.Примерно так (C #):

Node GenerateStructure(int levels)
{
    Node root = null;

    Node[] previous = null;

    for (int level = 1; level <= levels; level++)
    {
        int count = level;

        var current = new Node[count];

        for (int i = 0; i < count; i++)
            current[i] = new Node();

        if (level == 1)
            root = current[0];

        for (int i = 0; i < count - 1; i++)
        {
            previous[i].Left = current[i];
            previous[i].Right = current[i + 1];
        }

        previous = current;
    }

    return root;
}

Вся структура требует O (N ^ 2) памяти, где N - номер уровня.Этот подход требует O (N) дополнительной памяти для двух массивов.Другой подход заключается в создании графика слева направо, но для этого также потребуется O (N) дополнительной памяти.

Очевидно, что сложность по времени равна O (N ^ 2).

Answer 2

Больше, чем дерево, из которого я бы дал определение типа «связный граф из N вершин и N-1 ребер», эта структура выглядит как Паскаль (или Тарталья, как говорят в Италии) *. Таким образом, достаточно массива с подходящей индексацией.

Подробная информация о конструкции зависит от вашего ввода данных: пожалуйста, дайте еще подсказку.