Die Zeit-Komplexität für das löschen im binären Suchbaum

Davon ausgehen, die Höhe des BST ist h.
Wenn wir wollen, löschen eines Knotens mit zwei Kindern, was wäre dann die Zeit, die Komplexität des Prozesses.

Ich weiß, dass in einem normalen binären Baum, die Zeit-Komplexität für das löschen ist O(h); O(n) worst case O(logn) besten Fall. Aber seit wir ersetzen die Schlüssel für das löschen von Knoten mit den minimalen Knoten des rechten Unterbaum, es wird mehr Zeit zu finden, die minimale Schlüssel.

Also weiß jemand, wie erklären Sie sich die Zeit, die Komplexität in dieser situation?

InformationsquelleAutor devinda kariyawasam | 2014-12-15
  1. 5

    Quelle Wikipedia :

    Löschung

    Gibt es drei mögliche Fälle zu betrachten:

    • Löschen eines Blattes (Knoten ohne Kinder): Löschen eines Blattes ist einfach, denn wir können einfach entfernen Sie es aus dem Baum.

    • Löschen eines Knotens mit einem Kind: Entfernen Sie die Knoten und ersetzen Sie es mit Ihrem Kind.

    • Löschen eines Knotens mit zwei Kindern: Rufen Sie die Knoten, die gelöscht werden N. nicht löschen N. wählen Sie Stattdessen entweder den in-order Nachfolger-Knoten oder den in-order Vorgänger-Knoten, R. Kopieren Sie den Wert von R zu N, dann (rekursiv rufen Sie löschen auf R bis zum erreichen einer der ersten beiden Fälle. Wenn Sie in-order-Nachfolger zu einem Knoten, als rechten Unterbaum ist nicht NULL( Unsere vorliegenden Fall ist der Knoten hat 2 Kinder), dann seine in-order Nachfolger ist der Knoten mit dem geringsten Wert im rechten Unterbaum haben, die bei maximal 1 sub-Baum, so löschen Sie fallen würde in einer der ersten 2 Fällen.

    Die Zeit-Komplexität für das löschen im binären SuchbaumLöschen eines Knotens mit zwei Kindern aus einem binären Suchbaum. Zuerst den rechten Knoten in den linken Teilbaum, der inorder-Vorgänger 6, gekennzeichnet ist. Sein Wert wird kopiert und in den Knoten wird gelöscht. Der inorder-Vorgänger kann dann leicht gelöscht werden, weil es hat höchstens ein Kind. Die gleiche Methode funktioniert auch symmetrisch mit der inorder-Nachfolger gekennzeichnet 9.

    Konsequent mit den in-order Nachfolger oder die in-order-Vorgänger für jede Instanz der zwei-Kind-Fall kann es zu einer unausgeglichenen Baum, so dass einige Implementierungen wählen Sie eine oder das andere zu verschiedenen Zeiten.

    Laufzeitanalyse:

    Obwohl dieser Vorgang nicht immer traverse den Baum zu einem Blatt, das ist immer eine Möglichkeit; somit im schlimmsten Fall es benötigt Zeit proportional zur Höhe des Baumes. Es benötigt nicht mehr, auch wenn der Knoten zwei Kinder hat, seit es folgt noch einen einzigen Weg und nicht besuchen Sie jeden Knoten zweimal. Daher der Zeiger Anpassungen in allen drei Fällen benötigen Konstante Zeit.

    Nützliche Links :

    InformationsquelleAutor Rockstar
Schreibe einen Kommentar