Найти алгоритм в RBTREE в O (logn) - PullRequest
Новая
       41

Найти алгоритм в RBTREE в O (logn)

4 голосов
/ 10 февраля 2010

Мне нужно найти структуру данных, которую я могу сделать с помощью следующих действий:

  • Build (S, k) - O (nlogn)
  • Поиск (S, k) - O (logn)
  • Вставка (S, k) - O (logn)
  • Удалить (S, k) - O (logn)
  • Decrease-Upto (s, k, d) - O (logn) - этот метод должен вычитать d (d> 0) каждого узла, который <= k </li>

Очевидным первым выбором был RedBlackTree.

Однако я не могу прийти к решению, касающемуся уменьшения до O (Logn). что произойдет, если k больше максимального ключа в дереве - тогда я должен обновить все дерево.

Может кто-то предложить иначе? может быть, несколько советов?

1 Ответ

4 голосов
/ 10 февраля 2010

Вы можете хранить дополнительные значения в каждом узле дерева, назовем его дельта. Вы добавляете дельту узла к ключам, хранящимся во всех его потомках, чтобы получить фактические ключи. Таким образом, чтобы получить фактическое значение ключа в конкретном узле, вы суммируете все дельты от корня к этому узлу и добавляете эту сумму к сохраненному ключу.

Чтобы сделать Decrease-Upto, вы просто меняете дельты O (log n) узлов на одном пути от корня.

Вам не нужно менять структуру дерева после этой операции, потому что это не меняет порядок ключей.

...