2016-05-16 29 views
2

Если у меня есть порядок статистика бинарного сбалансированное дерево, которое имеет n различных целые чисел, как его ключи, и я хочу, чтобы написать функцию find(x), которая возвращает минимальное целое число, которое не в дереве, и больше x. в O(log(n)) время.недостающего числа в двоичном дереве поиска

Например, если ключи в дереве 6,7,8,10,11,13,14 затем find(6)=9, find(8)=9, find(10)=12, find(13)=15.

Я думаю о поиске max в O(log(n)) и индекс x (знак i_x) в O(log(n)) тогда, если i_x=n-(m-x) то я могу просто вернуться max+1.

По индексу Я имею в виду, что 6,7,8,10,11,13,14 индекс 6 = 0 и индекс 10 является 3, например ...

Но у меня возникают проблемы с другими случаями ...

+0

Найдите x, как обычно. Затем выполните поиск по первому стилю глубины из x, так что каждое целое число является приращением предыдущего. Если это не так, вы нашли свое целое число. – Striker

+0

@Striker Но для '1,2,3,4,5,6,7,9' с' find (1) 'это будет' O (n) ', не так ли? – dan785317

+0

В худшем случае да, это будет O (n). – Striker

ответ

2

Согласно 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.

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

+0

Я думаю, что мы должны использовать тот факт, что «узлам дерева нужно сохранить одно дополнительное значение, которое представляет собой размер поддерева, внедренного в этот узел», и используя это, создайте функцию 'find (x)' .. – dan785317

+0

Хорошо, я забыл об этом. Тогда интуиция проста. Следуйте по пути, как в классическом BST. Если вы хотите следовать левой ссылке, проверьте, нет ли отсутствующего int, проверяя значения дочерних элементов и количество узлов, которые они содержат. Если есть пробел, то обычно следуйте левой ссылке. Если нет, идите направо. –

+0

следует из корня? или от 'x'? если из 'x', поэтому мне может даже понадобиться« вверх »по краям ... – dan785317

1

Я столкнулся с аналогичным вопросом.

Не было ограничений по поиску более чем x, просто найдите недостающий элемент в BST.

Ниже мой ответ, это вполне возможно сделать в O(lg(n)) времени, при условии, что дерево почти сбалансировано. Возможно, вам стоит рассмотреть доказательство того, что ожидаемая высота случайно построенного BST равна lg(n) с учетом n элементов. Я использую более простую нотацию: O(h) где h = высота дерева, поэтому две вещи теперь раздельны.

допущения и/или требования:

  1. Я улучшить структуру данных. сохраните счет (left_subtree + right_subtree + 1) на каждом узле.
  2. Очевидно, что отсчет одного узла 1
  3. Этот счетчик предварительно вычисляются и сохраняются в каждом узле

enter image description here

Пожалуйста, простите мое множественные обозначения для не равно (=/= и !=)

Также обратите внимание, что код может быть структурирован немного лучше, если нужно написать рабочий код на машине.

Более того, я думаю, на данный момент, что это правильно. Я пробовал столько угловых дел, сколько мог, и вообще это работает. Даже если есть встречный пример, я не думаю, что будет сложно изменить код в соответствии с конкретным случаем; но, пожалуйста, прокомментируйте встречный пример, я заинтересован.

Смежные вопросы