Найти k-й наименьший элемент в O (log n)

Я знаю, что если сбалансировано, высота BST равна O (log (n)), что означает, что поиск O (log (n)), но делает несбалансированное дерево сбалансированным можно было бы увеличить время выполнения вставки/удаления, так как вам придется перебалансировать его после каждой вставки/удаления.Найти k-й наименьший элемент в O (log n)

Есть ли другой способ изменить BST, чтобы я мог найти наименьший элемент Kth в O (log (n)), не влияя на время выполнения других функций?

источник

2013-10-10 user2827214

Поскольку балансировка дерева амортизируется несколькими вызовами, это увеличивает время выполнения, но это не увеличивает вашу асимптотическую сложность. Сохранение сбалансированного дерева - относительно простая задача - посмотрите RB-деревья на хороший пример того, как это сделать. – dasblinkenlight

http://pine.cs.yale.edu/pinewiki/OrderStatisticsTree –

Зачем вам нужен запас для балансировки? После того, как сложность балансировки не увеличивается, вы можете использовать балансировку, а затем найти k-й наименьший элемент в O (logn) времени! –

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

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

Посмотрите на AVL trees, чтобы узнать, как он может балансировать, не влияя на сложность операций.

источник

2013-10-10 20:29:09

О, так вы говорите, так как вставка - это O (log (n)) и добавление функции балансировки (которая является O (log (n)) для сбалансированного дерева) внутри вставки делает всю функцию вставки равной O (2 * log (n)), который по-прежнему остается только O (log (n)) – user2827214

Сортировка. Основная идея заключается в том, что для чего-то вроде дерева AVL он будет в основном «ходить назад», когда дерево выполняет перебалансировки после вставки. Эти перебалансировки - это «O (log n)» total. Но да, это просто изменяет константу. –

Найти k-й наименьший элемент в O (log n)

ответ

Смежные вопросы