Usuń duplikaty z drzewa binarnego - algorytm, język-agnostyk, drzewo, drzewo binarne

Próbuję wymyślić algorytm do usuwania duplikatów z drzewa binarnego drzewa / binarnego wyszukiwania. Jak dotąd najlepsze, co mogłem wymyślić, było

Przechowuj kratkę drzewa w tablicy w trybie Inorder.
Jeśli drzewo nie ma porządku, posortuj tablicę.
usuń duplikaty z tablicy i zrekonstruuj drzewo binarne.

Czy musimy również przechować przedtrawowe drzewo, aby zrekonstruować drzewo?

To stawia złożoność na O(n log n ) czas i O(n) przestrzeń. Czy możemy zrobić lepiej? Pseudo-kodowe / kodowe próbki będą docenione

EDYCJA 1: Przyjmijmy, że struktura drzewa binarnego jest podana przez następujący obiekt

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

Odpowiedzi:

2 dla odpowiedzi № 1

Usuń zduplikowany algorytm dla drzewa wyszukiwania binarnego:

1. Rozpocznij spacer po drzewie (w / przed / po zamówieniu)

2. W każdym węźle wykonaj wyszukiwanie binarne na poddrzewie zakorzenionym w tym węźle dla wartości klucza przechowywanej w węźle.

   Jeśli klucz znajduje się w drzewie, wywołaj delete (klucz) i zrestartuj krok 2 (może mieć wiele duplikatów).

   Powtarzaj krok 2, aż klucz nie zostanie znaleziony w podsieci. Następnie wróć do kroku 1

Złożoność czasu - O(nlogn) (Dla każdego z n elementy wykonują binarne wyszukiwanie, które trwa logn czas)

Złożoność przestrzeni - O(logn) (dla przestrzeni stosu używanej w rekursji)

---

0 dla odpowiedzi nr 2

Mam dziwny pomysł:

Jeśli masz już drzewo z duplikatami i potrzebujesz zbudować nowe bez duplikatów, możesz po prostu:

1. Utwórz pustą mieszankę wartości węzłów
2. Utwórz nowe drzewo
3. Przechyl istniejące drzewo w dowolnej kolejności i pobieraj elementy jeden po drugim
4. Jeśli element jest już obecny w mapie mieszania, nie dodawaj go do nowego drzewo

Czy to jest w porządku?)

---

0 dla odpowiedzi № 3

Proponowane rozwiązanie rekurencyjne dla Twojego problemu: -

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)

Złożoność czasu:

Usunięcie w BST = O(logN)

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

Złożoność przestrzeni: O(logN)

Uwaga:- Zakładając zrównoważony BST

---

0 dla odpowiedzi nr 4

Miałem inny pomysł, który działa w przestrzeni O (n) i O (n). Na przykład mamy drzewo z korzeniem A i dwoje dzieci A i B. ZA A B

1. Utwórz liczniki Map, które mapują każdą wartość w drzewie na liczbę.
2. Przetestuj wszystkie elementy w drzewie, aby zaliczyć liczbę. Otrzymamy zliczenia [A] = 2 i liczymy [B] = 1. Zajmuje to przestrzeń O (n) i czas O (n).
3. Ponownie przechodź przez wszystkie elementy w drzewie. Dla każdego elementu sprawdź, czy liczy [element]> 1, a jeśli tak, ustawiamy counts [element] -, i usuwamy ten element (używając drzewa binarnego do usunięcia / rotacji). To jest czas O (n).
4. Po zakończeniu drzewo nie ma już duplikatów!

---

-1 dla odpowiedzi № 5

Sztuczka w tej sytuacji polega na tym, aby nie przechowywać duplikatów na początek ....

Po dodaniu węzłów do drzewa, dlaczego nie można podjąć decyzji o dodaniu węzła, jeśli ma on już duplikat w drzewie?

---