Algorithme pour le cas particulier de l'arbre de rang

Question

Je suis en train de créer un arbre de rang en fonction de l'arbre AVL avec des exigences particulières, permet de supposer que je arbre AVL avec des noeuds, chaque noeud a 2 champs:

id, priority

mon arbre AVL est trié par id, aussi j'ai une fonction:

foo(currentId, delta)

ce qui réduit la priorité des tous ids qui est inférieur ou égal à currentId par delta cette fonction doit travailler avec la complexité O (log n), donc ma question est que des informations supplémentaires dois-je magasin pour être en mesure de pop le nœud avec le highest priority à tout with complexity O(1) étape (après avoir utilisé foo aussi!).

P.S. J'ai essayé de stocker les informations sur la priorité maximum dans le sous-arbre droit, priorité maximum dans le sous-arbre gauche, mais il faut beaucoup de changements après foo. Il faudra plus que O (log n). Merci à l'avance pour toutes les bonnes idées ou de bons livres sur les arbres.

Answer 1

Au lieu de stocker le maximale priorité qui apparaît dans chaque sous-arbre, pour chaque nœud c avec un parent p, magasin en c la différence entre la priorité maximale dans le sous-arbre de c et la priorité maximale dans le sous-arbre p. De cette façon, vous pouvez mettre à jour une série de priorités dans O (log n), et toujours trouver l'élément de priorité maximale dans O (log n).