Definieren wir eine Funktion split(T,v)
, die einen Baum aufnimmt, T
und einen Wert, bei dem geteilt werden soll v
. Angenommen, jeder Knoten des Baums speichert zusätzlich zum Wert an diesem Knoten sein linkes und rechtes Kind. Verwenden Sie den folgenden Algorithmus:
Zuerst prüfen wir, ob der Eingabebaum einfach ein Blatt ist oder nicht.
Wenn T
es sich nicht um ein Blatt handelt, vergleichen Sie den Wert seines Wurzelknotens v'
mit v
.
Wenn v' < v
dann rekursiv split im linken Teilbaum aufrufen. Speichern Sie die Werte des rekursiven Aufrufs als L'
(zurückgegebener linker Baum), R'
(zurückgegebener rechter Baum) und r
(Optionstyp gibt an, ob der Wert v
gefunden wurde oder nicht). Konstruieren Sie den neuen rechten Baum newR = Node(R',v',R)
und kehren Sie zurück (L',r,newR)
.
Else wenn v' > v
dann rekursiv Split auf dem rechten Unterbaum nennen. Speichern Sie die Werte des rekursiven Aufrufs als L'
(zurückgegebener linker Baum), R'
(zurückgegebener rechter Baum) und r
(Optionstyp gibt an, ob der Wert v
gefunden wurde oder nicht). Konstruieren Sie den neuen linken Baum newL = Node(L',v',L)
und kehren Sie zurück (newL,r,R')
.
Andernfalls v' = v
kehren Sie zurück L, SOME(v), R
.
Wenn T
es sich um ein Blatt handelt, müssen wir die Wurzel des Baums erreicht haben, ohne den Eingabewert v zu finden, bei dem geteilt werden soll. Geben Sie zurück, dass Sie das Blatt nicht finden konnten, indem Sie zurückgehen NONE
.
Warum ist das logarithmisch? Nun, Sie überqueren höchstens einen Wurzel-Blatt-Pfad des Baumes. Wir können Knoten leicht in konstanter Zeit rekonstruieren, da wir nur -Referenzen (in einer imperativen Sprache) neu zuweisen oder -Werte neu zuweisen , deren Generierung (in einer funktionalen Sprache eine konstante Zeit in Anspruch nimmt) ).O(logn)O(logn)
Hier ist der entsprechende Code für den Algorithmus. Es ist in SML geschrieben, aber ich wäre bereit zu klären, was irgendetwas in den Kommentaren bedeutet.
fun split(T,v) =
case T of
Leaf => (Leaf, NONE, Leaf)
| Node(L,v,R) =>
case compare(v, v') of
LESS =>
let
val (L',r,R') = split(L,k)
in
(L',r,Node(R',r,R))
end
| GREATER =>
let
val (L',r,R') = split(R,k)
in
(Node(L',v',L),r,R')
end
| EQUAL => (L, SOME(v), R)
Weitere Informationen finden Sie in diesem Dokument . Es bietet eine gründlichere Erklärung der oben genannten.