Лучший способ выбрать наименьшее число последовательности чисел с разделителями - PullRequest
Новая
       16

Лучший способ выбрать наименьшее число последовательности чисел с разделителями

0 голосов
/ 27 сентября 2010

Если мне дают определенный набор чисел (которые для простоты я храню в сбалансированном бинарном дереве поиска), то я хочу ответить на запрос, который требует от меня сообщить, какое это наименьшее число между [A, B]Какой бы быстрый алгоритм для выполнения этой задачи?

Технически я мог бы пройти по дереву от корня в поисках A (или числа, которое больше, чем если A не присутствует), чем при возврате в поисках B (или число меньше, чем B), и при этом я мог сохранить счетчик для i, чтобы определить, когда я буду на i-м номере.Но это не кажется мне оптимальным.

Можно ли выполнить эту операцию для O (log n), высоты дерева, которое я использую для хранения универсального набора чисел?

Спасибо

1 Ответ

5 голосов
/ 27 сентября 2010

Вы, конечно, можете это сделать, если можете хранить некоторую информацию в узлах.Чтобы сделать обход O(logn), нам нужно, чтобы каждый узел знал, сколько узлов имеет его правое поддерево.(Вы можете сохранить эту информацию и по-прежнему добавлять / удалять из дерева за O (log (n)) время) 

def search(currentNode, k)
    if k == 0 then
        return currentNode
    else if currentNode.rightBranchSize >= k then
        // we remove 1 from k because currentNode isn't considered anymore
        return search(currentNode.right, k - 1)
    else
        // we decrease k because currentNode and its whole right subtree aren't considered anymore
        return search(currentNode.parent, k - currentNode.rightBranchSize - 1)
    end
end

Код должен быть понятен.
Мы начинаем с currentNode являющийся первым узлом с номером >= A и ищущий k-й элемент (k основан на 0).

  1. Как schnaader в своем комментарии, это будетпроще просто пройти по дереву, если k мало.
  2. Большинство распространенных библиотек (например, STL) не позволят вам проходить по дереву таким образом (они не предоставляют никакой структуры Node).с указателями на левое и правое поддеревья).Таким образом, хотя алгоритм и прост, его реализация может быть сложной.
  3. Для рассмотрения B из вашего вопроса требуется всего лишь небольшая модификация.
...