Splay Baumeinfügungs
https://stackoverflow.com/questions/2008630
-
18-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
durch einige Übungen gehen meine Binärbaum Fähigkeiten zu verbessern, beschloss ich, einen gespreizten Baum zu implementieren, wie in Wikipedia:. Splay Baum
Eine Sache, ich bin nicht der Teil über Insertion bekommen.
Dort heißt es:
Als erstes suchen wir x in dem gespreizten Baum. Wenn x nicht bereits vorhanden ist, dann werden wir es nicht finden, aber seine übergeordneten Knoten y. Zweitens führen wir eine Splay-Operation auf die y y zu der Wurzel des Baums splay bewegen. Drittens setzen wir den neuen Knoten x als root in einer geeigneten Art und Weise. Auf diese Weise entweder y nach links oder rechts Kind der neuen Wurzel x.
Meine Frage ist: Der obige Text scheint übermäßig kurz und bündig im Vergleich zu den anderen Beispielen in dem Artikel, warum das so ist? Es scheint, gibt es einige Fallstricke hier weggelassen. Zum Beispiel nach dem y-Knoten bis zur Wurzel Spreizen, kann ich nicht einfach blind ersetzen Wurzel mit x und y tack auf x als entweder links oder rechts Kind.
Lassen Sie sich den Wert nicht davon ausgehen, bereits im Baum vorhanden ist.
Ich habe diesen Baum:
10
/ \
5 15
/ \ \
1 6 20
und ich mag 8. Mit der obigen Beschreibung einzufügen, das werde ich den 6-Knoten zu finden, auf und in einem normalen binären Baum, würde 8 als rechtes Kind des 6-Knoten hinzugefügt werden, aber hier zuerst Ich habe die 6-Knoten bis zum Wurzel spreizen:
6
/ \
5 10
/ \
1 15
\
20
dann entweder von diesen beiden sind offensichtlich falsch:
8 8
\ /
6 6
/ \ / \
5 10 5 10
/ \ / \
1 15 1 15
\ \
20 20
6 is not greater than 8 10 is not less than 8
scheint es mir, dass der einzige Weg, zuerst die Spreizung zu tun, und dann das Hinzufügen richtig den neuen Wertes als root mean würde ich die folgenden Kriterien überprüfen (für den gespreizten Knoten als linkes Kind des neuen Stammes Zugabe) :
- I der Knoten an der Wurzel gespreizt ist kleiner als die neue Wurzel (6 <8)
- das rechte Kind des Knotens I an die Wurzel gespreizt ist auch weniger als die neue Wurzel (20 8)
Wenn ich jedoch die Knoten aufzuteilen bin ich gespreizt, durch das richtige Kind zu nehmen und es als das rechte Kind des neuen Knotens angehängt, ich würde das bekommen:
8
/ \
6 10
/ \
5 15
/ \
1 20
Aber ist diese einfache Veränderung gehen geben mir immer einen richtigen Baum? Ich bin eine harte Zeit mit einem Beispiel kommen mit, konnte aber diese führen zu dem folgenden:
- Der neue Wert ich hinzufügen möchte, ist höher als die temporäre Wurzel (der Knoten I an die Wurzel gespreizt), sondern auch höher als das am weitesten links stehenden Kind des rechten Kindes der temporären Wurzel?
Ie. ein Baum, wie dies im Grunde nach dem Spreizen aussehen würde, aber bevor ich die Wurzel ersetzen?
10
/ \
5 15
/ \
11 20
und ich möchte 13 hinzuzufügen, die der neue Baum wie diese machen würde:
13
/ \
10 15
/ / \
5 11 20 <-- 11, on the wrong side of 13
oder kann dies nie passieren?
Meine zweite Frage ist: Wäre es nicht viel einfacher zu sein, nur den Vorgang wie folgt zu umschreiben:
Als erstes suchen wir x in dem gespreizten Baum. Wenn x nicht bereits vorhanden ist, dann werden wir es nicht finden, aber seine übergeordneten Knoten y. Dann fügen wir den neuen Knoten als entweder ein linkes oder rechtes Kind des Elternknotens. Drittens führen wir eine Spreizung Operation auf dem node wir hinzugefügt , die den neuen Wert bewegen an der Wurzel des gespreizten Baum.
Hervorhebung von mir zu zeigen, was ich geändert.
Lösung
Ich sehe nicht, wie das Problem, das Sie passieren beschreiben könnte. Wenn Sie 13 in diesem Baum einfügen wollen, müssen Sie zuerst finden, wo es wäre:
10
/ \
5 15
/ \
11 20
Von 10 biegen Sie rechts ab, von 15 Sie gehen Sie nach links, von 11 Sie rechts gehen ... und dann haben Sie keine Elemente mehr. Wenn 13 in dem Baum gewesen wäre, hätten wir es als rechtes Kind von 11 Jahren gefunden So nach der Regel führen wir einen gespreizten Betrieb auf 11, die 11 an die Wurzel des gespreizten Baumes bewegen wird:
11
/ \
10 15
/ \
5 20
Dann fügen wir 13 als neue Wurzel, mit 11 als linkem Kind:
13
/ \
11 15
/ \
10 20
/
5
Jetzt gibt es kein Problem.
Als erstes suchen wir x in dem gespreizten Baum. Wenn x nicht bereits vorhanden ist, dann werden wir es nicht finden, aber seine übergeordneten Knoten y. Dann fügen wir den neuen Knoten als entweder ein linkes oder rechtes Kind des Elternknotens. Drittens führen wir einen gespreizten Betrieb auf dem Knoten wir hinzugefügt, um den neuen Wert die Wurzel des gespreizten Baumes bewegen wird.
Das klingt für mich wie es auch funktionieren würde, aber wenn ich Sie wäre, würde ich versuchen, nur die Version zu implementieren, wie es in der Wikipedia beschrieben, da viele Menschen getestet haben, dass und es ist bereits gut dokumentiert.
Andere Tipps
„Splay-Baum“ sofort aus mir einen Artikel in CUJ erinnere ich mich vor einiger Zeit gelesen, könnte man einen Einblick finden dort: Implementieren von Splay-Baum in C ++ .
Drittens setzen wir den neuen Knoten x als root in einer geeigneten Art und Weise. Auf diese Weise entweder y nach links oder rechts Kind der neuen Wurzel x.
Ja, aber diese neue Wurzel x hat 2 Kinder haben, das ist, warum dieser Satz könnte verwirrend klingen.
der neue Knoten würde zu dem Baum hinzugefügt werden. Dann würde der neue Knoten gespreizt werden, um die Wurzel oder die erste Ebene von der Wurzel zu sein. Auch wenn wir einen neuen Knoten einzufügen, müssen wir die Lage finden, sie zu setzen, so dass wir tun, um eine Entdeckung. Und alle Operationen einschließlich Fund auf einem gespreizten Baum eine Spreizung Operation auslösen. Kann das ist, warum, wie, dass der Wikipedia-Artikel beschreibt es. Ich legen Sie einfach den neuen Knoten und spreizen sie auf. So oder so der Baum besser ausbalanciert als es war. funktioniert gut
