Trova un algoritmo in RBTREE in O (log n)

Question

Ho bisogno di trovare una struttura di dati che è possibile fare con le seguenti azioni:

• Crea (S, k) - O (nlogn)
• Ricerca (S, k) - O (log n)
• Inserisci (S, k) - O (log n)
• Elimina (S, k) - O (log n)
• Diminuire-Upto (s, k, d) - O (log n) - questo metodo dovrebbe sottrarre d (d> 0) ogni nodo che è <= k

L'ovvia prima scelta era RedBlackTree.

Tuttavia, non posso venire a una soluzione per quanto riguarda Diminuzione-Fino a O (log). cosa succede se k è maggiore della chiave max nell'albero -. quel caso io devo aggiornamento dell'intero albero

Qualcuno può suggerire il contrario? forse qualche consiglio?

Answer 1

È possibile memorizzare un valore aggiunto in ogni nodo dell'albero, chiamiamolo delta. Si aggiunge delta di un nodo di chiavi memorizzate in tutta la sua discendente per ottenere le chiavi attuali. Quindi, per ottenere il valore reale di una chiave in un nodo particolare, si somma tutti i delta dalla radice a quel nodo e aggiungere questa somma alla chiave memorizzato.

Per fare Decrease-Upto, basta cambiare delta di O (log n) i nodi su un percorso dalla radice.

Non è necessario modificare la struttura dell'albero dopo questa operazione, perché è non cambia ordinamento delle chiavi.