Итерация по дереву AVL в пространстве O (1) без рекурсии

Question

У меня есть дерево AVL.Каждый узел выглядит следующим образом:

typedef struct {
    Node *parent;  // the parent node
    Node *left;    // the node left of this node
    Node *right;   // the node right of this node
    int height;    // the height of this node
    void *value;   // payload
} Node;

Возможно ли выполнить итерацию по дереву AVL с этими узлами в пространстве O (1), без рекурсии, если да, то как?

Если нет, то решение с подпространством O (n) или там, где действительно необходимо пространство O (N), также ценится.

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

Answer 1

Если вы сохраняете последний узел, который вы посетили, вы можете получить следующий узел для посещения в итераторе.

• Если последний узел был вашим родителем, перейдите вниз по левому поддереву.
• Если последний узел был вашим левым поддеревом, перейдите по правому поддереву.
• Если последний узел был вашим правильным поддеревом, перейдите к вашему родителю.

Этот алгоритм дает вам обход в O (1) для дерева.Вам нужно немного прояснить это для листьев и решить, какой тип итератора (pre / in / post-order) вы хотите решить, где должен находиться итератор, и ждать приращения.

Answer 2

«Источники данных и их алгоритмы» Гарри Льюиса и Ларри Дененберга описывают обратный переход по ссылкам для постоянного пространственного обхода двоичного дерева.Для этого вам не нужен родительский указатель на каждом узле.Обход использует существующие указатели в дереве для хранения пути для отслеживания назад.Требуется 2-3 дополнительных ссылки на узлы.Плюс немного на каждом узле, чтобы отслеживать направление прохождения (вверх или вниз) при движении вниз.В моей реализации этих алгоритмов из книги профилирование показывает, что этот обход имеет гораздо меньше памяти / процессорного времени.Реализация в Java (было бы быстрее, я думаю) здесь .

Answer 3

Можно получить следующий узел в порядке, учитывая указатель на некоторый узел, если вы сохраняете родительские указатели.Это можно использовать для итерации дерева, начиная с самого левого узла.Из моей реализации дерева AVL :

BAVLNode * BAVL_GetNext (const BAVL *o, BAVLNode *n)
{
    if (n->link[1]) {
        n = n->link[1];
        while (n->link[0]) {
            n = n->link[0];
        }
    } else {
        while (n->parent && n == n->parent->link[1]) {
            n = n->parent;
        }
        n = n->parent;
    }

    return n;
}

Чтобы получить самый левый узел:

BAVLNode * BAVL_GetFirst (const BAVL *o)
{
    if (!o->root) {
        return NULL;
    }

    BAVLNode *n = o->root;
    while (n->link[0]) {
        n = n->link[0];
    }

    return n;
}

Здесь, node->link[0] и node->link[1] - это левые иправый потомок узла, соответственно, и node->parent - указатель на родительский узел (или NULL для корня).

Одна операция GetNext () имеет сложность времени O (logn).Однако при использовании для итерации всего дерева вы получаете O (n) амортизированной сложности по времени.