Ich habe eine Datenstruktur-Hausaufgabe, die zusätzlich zu den regulären AVL-Baumfunktionen eine Funktion hinzufügen muss, die die minimale Lücke zwischen zwei beliebigen Zahlen im AVL-Baum zurückgibt (die Knoten in der AVL stellen tatsächlich Zahlen dar).
Nehmen wir an, wir haben die Nummern (als Knoten) 1 5 12 20 23 21 im AVL-Baum, die Funktion sollte die minimale Lücke zwischen zwei beliebigen Zahlen zurückgeben. In dieser Situation sollte es "1" zurückgeben, was | 20-21 | ist oder | 21-20 |.
Es sollte in O (1) gemacht werden.
Ich habe versucht, viel darüber nachzudenken, und ich weiß, dass es einen Trick gibt, aber ich konnte ihn einfach nicht finden. Ich habe Stunden damit verbracht.
Es gab noch eine andere Aufgabe, nämlich die maximale Lücke zu finden. Das ist einfach, es ist der Unterschied zwischen der minimalen und maximalen Anzahl.
Sie müssen die Datenstruktur erweitern, sonst können Sie keine O (1) Suche nach der minimalen Lücke zwischen den Zahlen, die den Baum bilden, erhalten.
Sie haben die zusätzliche Einschränkung, die Zeitkomplexität der Einfüge- / Lösch- / Suchfunktion nicht zu erhöhen, und ich gehe davon aus, dass Sie auch die Komplexität des Platzes nicht erhöhen wollen.
Betrachten wir einen generischen Knoten r , mit einem linken Teilbaum r.L und einem rechten Teilbaum r.R ; Wir erweitern die Informationen im Knoten r zusätzliche Zahl r.x als Mindestwert zwischen definiert:
(oder nicht definiert, wenn keine der vorherigen Bedingungen gültig ist, im Falle eines Blattknotens)
Um schnelles Einfügen / Löschen zu ermöglichen, müssen wir zusätzlich in jedem internen Knoten die Referenzen zu seinen linken und rechten Blattknoten hinzufügen.
Das sehen Sie mit diesen Ergänzungen:
Die kleinste Lücke im Baum ist der x Wert des Wurzelknotens, genauer gesagt ist für jeden Teilbaum die minimale Lücke in den Teilbaumelementen nur der Teilbaum root x Wert.
Der Beweis dieser Aussage kann durch Rekursion gemacht werden: Betrachten wir einen Baum, der durch den Knoten r verwurzelt ist, mit einem linken Teilbaum r.L und einem rechten Teilbaum r.R . Die induktive Hypothese lautet, dass die Wurzeln der Werte r.L und r.R x die Werte der minimalen Lücken zwischen den Knotenwerten des Teilbaums sind. Es ist offensichtlich, dass die minimale Lücke gefunden werden kann, wenn nur die Paare von Knoten mit Werten berücksichtigt werden, die in der wertsortierten Liste benachbart sind; Die Paare, die durch Werte gebildet werden, die von den Knoten von rL gespeichert werden, haben ihre minimale Lücke im Wert rL root x . Gleiches gilt für die Rechte Teilbaum. Gegeben ist (jeder Wert von Knoten in r.L ) & lt; Wert von L Wurzelknoten & lt; (alle Werte von Knoten in r.R ), die einzigen Paare benachbarter Werte, die nicht berücksichtigt werden, sind zwei:
Der r.L -Knoten mit dem höheren Wert ist sein rechtes Blatt von den AVL-Baumeigenschaften, und der r.R -Knoten mit dem niedrigeren Wert ist sein linkstes Blatt. Zuweisen zu rx Wert ist der minimale Wert zwischen den vier Werten (rL root x Wert, rR root x Wert, (r - rL root) Lücke, (r - rR root) Lücke ist die gleiche zuzuweisen die kleinere Lücke zwischen aufeinanderfolgenden Knotenwerten in dem gesamten Baum, die äquivalent zu der kleineren Lücke zwischen jedem möglichen Paar von Knotenwerten ist. Die Fälle, in denen einer oder zwei der Unterbäume leer sind, sind trivial. In den Basisfällen eines Baumes, der nur aus einem oder drei Knoten besteht, ist es trivial zu sehen, dass der x-Wert der Baumwurzel der minimale Lückenwert ist.
Diese Funktion könnte für Sie hilfreich sein:
%Vor%Hier ist die Node-Datenstruktur:
%Vor%Tags und Links search data-structures tree avl-tree