Алгоритм для специального случая ранга дерева

Question

Я пытаюсь создать некоторый ранг дерева на основе AVL дерева с особыми требованиями, позволяет предположить, что у меня есть AVL дерево с узлами, каждый узел имеет 2 поля:

id, priority 

мое AVL дерево сортируется по идентификатору, а также у меня есть функция:

foo(currentId, delta) 

который понижает приоритет всех идентификаторов, которые меньше или равны currentId по delta эта функция должна работать со сложностью O (журнал n), , поэтому my qu estion - какая дополнительная информация мне нужна для хранения, чтобы иметь возможность поместить узел с highest priority на любом этапе with complexity O(1) (после использования foo тоже!).

P.S. Я попытался сохранить информацию о максимальном приоритете в правом поддереве, максимальный приоритет в левом поддереве, но после foo ему нужно много изменений. Это займет больше, чем просто O (log n). Заранее благодарим за хорошие идеи или хорошие книги о деревьях.

Answer 1

Вместо того, чтобы хранить приоритет максимум, который появляется в каждом поддереве, для каждого узел С с родительским р, магазином в гр в разности между максимальным приоритетом в поддереве deg; С и ​​максимальным приоритетом в поддереве р в. Таким образом, вы можете обновить ряд приоритетов в O (log n) времени и по-прежнему найти элемент максимального приоритета в O (log n) времени.