Как найти ближайший предшественник с временной сложностью O (log n)

Question

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

Как я это сделал с O (n), я делю дерево на 2 на основе ключа (запись) и выполняю максимальный поиск для левого дерева и поиска минимального дерева. Я знаю, что это не log n, поскольку после того, как я сузил решение, мне все равно придется обрабатывать все узлы в левом или правом дереве, так что в лучшем случае это еще 1/2n.

Я могу видеть образец решений, но все равно не могу обдумать его. Я думаю об использовании указателя root и node, но я все еще не уверен, как его реализовать.

Любые указатели будут оценены, я googled и попытался решить эту проблему безрезультатно в течение нескольких дней.

Answer 1

Учитывая узел N в дереве AVL, есть три случая:

1. N имеет левый ребенок L. Тогда непосредственный предшественник N должен быть самым правым глубочайшим потомком L., найдите его, вам нужно спуститься в поддерево L, взяв правильную ветвь на каждом под-узле. Может быть не более log n уровней, поэтому это O (log n).

2. N не имеет левого ребенка, но сам является правильным потомком родителя P. Тогда P должен быть непосредственным предшественником, находящимся в O (1) раз.

3. N не имеет левого дочернего элемента и является левым дочерним элементом родителя P. Затем поднимите дерево по направлению к корню до тех пор, пока не найдете узел, который является правильным потомком A-восходящего A. Если такого A нет, N не имеет предшественника; в противном случае A является непосредственным предшественником N. Опять же, для проверки может быть не более log n родительских уровней, поэтому это также O (log n).

Определение того, какое из трех применений, очевидно, может быть выполнено в течение O (1), поэтому общая временная сложность O (log n).

(На самом деле, случай 2 представляет собой частный случай случае 3;. Я написал его в трех случаях, чтобы надеяться, сделать его легче следовать)

Пример АВЛ дерева для справки (это то же самое, как пример приведены на Wikipedia page for AVL tree, но я воссозданы график вместо копирования изображения; источник может быть раздвоенный от here если кто-нибудь хотел бы сделать модификации):

Узлы 17 и 50 являются примерами Дело 1; узлы 23 и 76 являются примерами случая 2; узел 9 является примером случая 3 без предшественника; узел 19 является примером случая 3 с предшественниками. Если вы рассмотрите каждый пример, рассматривающий примеры из дерева выше, вы сможете подтвердить, что утверждения верны. Это может быть проще, чем пройти формальное доказательство (которое, тем не менее, может быть дано).

Answer 2

Я на самом деле выяснил более простой способ решить эту проблему без использования родительского или дочернего указателя.

Вот что я сделал: Сохраните каждый узел, когда я пересекаю дерево рекурсивно и сохраняю все узлы с записью меньше цели.

Если это лист, верните указатель темпа к вызывающему.