сбалансированное посещение двоичного дерева с изюминкой - PullRequest
Новая
       23

сбалансированное посещение двоичного дерева с изюминкой

3 голосов
/ 08 августа 2011

Поиск алгоритма O (N) на месте, который печатает пару узлов (при обходе дерева), как показано ниже для заданного сбалансированного двоичного дерева: 

                 a

              b     c

             d e   f g

Вывод: bc, de, ef, fg

Где «a» - корневой узел, «b» - левый потомок, «c» - право и т. Д. Обратите внимание на пару 'ef' на выходе.

Дополнительная информация на основе комментариев ниже:

  1. 'пара узлов' - каждая соседняя пара на каждом уровне
  2. каждый узел может иметь указатель / ссылку «родителя» в дополнение к «левому» и «правому»
  3. Если бы мы ослабили O (N) и на месте, есть ли более простые решения (как рекурсивные, так и итеративные)?

Ответы [ 2 ]

3 голосов
/ 10 августа 2011

Если это дерево хранится в массиве, его можно переставить так, чтобы оно было «непрерывным по уровню» (первый элемент - это корень, следующие два его потомка, следующие четыре их потомка и т. Д.), И проблема тривиальна.

Если он хранится другим способом, это становится проблематичным.Вы можете попробовать обход в ширину, но это может занять O (n) памяти.

Ну, я думаю, вы можете создать алгоритм времени O (n log n), сохранив текущий уровень и путь ктекущий элемент (представленный в виде двоичного числа) и сохраняющий только последний посещенный элемент, чтобы иметь возможность создавать пары.Только O (1 + log n) памяти.-> Это может быть алгоритм O (n) с обратным отслеживанием (см. Ниже).

Я знаю, что существует простой алгоритм, который посещает все узлы по порядку в O (n), поэтому может быть хитростьпосещать «сестринские» узлы по порядку за O (n) время.Время O (n log n) гарантировано, но вы можете просто остановиться на данном уровне.

Существует также тривиальный алгоритм O (n log n), вам просто нужно отфильтровать узлы для данногоуровень, увеличивая уровень для следующего цикла.

Редактировать:

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

Начиная с корневого узла в двоичном дереве узла n-1, это составляет 1 + 3 + 7 + 15 + ... + n - 1 операция.Это 2 + 4 + 8 + 16 + ... + n - log2n = 2n - log2n = O (n) операций.

Без специальных Node* parent членов этот алгоритм возможен только с O (log n) память из-за стека, необходимого для обхода по порядку.

2 голосов
/ 10 августа 2011

Предполагая, что у вас есть следующая структура в качестве дерева: 

struct Node
{
    Node *left;
    Node *right;
    int value;
};

Вы можете распечатать все пары за три прохода, модифицируя дерево на месте. Идея состоит в том, чтобы связать узлы на одной глубине вместе с их указателем right. Вы идете вниз, следуя указателям left. Мы также поддерживаем количество ожидаемых узлов для каждой глубины, так как мы не завершаем список нулем для каждой глубины. Затем разархивируем, чтобы восстановить дерево в его первоначальной конфигурации.

Прелесть этого в том, что функция zip_down; он объединяет два поддерева так, что правая ветвь левого поддерева указывает на левую ветвь правого поддерева. Если вы делаете это для каждого поддерева, вы можете выполнять итерацию по каждой глубине, следуя указателю right. 

struct Node
{
    Node *left;
    Node *right;
    int value;
};

void zip_down(Node *left, Node *right)
{
    if (left && right)
    {
        zip_down(left->right, right->left);
        left->right= right;
    }
}

void zip(Node *left, Node *right)
{
    if (left && right)
    {
        zip(left->left, left->right);
        zip_down(left, right);
        zip(right->left, right->right);
    }
}

void print_pairs(const Node * const node, int depth)
{
    int count= 1 << depth;

    for (const Node *node_iter= node; count > 1; node_iter= node_iter->right, --count)
    {
        printf("(%c, %c) ", node_iter->value, node_iter->right->value);
    }

    if (node->left)
    {
        print_pairs(node->left, depth + 1);
    }
}

void generate_tree(int depth, Node *node, char *next)
{
    if (depth>0)
    {
        (node->left= new Node)->value= (*next)++;
        (node->right= new Node)->value= (*next)++;

        generate_tree(depth - 1, node->left, next);
        generate_tree(depth - 1, node->right, next);
    }
    else
    {
        node->left= NULL;
        node->right= NULL;
    }
}

void print_tree(const Node * const node)
{
    if (node)
    {
        printf("%c", node->value);
        print_tree(node->left);
        print_tree(node->right);
    }
}

void unzip(Node * const node)
{
    if (node->left && node->right)
    {
        node->right= node->left->right;
        assert(node->right->value - node->left->value == 1);
        unzip(node->left);
        unzip(node->right);
    }
    else
    {
        assert(node->left==NULL);
        node->right= NULL;
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
    char value_generator= 'a';
    Node root;

    root.value= value_generator++;
    generate_tree(2, &root, &value_generator);
    print_tree(&root);
    printf("\n");

    zip(root.left, root.right);
    print_pairs(&root, 0);
    printf("\n");

    unzip(&root);
    print_tree(&root);
    printf("\n");

    return 0;
}

EDIT4: на месте, время O (n), пространство стека O (log n).

...