BST mit Duplikaten

Question

Ich weiß, dass BST keine Duplikate erlaubt. Zum Beispiel, wenn ich ein Wort "RABSAB" habe.

Der binäre Suchbaum für die obige Zeichenfolge ist:

R 
    /\ 
    A S 
    \ 
    B 

Was passiert, wenn wir die Duplikate im Baum enthalten wollten. Wie wird sich der Baum verändern? Diese Frage wurde mir in einem Interview gestellt.

Sie fragten mich ziehen zu:

1. ein binärer Baum
2. eine unausgewogene binärer Suchbaum
3. ein Baum binäre Suche ohne Duplikate
4. ein binärer Suchbaum mit Dubletten

Jede Hilfe ist willkommen!

PS: mir zu gestalten, indem die entsprechenden Bäume

Zeichnung

Answer 1

Regel in einem binären Suchbaum ohne Duplikat einzufügen ist:

1. Gehen Sie links, wenn das Element weniger als Wurzel ist
2. Gehen Sie rechts, wenn das Element größer ist als Wurzel ist.

Und doppelte Einträge zu ermöglichen, haben Sie die Regel wie unten zu ändern:

1. Gehen Sie links, wenn das Element kleiner oder gleich Wurzel
2. Gehen Sie rechts, wenn das Element größer ist als Wurzel ist.

oder

1. Go links, wenn das Element weniger als Wurzel ist
2. Go rechts, wenn das Element größer oder gleich Wurzel ist.

oder

1. Go links, wenn das Element weniger als Wurzel ist
2. Go rechts, wenn das Element größer als Wurzel ist.
3. Erhöhen Sie die Anzahl, wenn das Element gleich der Wurzel ist.

Also Ihr BST für Wort "RABSAB", mit Dubletten können wie:

 R 
    /\ 
    A S 
/\ 
A B 
    /
    B 

Oder

 R 
    /\ 
    A S 
    \ 
    A 
     \ 
     B 
     \ 
     B 

oder

R(1) 
/\ 
/ \ 
A(2) S(1) 
    \ 
    \ 
    B(2) 

In ersten zwei Fälle, beide Einfügen und Suchen wird etwas komplex! Sie finden es here mit viel Erklärung!

Und der dritte Fall ist etwas einfacher zu pflegen.

Alle von ihnen werden erfolgreich verwendet, um Duplikate zu erlauben, jetzt haben Sie die Wahl!

Answer 2

Eine Möglichkeit ist, den Baum so zu modifizieren, dass ein Zweig wird die Duplikate enthalten, zum Beispiel haben die linken Zweige Knoten halten, die kleiner oder gleich der Eltern haben alternativ die richtigen Zweige Knoten halten, die an die Mutter größer oder gleich sind

eine weitere Option ist es, alle Duplikate in einem Knoten zu speichern, so dass anstelle von

class Node { 
    Node left, right; 
    Object data; 
} 

du stattdessen haben

class Node { 
    Node left, right; 
    List data; 
} 

oder

class Node { 
    Node left, right; 
    Object data; 
    int count; 
} 

Answer 3

In einem normalen BST Einsetzen und suchen beide auftreten, basierend auf weniger als (>) und größer als (<) Regel.

Sie könnten stattdessen versuchen, auf weniger als gleich (> =) oder größer als gleich (< =) einzufügen und versuchen, dieselbe Regel für die Suche zu verwenden.

Alternativ können Sie in jeden Knoten ein Array einfügen, um doppelte Elemente aufzunehmen.

Answer 4

Für Ihre Eingabe RABPAB können Sie eine BST erstellen, indem Sie eine LISTE verwenden, um alle gleichwertigen Schlüssel zu speichern. Alle gleichwertigen Schlüssel werden auf derselben Ebene unter Verwendung einer Datenstruktur platziert, die sie speichern kann.

Die BST etwas wie folgt aussehen,

 R 
    /\ 
A--A P 
    \ 
    B--B 

Der Java-Code für Ihre BST ganzzahlige Werte zu speichern, wie dies sein könnte,

class Node 
{ 
    Node left, right; 
    int data[maxvalue]; 
} 

Hier maxvalue ist die maximal mögliche gleich bewertet Tasten.