Encontre um algoritmo no RBTree em O (logn)

Question

Preciso encontrar uma estrutura de dados que possa fazer com as seguintes ações:

• Build (S, K) - O (nLogn)
• Pesquisa (S, K) - O (logn)
• Inserir (s, k) - o (logn)
• Delete (S, K) - O (logn)
• Diminuição -upto (s, k, d) - o (logn) - Este método deve subtrair d (d> 0) todo nó que é <= k

A primeira escolha óbvia foi Redblacktree.

No entanto, não posso chegar a uma solução em relação à diminuição-upto em O (logn). O que acontece se K for maior, então a chave máxima na árvore - nesse caso, tenho que atualizar toda a árvore.

Alguém pode sugerir o contrário? Talvez algumas dicas?

Answer 1

Você pode armazenar um valor extra em cada nó da árvore, vamos chamá -lo de delta. Você adiciona delta de um nó às teclas armazenadas em todo o seu descendente para obter as chaves reais. Portanto, para obter o valor real de uma chave em um nó específico, você resume todos os deltas da raiz ao nó e adicione essa soma à tecla armazenada.

Façam Decrease-Upto, basta alterar os deltas dos nós (log n) em um caminho da raiz.

Você não precisa alterar a estrutura da árvore após esta operação, porque não muda a ordem das chaves.