Lösche Duplikate aus dem Binärbaum - Algorithmus, sprachunabhängig, Baum, Binärbaum

Ich versuche, einen Algorithmus zum Löschen von Duplikaten aus einem Binärbaum / binären Suchbaum zu finden. Bisher war das Beste, was ich mir vorstellen konnte

Store Inorder-Traversal des Baums in einem Array.
Wenn der Baum keine Reihenfolge hat, sortieren Sie das Array.
Entferne Duplikate aus dem Array und rekonstruiere den Binärbaum.

Müssen wir die Vorbestellung des Baumes speichern, um den Baum zu rekonstruieren?

Dies bringt die Komplexität auf O(n log n ) Zeit und O(n) Raum. Können wir es besser machen? Pseudocode / Codebeispiele würden geschätzt werden

EDIT 1: Nehmen Sie an, dass die Struktur des Binärbaums durch das folgende Objekt gegeben ist

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

Antworten:

2 für die Antwort № 1

Entfernen Sie doppelten Algorithmus für eine binäre Suchstruktur:

1. Beginne einen Baumspaziergang (in / vor / nach Bestellung)

2. Führen Sie an jedem Knoten eine binäre Suche in dem Teilbaum durch, der an diesem Knoten für den im Knoten gespeicherten Schlüsselwert verwurzelt ist.

   Wenn der Schlüsselwert in der Baumstruktur gefunden wird, rufen Sie delete (key) auf und starten Sie Schritt 2 (möglicherweise mehrere Duplikate) neu.

   Wiederholen Sie Schritt 2, bis die Taste nicht in der Unterstruktur gefunden wurde. Dann gehe zurück zu Schritt 1

Zeitkomplexität - O(nlogn) (Für jeden der n Elemente tun eine binäre Suche, die dauert logn Zeit)

Raumkomplexität - O(logn) (für den Stack-Platz, der in der Rekursion verwendet wird)

---

0 für die Antwort № 2

Ich habe eine komische Idee:

Wenn Sie bereits einen Baum mit Duplikaten haben und den neuen ohne Duplikate erstellen müssen, können Sie einfach:

1. Erstelle leere hashmap der Knotenwerte
2. Erstelle einen neuen Baum
3. Durchqueren Sie den vorhandenen Baum in beliebiger Reihenfolge und erhalten Sie Elemente einzeln
4. Wenn das Element bereits in der Hash-Map vorhanden ist, fügen Sie es nicht zu new hinzu Baum

Ist es o.k?)

---

0 für die Antwort № 3

Vorgeschlagene rekursive Lösung für Ihr Problem: -

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)

Zeit Komplexität:

Löschung in BST = O(logN)

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

Raumkomplexität: O(logN)

Hinweis:- Angenommen, ausgewogene BST

---

0 für die Antwort № 4

Ich hatte eine andere Idee, die in O (n) Zeit und O (n) Raum läuft. Zum Beispiel haben wir einen Baum mit Wurzel A und zwei Kindern A und B. EIN A B

1. Erstellen Sie eine Kartenzählung, die jeden Wert in der Baumstruktur einer Zählung zuordnet.
2. Durchqueren Sie alle Elemente in der Baumstruktur, um die Anzahl zu erhöhen. Wir erhalten Zählungen [A] = 2 und zählen [B] = 1. Dies benötigt O (n) Raum und O (n) Zeit.
3. Durchqueren Sie erneut alle Elemente im Baum. Prüfen Sie für jedes Element, ob counts [element]> 1 ist und wenn ja, setzen wir counts [element] -, und löschen Sie dieses Element (mithilfe der Binärbaumlöschung / -rotation). Dies ist O (n) Zeit.
4. Sobald das erledigt ist, hat der Baum keine Duplikate mehr!

---

-1 für die Antwort № 5

Der Trick in dieser Situation ist, die Duplikate nicht zu speichern, um damit zu beginnen ....

Wenn Sie die Knoten zum Baum hinzufügen, warum können Sie die Entscheidung treffen, den Knoten nicht hinzuzufügen, wenn er bereits ein Duplikat in der Struktur hat?

---