Согласно wikipedia, порядок статистики дерево поддерживает эти две операции в журнале (п):
- Выберите (я) - найти i-й наименьший элемент, сохраненный в дереве в O (журнал (п))
- Ранг (x) - найти ранг элемента x в дереве, т. е. его индекс в отсортированном списке элементов дерева в O (log (n))
Начните с получения ранга x и выберите высшие чины x, пока не увидите найдите место для вставки отсутствующего элемента. Но это имеет наихудший n * log (n).
Итак, если у вас есть ранг x, вы делаете своего рода бинарный поиск. Основная идея заключается в том, существует ли пространство между числом x и y, которые находятся в дереве. Если есть rank(x) - rank(y) != x - y
.
Общий случай: при поиске номера в интервале [lo, hi] (lo и hi - ранги в дереве, середина - средний ранг), если между словом lo и mid существует пробел, то поиск внутри [lo, mid], ищите внутри [mid, hi]. Вы в конечном итоге найдете номер, который ищете.
Однако это решение не выполняется в log (n) времени, но в log^2 (n). Это лучшее, что я могу придумать для общего решения.
EDIT:
Ну, это сложный вопрос, я изменил свое мнение несколько раз. Вот что я придумал:
Я предполагаю, что левый узел имеет худшее значение, а правый узел имеет высшую ценность
Интуиции find(x)
: Начало в корне и идти вниз по дереву почти как в стандартное двоичное дерево. Если ветка, в которую мы хотим пойти, не содержит решение find(x)
, тогда разрежьте его.
Мы пройдем основные случаи первых:
- Если узел я нашел пустой, то я сделал, и я возвращать значение, что я искал.
- Если текущее значение меньше того, которое я ищу, я ищу x в правом поддереве
- Если я нашел узел, содержащий x, то я ищу x + 1 в правом поддереве.
Случай, когда x находится в левом поддереве, более сложный, поскольку он может содержать x, x + 1, x + 2, x + 3 и т. Д. До y-1, где y - значение, хранящееся в текущий узел. В этом случае мы хотим найти y + 1 в правом поддереве.
Однако, если все числа от x до y не находятся в левом поддереве (то есть есть пробел), то мы найдем в нем значение, поэтому мы рассмотрим левое поддерево для x.
Вопрос: Как найти, существует ли последовательность из x в y в поддереве?
Алгоритм в питона выглядит следующим образом:
def find(node, x):
if node == null:
return x
if node.data < x:
return find(node.right, x)
if node.data == x:
return find(node.right, x+1)
if is_full(...):
return find(node.right, node.data+1)
return find(node.left, x)
Чтобы получить наименьшее значение строго больше, чем х, которое не в дереве, то первый вызов find(root, x+1)
. Если вы хотите, чтобы наименьшее значение было больше или равно x, которое не находится в дереве, первый вызов равен find(root, x)
. Метод is_full
проверяет, содержит ли левое поддерево все число от x до node.data-1.
Теперь, используя это как отправную точку, я считаю, что вы можете найти подходящее решение самостоятельно, используя тот факт, что количество узлов, содержащихся в каждом поддереве, хранится в корне поддерева.
Найдите x, как обычно. Затем выполните поиск по первому стилю глубины из x, так что каждое целое число является приращением предыдущего. Если это не так, вы нашли свое целое число. – Striker
@Striker Но для '1,2,3,4,5,6,7,9' с' find (1) 'это будет' O (n) ', не так ли? – dan785317
В худшем случае да, это будет O (n). – Striker