Порядок вращения двоичного дерева поиска

Question

Предположим, у меня есть сбалансированное двоичное дерево поиска, представляющее эту упорядоченную последовательность.

A<B<C<D<E<F<G<H 

Учитывая один из элементов, например, F, как я эффективно преобразовать дерево так, что результат представляет эту упорядоченную последовательность?

F<G<H<A<B<C<D<E? 

Элементы из F вправо были перемещены перед всеми остальными элементами. Обратите внимание, что это не имеет никакого отношения к «вращению дерева» в обычном смысле. Вращение здесь происходит в смысле порядка элементов. Это то же самое, что и значение «вращения» для двусвязного списка. Например, если проблема была о двусвязного списки, а не бинарные деревья поиска, решение тривиально:

E.next := null 
F.prev := null 
H.next := A 
A.prev := H 

Есть ли эффективное решение для сбалансированного двоичного дерева поиска? примечание

Реализация:

На первый взгляд может показаться, что даже если существует эффективный алгоритм для этого не было бы много пользы, так как значения перемещаемых элементов должны быть обновлены сохранить инварианты двоичного дерева поиска (левый ребенок меньше, правый - больше). Однако это не так, как в модульной арифметике по модулю N, порядок можно фиксировать в постоянное время без изменения значений узлов. Предположим, что порядок узлов определяется как folows:

(A < B) if and only if ((A.value - C) mod N) < ((B.value - C) mod N) 

Здесь a.value, B.value и С представляют собой целые числа в диапазоне [0, N). Графическая интерпретация этого является то, что мы имеем круг с N точек распространяются вокруг, и мы заказываем точки таким образом, что С является наименее точкой, а затем С + 1, C + 2 и т.д., до C + (N-1), что является наибольшей точкой.

В любом случае, после перемещения F и все последующие элементы в передней, дерево инварианты могут быть тривиальным образом фиксируется путем изменения C:

C := F.value 

Answer 1

В общем случае это не может быть сделано менее чем Вовремя. Баланс может быть восстановлен в O (log N) после небольшого изменения, но резка всей ветки и вставка ее в другое место - большое изменение.

Извлечение n элементов и их вставка одна за другой принимают O (n log N). Если n велико, стоит перестроить все дерево, что можно сделать в O (N) времени.

Таким образом, вы можете рассматривать всю последовательность обхода порядка в виде кругового списка. Вы можете сохранить указатель на элемент, который вы считаете «первым», и просто изменить его, когда вы хотите переместить некоторые элементы с «конца» на «начало» и наоборот. Когда вы хотите посетить последовательность в порядке, просто начните с заостренного элемента («первый»), продолжите обход в порядке и оберните вокруг конца дерева.После посещения самого правого элемента продолжайте левое. Остановитесь, когда вы снова достигнете «первого» элемента.