BST mit Duplikaten

8

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

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

%Vor%

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

Sie haben mich gebeten zu zeichnen:

  1. ein binärer Baum
  2. ein unsymmetrischer binärer Suchbaum
  3. ein binärer Suchbaum ohne Duplikate
  4. ein binärer Suchbaum mit Duplikaten

Jede Hilfe ist willkommen!

PS: Helfen Sie mir, indem Sie die zugehörigen Bäume zeichnen

    
user 24.05.2013, 04:53
quelle

4 Antworten

17

Regel zum Einfügen in eine binäre Suchstruktur ohne Duplikat ist:

  1. Gehe nach links, wenn das Element kleiner als root ist
  2. Gehe nach rechts, wenn das Element größer als root ist.

Um doppelte Einträge zuzulassen, müssen Sie die Regel wie folgt ändern:

  1. Gehe nach links, wenn das Element weniger oder gleich Root ist
  2. Gehe nach rechts, wenn das Element größer als root ist.

oder

  1. Gehe nach links, wenn das Element weniger als root
    2. ist
  2. Gehe nach rechts, wenn das Element größer oder gleich root ist.

oder

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

So kann Ihr BST für das Wort "RABSAB" mit Duplikaten wie folgt aussehen:

%Vor%

Oder

%Vor%

oder

%Vor%

In den ersten zwei Fällen wird sowohl die Insertion als auch die Suche etwas komplex! Sie werden es hier mit vielen Erklärungen finden !

Und der dritte Fall ist etwas einfacher zu pflegen.

Alle werden erfolgreich verwendet, um Duplikate zu erlauben, jetzt ist die Wahl deine!

    
Sazzadur Rahaman 24.05.2013, 05:16
quelle
1

Eine Option besteht darin, den Baum so zu ändern, dass ein Zweig die Duplikate enthält, zum Beispiel haben die linken Zweige Knoten, die kleiner oder gleich dem Vater sind, oder die rechten Zweige Knoten haben, die größer oder gleich sind zum Elternteil

Eine andere Option ist, alle Duplikate in einem Knoten zu speichern, also anstelle von

%Vor%

Sie hätten stattdessen

%Vor%

oder

%Vor%     
Zim-Zam O'Pootertoot 24.05.2013 05:01
quelle
0

Bei einer normalen BST-Einfügung und -Suche treten beide basierend auf einer Regel kleiner als (& gt;) und grßer als (& lt;) auf.

Sie können stattdessen die Einfügung bei weniger als gleich (& gt; =) oder größer als gleich (& lt; =) versuchen und versuchen, die gleiche Regel für die Suche zu verwenden.

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

    
amitdonanand 24.05.2013 05:04
quelle
0

Für Ihre Eingabe RABPAB können Sie eine BST erstellen, indem Sie eine LIST 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 wird in etwa so aussehen,

%Vor%

Der Java-Code für Ihre BST-Speicherung von Integer-Werten könnte so aussehen,

%Vor%

Hier ist maxvalue die maximal möglichen gleichwertigen Schlüssel.

    
Deepu 24.05.2013 05:09
quelle

Tags und Links

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Probleme mit einer POST / PUT Json RESTful Anfrage Grails