Удалить дубликаты из двоичного дерева

Question

Im пытается придумать алгоритм для удаления дубликатов из двоичного дерева/дерева двоичного поиска. Пока что лучшее, что я мог придумать, было

Магазин Обход обхода дерева в массиве.
Если дерево не имеет порядка, сортируйте массив.
удалите дубликаты из массива и восстановите двоичное дерево.

Нужно ли хранить предварительный обход дерева и реконструировать дерево?

Это ставит сложность на O(n log n) раз и O(n) пространство. Мы можем сделать лучше? Псевдо образцы кода/кода будут оценены

EDIT 1: Предположим, что структура двоичного дерева задается следующим объектом

public class Node 
{ 
    int data; 
    Node right; 
    Node left; 
// getters and setters for the left and right nodes 
} 

Answer 1

Весь фокус в этой ситуации, чтобы не хранить дубликаты, чтобы начать с. ...

Когда вы добавляете узлы в дерево, почему вы не можете принять решение не добавлять узел, если он уже имеет дубликат в дереве?

Answer 2

У меня есть странная идея:

Если у вас уже есть дерево с дубликатами и нужно построить новый без дубликатов, то вы можете просто:

1. Создание пустой HashMap узла значения
2. Создать новое дерево
3. Пройдите существующее дерево в любом порядке и получите элементы по одному
4. Если элемент уже присутствует на карте хэша, то не добавляйте его в новый дерево

Это нормально)

Answer 3

Удалить дубликаты алгоритм бинарного дерева поиска:

1. Начало дерево ходьбы (в/до/после заказа)

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

   Если значение ключа найдено по дереву, вызовите delete (key) и повторите шаг 2 (возможно, у вас есть несколько дубликатов).

   Повторите шаг 2 до тех пор, пока ключ не будет найден в подэлементе.Затем вернитесь к шагу 1

Временной сложности - O(nlogn) (Для каждого из n элементов сделать бинарный поиск, который принимает logn время)

Space Сложности - O(logn) (для стека пространства, используемого в рекурсии)

Answer 4

Предлагаемое Рекурсивное решения для вашей проблемы: -

deleteDup(Node p) { 

    if(p == NULL) return 

    else { 

    deleteDup(p.left) 
    deleteDup(p.right) 
    delete(p.value,p.left) 
    delete(p.value,p.right) 

    } 

} 

deleteDup(root) 

Ti меня сложности:

Удаление в BST = O(logN)

T(N) = 2T(N/2) + O(logN) 
T(N) = O(N) 

Space Сложность: O(logN)

Примечание: - Предполагая, что уравновешивается BST

Answer 5

У меня была еще одна идея, которая работает в O (N) времени и O (n). Например, у нас есть дерево с корнем A и двумя детьми А и В. A B

1. Создание карты подсчета, которая отображает каждое значение в дереве отсчету.
2. Пройдите все элементы в дереве, чтобы заполнить подсчеты. Получим отсчеты [A] = 2 и подсчитаем [B] = 1. Это занимает O (n) пространство и O (n) время.
3. Снова, перемещайте все элементы в дереве. Для каждого элемента проверьте, есть ли counts [element]> 1, и если это так, мы устанавливаем counts [element] - и удаляем этот элемент (с помощью удаления/вращения двоичного дерева). Это время O (n).
4. После того, как сделано, у дерева больше нет дубликатов!