удаление в бинарном дереве поиска

Question

Мне дали два бинарных дерева поиска.Например, A и B. Затем меня попросили удалить дерево B из дерева A.

Под удалением я имею в виду удаление всех узлов, присутствующих в B, из A. Примечание: B - этонеобязательно поддерево A.

например:
A:

      50   
     / \  
    10  75  
   /   / \  
  1   60   90                 

B:

     10
     / \
    1   75

Результирующее дерево должно быть:

     50
       \
        60
         \ 
          90

Мне пришло в голову два подхода:
A1:
node * deleteTree (node ​​* A, node * B);
Возьмите корень дерева B. Удалите этот узел из дерева A (обычным методом удаления BSt).Затем разделите задачу на две части - для левого поддерева B и правого поддерева B. Для каждого поддерева выполните рекурсию.Для левого поддерева узел, который занимал удаленный узел, должен служить корнем для дерева A. Для правого поддерева преемник-порядок удаленного узла должен быть сервером в качестве корня для дерева A.

A2: Другой подход немного странный.Я нахожу обход и порядок по дереву A. Найдите и удалите все узлы в дереве B, используя бинарный поиск и рекурсию (мы не изменяем предзаказ).Наконец, реконструируем наш bst из порядка (оставшегося) и предзаказа (без изменений).

Вероятность A: Найти эффективный путь для BST.
Вероятность B: Найти эффективный путь для любого двоичного дерева (не толькоBST).

Answer 1

Задача A

Я предполагаю, что два дерева сбалансированы.

void deleteTree(node* A, node* B)
{
    if(A == NULL || B == NULL)
        return;

    if(A->data == B->data)
    {
        deleteTree(A->left, B->left);
        deleteTree(A->right, B->right);
        removeNode(A); // Normal BST remove
    }
    else if(A->data > B->data)
    {
        Node* right = B->right;
        B->right = NULL;
        deleteTree(A->left, B);
        deleteTree(A, right);
    }
    else // (A->data < B->data)
    {
        Node* left = B->left;
        B->left = NULL;
        deleteTree(A->right, B);
        deleteTree(A, left);
    }
}

Сложность времени:

T(N) = 2 * T(N / 2) + O(1)

Таким образом, общая сложность равна O (N) согласно основной теореме.Сложность пространства составляет O (1) .Одним из недостатков является то, что я уничтожил B.

PS: У меня нет реализации BST, поэтому я не могу протестировать код для вас.Но я думаю, что идея верна.

Задача B

Использовать хеш-таблицу для одного дерева и обходить другое.Вы получите O (N) за сложность времени и пространства.

Answer 2

Как я понимаю, почему бы вам не выполнить обход по порядку b.Затем, пока массив не будет пустым, выполните обычное удаление из a для значения индекса массива.Обход O (n) и удаление для каждого индекса будет O (logn).Всего эта операция будет O (nlogn).