как увеличить все значения ключей, которые больше или равны K на D в красно-черном дереве в O (lgn)

Question

я изучаю алгоритмы atm, и у меня есть вопрос, как я могу увеличить все значения ключей, которые больше или равны K на D в красно-черном дереве в O (lgn)

Предположим, что красно-черное дерево имеет n узлов, называемых S

УВЕЛИЧЕНИЕ-С (S, K, D)

Answer 1

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

Таким образом, 13 является родителем, 17 тогда будет 17-13 = 4, 15 будет 15-17 = -1. Это означает, что когда вам нужно реальное значение, вам нужно сложить родительские узлы, поэтому, чтобы получить 15, вы берете 13 -> 4 -> -2 13 + 4-2 = 15.

Таким образом, вы можете изменить узлы, которые больше, чем x, в log n раз.

Если мы хотим изменить все больше 23 с +4, мы опустимся до 17, затем до 25, что> 23, и добавим 4 к его относительному значению, которое было 25-17 = 8, и увеличим его до 12, теперь все его дочерние элементы больше на 4, затем мы переходим к 22, которое меньше, поэтому мы вычитаем 4 из его относительного значения -3, которое затем получает -7, и когда мы достигаем кнопки, все готово. Итак, каково значение узла, который изначально был 27, его 13 + 4 + (8 + 4) + 2 = 31.

Но я бы не хотел писать код для восстановления баланса дерева при добавлении или удалении узла.

Answer 2

Бинарное дерево поиска обладает тем свойством, что для данного узла все узлы в левом поддереве будут меньше, чем узел, а все узлы в правом поддереве будут больше. Итак, давайте предположим, что корень имеет значение K. Затем необходимо увеличить каждый узел в правом поддереве, так как дерево сбалансировано (красно-черное дерево) и будет содержать около половины узлов. Таким образом, вам нужно выполнить n / 2 операции увеличения или O (n) операции

То, что вы просите, невозможно