Как найти непосредственного предшественника с O (log n) сложностью по времени
Во-первых, я хотел бы, чтобы кто-нибудь знал, что это назначение, и я закончил поиск непосредственного предшественника с помощью O (n), но я хотел бы сделать это с помощью O (log n), я знаю, что это возможно с дерево является деревом AVL.
То, как я сделал это с помощью O (n), я делю дерево на 2 на основе ключа (записи) и выполняю максимальный поиск для левого дерева и минимальный поиск для правого дерева. Я знаю, что это не лог n, так как после того, как я сузил решение, мне все еще нужно обработать все узлы в левом или правом дереве, так что в лучшем случае это все равно 1 / 2n.
Я могу видеть схему решений, но все еще не могу обернуться вокруг этого. я думаю об использовании указателя корня и узла, но я все еще не уверен, как это реализовать.
Любые указатели будут оценены, я гуглил и пытался решить эту проблему безрезультатно в течение нескольких дней.
Решение
Для данного узла N в дереве AVL существует три случая:
-
У N есть левый потомок L. Тогда непосредственный предшественник N должен быть самым правым самым глубоким потомком L. Чтобы найти его, вам нужно спуститься в поддерево L, взяв правую ветвь в каждом подузле. Может быть не более log n уровней, так что это O (log n).
-
N не имеет левого потомка, но сам является правым потомком родительского P. Тогда P должен быть непосредственным предшественником, расположенным за O (1) времени.
-
N не имеет левого потомка и является левым дочерним элементом родительского P. Затем идите вверх по дереву к корню, пока не найдете узел, являющийся правым дочерним элементом восходящего элемента A. Если такого A нет, N не имеет никакого предшественник; в противном случае A является непосредственным предшественником N. Опять же, может быть проверено не более log n родительских уровней, так что это также O (log n).
Определить, какое из трех применений очевидно, может быть сделано за O (1) время, поэтому общая сложность времени составляет O (log n).
(На самом деле, случай 2 — это особый случай случая 3; я написал его в трех случаях, чтобы, надеюсь, было легче следовать.)
Пример дерева AVL для справки (это тот же пример, который приведен на Страница Википедии для дерева AVL, но я воссоздал график, а не скопировал изображение; источник может быть разветвлен Вот если кто-то хотел бы внести изменения):
Узлы 17 и 50 являются примерами случая 1; узлы 23 и 76 являются примерами случая 2; узел 9 является примером случая 3 без предшественника; узел 19 является примером случая 3 с предшественниками. Если вы продумаете каждый из случаев, рассматривая примеры из дерева выше, вы сможете подтвердить, что утверждения верны. Это может быть проще, чем проходить формальное доказательство (которое, тем не менее, можно дать).
Другие решения
На самом деле я нашел более простой способ решить эту проблему без использования родительского или дочернего указателя.
Вот что я сделал:
Сохраняйте каждый узел, когда я рекурсивно пересекаю дерево, и сохраняйте все узлы, у которых запись меньше целевой.
если это лист, то верните временный указатель на вызывающего.