Медиана BST в O (logn) временная сложность

Question

Я наткнулся на решение, указанное в http://discuss.joelonsoftware.com/default.asp?interview.11.780597.8, используя обход Morris InOrder, с помощью которого мы можем найти медиану в O(n) времени.

Но можно ли достичь того же, используя O(logn) раз? То же самое было задано здесь: http://www.careercup.com/question?id=192816

Answer 1

Если вы также поддерживаете подсчет количества левых и правых потомков узла, вы можете сделать это в O (logN), выполнив поиск медианной позиции. Фактически, вы можете найти k-й наибольший элемент в O (logn) времени.

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

Если дерево не сбалансировано, то у вас есть сложность худшего случая Omega (n).

См. Order Statistic Tree.

btw, BigO и Smallo очень разные (ваше название говорит Smallo).

Answer 2

Если вы не гарантируете какое-то сбалансированное дерево, это невозможно.

Рассмотрите дерево, которое является полностью вырожденным - например, каждый указатель left имеет значение NULL (ноль, что бы то ни было), поэтому каждый узел имеет только правильный дочерний элемент (то есть для всех практических целей «дерево» представляет собой действительно связанный список).

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

Answer 3

Мы можем найти медиану, используя указатель rabbit и указатель turtle. Кролик движется в два раза быстрее, чем черепаха, в обход ОНТ в порядке. Таким образом, когда кролик достигает конца обхода, черепаха находится в медианной BST.

См. full explanation.