Ich hatte diese Frage während einer Prüfung und konnte keine schnelle Antwort finden.
Es gibt ein Array A mit einigen geordneten Zahlen A = [1,3,6,9,11] und ein BST mit Zahlen als Schlüssel. Ich muss einen effizienten rekursiven Algorithmus zur Verfügung stellen, um die Zahlen in A von der BST zu löschen.
Das Problem, das ich habe, ist nicht das Löschen der Knoten, sondern die Verwendung der Tatsache, dass das Array beim Löschen der Knoten geordnet ist.
Kann mir jemand mit einigen Tipps helfen?
Hier ist ein möglicher Ansatz.
Sie könnten gleichzeitig sowohl die BST (mit dem rekursiven Standardalgorithmus ) als auch A (von links) durchqueren nach rechts). Jede der Durchquerungen ergibt Elemente in aufsteigender Reihenfolge. Sie suchen nach übereinstimmenden Elementen, um sie aus der Baumstruktur zu löschen.
Ein naive Algorithmus hat O(size(BST)) Zeitkomplexität.
In einigen Fällen können Sie es vermeiden, den linken Teilbaum vollständig zu betrachten: Der Wert des "aktuellen" Knotens im Baum gibt Ihnen eine obere Grenze für die Werte im linken Teilbaum, also wenn dieser kleiner ist als der Wert des "current" Element von A , überspringe den linken Teilbaum.
Sie können den Algorithmus auch stoppen, sobald Sie A erschöpft haben.
Lassen Sie eine BST durch ihren Wurzelknoten dargestellt werden.
Die Funktion delete-array-from-bst mit den Argumenten array und bst ist:
array oder bst leer ist: return Das Teilen des Arrays ist eine binäre Suche, so dass Sie nicht jeden Array-Wert mit dem Root-Knoten vergleichen müssen. Die Subarrays können die Struktur mit dem ursprünglichen Array teilen. Wenn Sie den gleichen Wert zuletzt löschen, wird sichergestellt, dass Sie nicht die schlechteste Löschbedingung für jeden Wert im Array treffen.
Tags und Links algorithm