7.1 insert

AlexanderP
Erstie
Erstie
Beiträge: 21
Registriert: 18. Apr 2013 12:12

7.1 insert

Beitrag von AlexanderP »

Hallo,
ich bin etwas verwirrt. Der Induktionsschritt 1.1.2 im WiKi lautet:

1. if(p.key == K)
1.1 if(p.left == void)
1.1.2 -> p.left.key = K und p.left.left = void, p.left.right=void


Soll das etwa bedeuten, dass hier ein Duplicat eingefügt wird, weil wir ja schon p.key == K haben?

mfg Alex

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: 7.1 insert

Beitrag von JannikV »

Jop. Ein Baum darf im Allgemeinen durchaus Duplikate enthalten. Muss ja nicht unbedingt ein Set sein.

Benutze ich den Baum, zum Beispiel, um einen Heap, den ich als Queue verwenden will, zu implementieren, dann ist ja vollkommen gewollt, dass da Werte mehrfach vorkommen können.
Wenn ich mit dem Baum aber ein Set implementieren will, würde man auf das Einfügen von Duplikaten verzichten.

VG

AlexanderP
Erstie
Erstie
Beiträge: 21
Registriert: 18. Apr 2013 12:12

Re: 7.1 insert

Beitrag von AlexanderP »

Okey danke!

AnnaW
Mausschubser
Mausschubser
Beiträge: 77
Registriert: 29. Jul 2012 23:05

Re: 7.1 insert

Beitrag von AnnaW »

Hallo,

ich habe auch noch eine kurze Frage zu insert. In der Invariante heißt es, "The key K is in the range of v". In dem Video über Binäre Suchbäume wird aber keine Range erklärt. Verstehe ich das richtig, dass das heißt, dass ivh von dem Knoten v direkt zu dem Key K komme? Also, dass es praktisch ein Geschwister ist?

Viele Grüße

Anna

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: 7.1 insert

Beitrag von JannikV »

Hi,

in-range bedeutet simpel ausgedrückt dass man bisher immer richtig den Baum entlang gegangen ist, also der Key noch durch weiter absteigen erreichbar ist.
Im Gegensatz dazu ist der Key nicht in-range des aktuellen Knotens wenn ich beispielsweise in folgendem Bild den Key 4 suche, aber grade beim Knoten 3 bin.
Ich wäre aber in-range wenn ich bei 2 wäre.
Bild

AnnaW
Mausschubser
Mausschubser
Beiträge: 77
Registriert: 29. Jul 2012 23:05

Re: 7.1 insert

Beitrag von AnnaW »

Ah alles klar :-) Danke für die Erklärung :-)

ONeff
Neuling
Neuling
Beiträge: 10
Registriert: 19. Okt 2011 01:19
Kontaktdaten:

Re: 7.1 insert

Beitrag von ONeff »

Wie ist das nun, wenn ich in diesem Beispielbaum, der hier gezeigt wird nun zum Beispiel eine 2 Hinzufügen möchte. Laut Wiki springt der Pointer doch dann zum linken Knoten, dass heißt der die 2 wird dann hinter die 4 links angefügt, oder nicht ?
Also haben wir eine 2 über der 4 und die andere 2 links hinter der 4.

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: 7.1 insert

Beitrag von JannikV »

Ganz genau.

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: 7.1 insert

Beitrag von JannikV »

ACHTUNG: mir ist hier ein großer Fehler passiert. Als ich nach Binärbaum gegoogelt habe und dann das obige Bild von Wikipedia übernommen habe um in-range zu erklären ist mir nicht aufgefallen, dass das ja gar kein Binary-search-tree ist x_X

Wenn dann dürfen die Zahlen die da stehen nicht als Key-Inhalt betrachtet werden, sondern einfach nur als Indexnummer eines Knotens um darüber sprechen zu können.

VG

derJan2
Windoof-User
Windoof-User
Beiträge: 39
Registriert: 23. Mai 2012 21:37

Re: 7.1 insert

Beitrag von derJan2 »

Hallo Jannik,

zusammen mit dem fehlerhaften Bild ist deine Erklärung von "range" vielleicht etwas widersprüchlich. Bei dir klingt es so, als ob sich der range auf die konkreten Schlüsselwerte bezieht, die in den Nachfolgerknoten stehen. Ich versuche mich mal an einer eigenen Erklärung, du darfst mich dann gerne verbessern.

Der range ist der Wertebereich der Schlüsselwerte, den ein Knoten enthalten könnte. Die root kann alle Werte enthalten, also als Intervall (-unendlich, unendlich). Rechte Nachfolgerknoten haben den gleichen range wie ihr Vorgängerknoten, nur dass die linke Intervallgrenze nun durch den Schlüsselwert des Vorgängerknotens gegeben ist. Umgekehrt haben linke Nachfolgerknoten den gleichen range wie ihr Vorgängerknoten, nur dass die rechte Intervallgrenze nun durch den Schlüsselwert des Vorgängerknotens gegeben ist.

Im Beispiel unten ist der range der Wurzel (-unendlich, unendlich),
der range des Knotens mit key = 14 ist [6, unendlich)
und der range des Knotens mit key = 13 ist [6,14].

Bild

Gruß, derJan2

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: 7.1 insert

Beitrag von JannikV »

Jop, so sollte es jetzt aber stimmen ^^

Antworten

Zurück zu „Archiv“