Wie würden Sie einen ausgeglichenen Baum mit Lazy Deletionen implementieren?

Question

Genauer gesagt, ein AVL-Baum. Ist es möglich? Ich würde es gerne tun, aber ich denke, dass die nicht gelöschten Knoten problematisch sein können, um mit den Rotationen umzugehen.

Ich habe eine, die normal funktioniert, aber ich möchte diese mit faul löschen für etwas anderes verwenden.

Answer 1

Wenn Sie wollen, dass es in Bezug auf alle Knoten (einschließlich der markierten gelöscht) "ausgeglichen" bleibt, müssen Sie nichts tun - Sie sind schon da.

Wenn Sie wollen, dass es in Bezug auf die Gruppe der nicht gelöschten Knoten "ausgeglichen" bleibt - die Frage ist warum? Der ganze Sinn des Balancing ist die Vermeidung von Run-away-Suchen (linear worst case) und das hängt von den Knoten ab, nicht von ihrem Löschstatus.

Answer 2

Was genau löscht nicht im Zusammenhang mit einem AVL-Baum?

Es könnte bedeuten, Sie tun keine Arbeit an der Löschung, das heißt, Sie aktualisieren den Baum überhaupt nicht.

Dies führt dazu, dass der Baum nicht richtig ausbalanciert wird, da der Aufwärtsscan nach Balance-Faktoren mit falschen Balance-Faktoren arbeitet.

Es könnte bedeuten, die Balance-Faktoren zu aktualisieren, aber nicht auszugleichen.

Das bedeutet, Sie würden enden, wenn Sie sich dazu entschieden haben, etwas zu löschen, mit einem Balance-Faktor größer als 2 oder kleiner als -2; was bedeutet, dass mehrere Rotationen korrigiert werden müssen. Das Problem hierbei ist jedoch, dass Sie bei einer Rotation nicht mehr wissen können, ob Sie eine Teilbaumtiefe eliminiert haben oder nicht. Denn obwohl Sie wissen, dass auf einer Seite 3 Unterbaumtiefen zu viele sind, wissen Sie nicht mehr, dass genau ein Element jede Ebene dieser zusätzlichen Tiefe verursacht - etwas, das Sie normalerweise wissen, weil Sie einzelne Elemente gleichzeitig hinzufügen oder entfernen - Sie haben keine Ahnung, wie viele Umdrehungen Sie machen müssen. Sie könnten drei Rotationen machen und nur eine Teilbaumtiefe verloren haben, weil es zwei Elemente in dieser Tiefe gab. In der Tat, wie würden Sie überhaupt in der Lage sein, welche Elemente zu drehen, um die notwendigen Elemente zu bekommen? Sie würden nicht unbedingt alle in dem Pfad von Ihrem ausgewählten Element löschen und der Punkt, wo der Balance-Faktor 3 ist.

Ich bin mir nicht sicher, aber ich werde auf einem Ast gehen und sagen, faul löscht bricht AVL wie wir wissen.

Warum sollten Sie sowieso verzögern? Der ganze Sinn von AVL besteht darin, die Kosten für die Neugewichtung über jedes Add/Delete zu amortisieren, so dass Sie bei O bleiben (log n) - warum sollten Sie Rebalancing-Schulden für größere, weniger häufige Rebalancing-Prozesse aufbauen?