Encontrar un algoritmo en RBTREE en O (log n)

Question

Tengo que encontrar una estructura de datos que puedo hacer con las siguientes acciones:

• Build (S, k) - O (nlogn)
• Buscar (S, k) - O (log n)
• Insertar (S, k) - O (log n)
• Eliminar (S, k) - O (log n)
• Disminuir-Upto (s, k, d) - O (log n) - este método debe restar d (d> 0) cada nodo que es <= k

La primera elección obvia era RedBlackTree.

Sin embargo, no puede llegar a una solución con respecto a Disminución-Upto en O (Logn). ¿qué ocurre si k es mayor que la tecla máximo en el árbol -. ese caso tengo que actualización de todo el árbol

Puede alguien sugerir lo contrario? tal vez algunos consejos?

Answer 1

Puede almacenar un valor extra en cada nodo del árbol, llamémosle delta. Agrega delta de un nodo a claves almacenadas en toda su descendiente para obtener las claves reales. Por lo tanto, para obtener el valor real de una llave en un nodo particular, se resumen todos los deltas de la raíz a ese nodo y añadir esta suma a la clave almacenada.

Para hacer Decrease-Upto, que acaba de cambiar los deltas de O (log n) nodos en una ruta desde la raíz.

Usted no tiene que cambiar la estructura del árbol después de esta operación, porque es no cambiar orden de las teclas.