Algorithmus für den speziellen Fall von Rang Baum

Question

Ich versuche, einigen Rang Baum mit besonderen Anforderungen auf Basis von AVL-Baum zu erstellen, annehmen kann, dass ich mit Knoten AVL-Baum habe, hat jeder Knoten zwei Felder:

id, priority 

meine AVL-Baum von ID sortiert, auch habe ich eine Funktion:

foo(currentId, delta) 

, die die Priorität der alle IDs senkt, die durch delta diese Funktion mit Komplexität O (log arbeiten muss currentId weniger oder gleich n), so meine qu Estion ist welche zusätzliche Information muss ich speichern, um den Knoten mit highest priority in jeder Phase with complexity O(1) (nach der Verwendung von foo auch!) Pop.

P.S. Ich habe versucht, Informationen über maximale Priorität im rechten Teilbaum, maximale Priorität im linken Teilbaum zu speichern, aber es braucht viele Änderungen nach . Es wird mehr als nur O (log n) benötigen. Vielen Dank im Voraus für gute Ideen oder gute Bücher über Bäume.

Answer 1

Anstatt speichern die maximalen Priorität, die in jedem Unterbaum erscheint, für jeden Knoten c mit Mutter p, store in c die Differenz zwischen der maximalen Priorität im Teilbaum der c und die maximalen Priorität in Teilstruktur der p. Auf diese Weise können Sie einen Bereich von Prioritäten in der Zeit O (log n) aktualisieren und immer noch das Element mit der höchsten Priorität in der Zeit O (log n) finden.