Stellen Sie sich vor, dass Sie auf einem Array, dieses Problem zu lösen sind eher als ein Baum AVL. Wie kannst du das machen? Beginnen Sie zunächst mit einer binären Suche über das Array, um die kleinste Zahl s größer als p zu finden. Wenn diese Zahl größer als p + 1 ist, gib einfach p + 1 zurück. Ansonsten sind wir mitten in einer Reihe von Elementen und müssen die kleinste Zahl finden, die über den Lauf hinausgeht. Um dies zu tun, können Sie darüber nachdenken, das folgende Problem zu lösen: Finden Sie das kleinste Element x, so dass x - s größer ist als der Index von x minus dem Index von s. Dies kann durch eine binäre Suche in der verbleibenden Hälfte des Arrays erfolgen: Wenn die Differenz zwischen dem aktuellen Element und s gleich dem Abstand zwischen dem aktuellen Element und s ist, gehe nach rechts, andernfalls nach links. Sobald Sie dieses Element x gefunden haben, gehen Sie zu dem Element davor, fügen Sie eins hinzu, und das ist Ihre Antwort.
Um dieses Problem in der AVL-Struktur zu lösen, passen Sie den obigen Algorithmus im Wesentlichen so an, dass Baumsuchen statt Binärsuchen verwendet werden. Die Tatsache, dass Sie über Unterstrukturinformationen verfügen, bedeutet, dass Sie den Index eines beliebigen Elements in der Struktur mithilfe der Standardstatistikmethode ermitteln können. Ich stelle mir vor, dass der endgültige Algorithmus ein wenig chaotisch sein wird, aber er wird den obigen Algorithmus in der Zeit O (log n) originalgetreu simulieren.
Können wir jedem Knoten zusätzliche Informationen hinzufügen? – templatetypedef
@templatetypedef Dies ist was gegeben. Was hattest du vor? –
Ich würde mir vorstellen, dass dies einfacher wäre, wenn jeder Teilbaum auch seine Min- und Max-Werte speichern würde. – templatetypedef