Медиана 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) в наихудшем случае.

См .: Дерево статистики заказов.

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

Answer 2

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

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

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

Answer 3

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

См. Полное объяснение .