Удаление всех узлов в двоичном дереве с использованием O (1) дополнительного пространства для хранения?

Ответ 1

Действительно, можно удалить все узлы в двоичном дереве с использованием вспомогательного пространства хранения O (n) и O (1) с помощью алгоритма, основанного на вращения дерева.

Учитывая двоичное дерево со следующей формой:

           u
          / \
         v   C
        / \
       A   B

Правое вращение этого дерева вытягивает node v над node u и приводит к следующему дереву:

        v
       / \
      A   u
         / \
        B   C

Обратите внимание, что вращение дерева может быть выполнено в O (1) времени и пространстве, просто изменив корень дерева на v, установив u левый дочерний элемент в прежний правый дочерний элемент, а затем установив v правильный дочерний элемент u.

Вращение деревьев полезно в этом контексте, потому что правильное вращение всегда будет уменьшать высоту левого поддерева дерева на единицу. Это полезно из-за умного наблюдения: очень просто удалить корень дерева, если у него нет левой подщелицы. В частности, если дерево имеет такую ​​форму:

     v
      \
       A

Затем мы можем удалить все узлы в дереве, удалив node v, а затем удалив все узлы в своем поддереве A. Это приводит к очень простому алгоритму для удаления всех узлов в дереве:

while (root is not null) {
    if (root has a left child) {
        perform a right rotation
    } else {
        delete the root, and make the root right child the new root.
    }
}

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

Кроме того, можно показать, что этот алгоритм также работает в O (n) времени. Интуитивно, это можно увидеть, посмотрев, сколько раз может быть повернуто данное ребро. Во-первых, обратите внимание, что всякий раз, когда выполняется правильное вращение, ребро, которое идет от node к его левому дочернему элементу, преобразуется в правый край, который исходит от прежнего ребенка назад к его родительскому. Затем обратите внимание, что как только мы выполним поворот, который перемещает node u в качестве правильного дочернего элемента node v, мы никогда не коснемся node u снова, пока не удалим node v и все v поддеревья слева. В результате мы можем связать количество полных поворотов, которые когда-либо будут выполнены, отметив, что каждое ребро в дереве будет вращаться с его родителем не более одного раза. Следовательно, выполняется не более O (n) поворотов, каждый из которых принимает время O (1), и сделано ровно n удалений. Это означает, что алгоритм работает во времени O (n) и использует только O (1) пространство.

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

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

Ответ 2

Позвольте мне начать с серьезной шутки: если вы установите корень BST равным null, вы фактически удалите все узлы в дереве (сборщик мусора сделает доступным пространство). Хотя формулировка является специфичной для Java, идея сохраняется для других языков программирования. Я упоминаю об этом на всякий случай, когда вы были на собеседовании или сдавали экзамен.

В противном случае все, что вам нужно сделать, это использовать измененную версию DSW algorithm. В основном превратите дерево в основу и затем удалите, как вы бы linked list. Пространство O (1) и время O (n). Вы должны найти переговоры о DSW в любом учебнике или в Интернете.

В основном DSW используется для баланса BST. Но для вашего случая, как только вы получите основу, вместо балансировки, вы удаляете, как и связанный список.

Ответ 3

Алгоритм 1, O (n) время и O (1) пространство: немедленно удалить узел, если у него нет обоих дочерних элементов. В противном случае доберитесь до самого левого узла, переворачивая "левые" ссылки, чтобы убедиться, что все узлы достижимы - самый левый узел становится новым корнем:

void delete_tree(Node *node) {
    Node *p, *left, *right;

    for (p = node; p; ) {
        left = p->left;
        right = p->right;
        if (left && right) {
            Node *prev_p = nullptr;
            do {
                p->left = prev_p;
                prev_p = p;
                p = left;
            } while ((left = p->left) != nullptr);
            p->left = p->right;
            p->right = prev_p;       //need it on the right to avoid loop
        } else {
            delete p;
            p = (left) ? left : right;
        }
    }
}

Алгоритм 2, время O (n) и пространство O (1): пересекают узлы в глубину, заменяя дочерние ссылки ссылками на родительские. Каждый узел удаляется по пути вверх:

void delete_tree(Node *node) {
    Node *p, *left, *right;
    Node *upper = nullptr;

    for (p = node; p; ) {
        left = p->left;
        right = p->right;
        if (left && left != upper) {
            p->left = upper;
            upper = p;
            p = left;
        } else if (right && right != upper) {
            p->right = upper;
            upper = p;
            p = right;
        } else {
            delete p;
            p = upper;
            if (p)
                upper = (p->left) ? p->left : p->right;
        }
    }
}

Ответ 4

Я удивлен всеми ответами выше, которые требуют сложных операций.

Удаление узлов из BST с O (1) дополнительной памятью возможно, просто заменив все рекурсивные вызовы циклом, который ищет узел и также отслеживает родительский узел текущего узла. Использовать рекурсию проще, потому что рекурсивные вызовы автоматически сохраняют всех предков искомого узла в стеке. Однако не обязательно хранить всех предков. Необходимо только сохранить искомый узел и его родительский элемент, чтобы искомый узел можно было отсоединить. Хранение всех предков - просто пустая трата пространства.

Решение в Python 3 ниже. Не сбрасывайте со стороны, казалось бы, рекурсивный вызов на delete - максимальная глубина рекурсии здесь равна 2, поскольку второй вызов на удаление гарантированно приведет к базовому случаю удаления (корневой узел, содержащий искомое значение).

class Tree(object):
    def __init__(self, x):
        self.value = x
        self.left = None
        self.right = None


def remove_rightmost(parent, parent_left, child):
    while child.right is not None:
        parent = child
        parent_left = False
        child = child.right
    if parent_left:
        parent.left = child.left
    else:
        parent.right = child.left
    return child.value


def delete(t, q):
    if t is None:
        return None

    if t.value == q:
        if t.left is None:
            return t.right
        else:
            rightmost_value = remove_rightmost(t, True, t.left)
            t.value = rightmost_value
            return t

    rv = t
    while t is not None and t.value != q:
        parent = t
        if q < t.value:
            t = t.left
            parent_left = True
        else:
            t = t.right
            parent_left = False

    if t is None:
        return rv

    if parent_left:
        parent.left = delete(t, q)
    else:
        parent.right = delete(t, q)

    return rv


def deleteFromBST(t, queries):
    for q in queries:
        t = delete(t, q)
    return t