Максимальное целое число с одинаковыми строками, в красном черном дереве

Question

У меня есть дерево с набором чисел, где каждое число имеет две строки: a и b. Таким образом, структура выглядит следующим образом:

-число-б

для каждого узла.

Я хочу получить максимальное число в дереве, где a = b в O (log n) наихудшее время выполнения.

Мой подход: Пробовал красное черное дерево. Это имеет O (log n), если число находится в правом поддереве. Но O (n), если число находится в левом поддереве.

Невозможно использовать обычный BST, так как для худшего случая он имеет O (n) как время выполнения.

Answer 1

Одним из решений является поддержание двух деревьев; где a == b и где a! = b. Для большинства функций вам, вероятно, потребуется вызвать на оба дерева, но это закончится тем же самым большим значением сложности, что и 2 * O (log n) -> O (log n).

Answer 2

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

Для данного дерева максимальное требуемое значение можно считывать с корня.

Во время ввода/удаления/вращения это свойство можно поддерживать в O (log n) времени.

Существует глава под названием Структуры увеличивающий данных в Введение в алгоритмы по Cormen и др (обычно называют CLR книги). на этом.

Предлагаю вам прочитать его. Соответствующая теорема является теорема 14.1, которая гласит

Пусть f быть поле, которое усиливает красно-черное дерево T из n узлов и предположить, что содержимое f для узла x может быть вычислена с использованием только информации узлы x, left(x) и right(x), включая f(left(x)) и f(right(x)). Затем мы можем поддерживать значения f во всех узлах T при вставке и удалении без асимптотически влияющих на производительность этих операций O(log n).

левый (х) является левым потомком х и т.д.

Для вас случая, определить g(node) быть node.number если node.a == node.b и -infinity иначе.

Определить f(x) будет max f(left(x)), f(right(x)), g(x).