Trouver un algorithme RBTREE en O (logn)

Question

Je dois trouver une structure de données que je peux faire avec les actions suivantes:

• Construction (S, k) - O (nlogn)
• Recherche (S, k) - O (log n)
• Insert (S, k) - O (log n)
• Supprimer (S, k) - O (log n)
• Diminution-Upto (s, k, d) - O (logn) - cette méthode doit soustraire d (d> 0) à chaque noeud qui est <= k

La première évidence est RedBlackTree choise.

Cependant, je ne peux pas venir à une solution concernant Diminution-O Upto (LOGN). ce qui se passe si k est supérieure à la clé max dans l'arbre -. ce cas, je dois mettre à jour l'arbre entier

Quelqu'un peut-il suggérer le contraire? peut-être quelques conseils?

Answer 1

Vous pouvez stocker une valeur supplémentaire dans chaque nœud de l'arbre, Appelons-le delta. Vous ajoutez delta d'un nœud à clés stockées dans tous ses descendants pour obtenir les clés réelles. Donc, pour obtenir la valeur réelle d'une clé dans un nœud particulier, vous somme de toutes les deltas de la racine à ce nœud et ajouter cette somme à la clé stockée.

Pour ce faire Decrease-Upto, vous venez de changer deltas de O (log n) noeuds sur un chemin de la racine.

Vous ne devez pas changer la structure de l'arbre après cette opération, car est ne change pas l'ordre des clés.