В чем недостаток использования дерева AVL?

Question

Мне кажется, что дерево AVL всегда более эффективно, чем BST. Итак, почему люди все еще используют BST? Есть ли затраты, связанные с реализацией AVL?

Answer 1

AVL Деревья имеют свои преимущества и недостатки по сравнению с другими деревьями, например, красно-черными деревьями или 2-3 деревьями или просто равными BST.

AVL деревья:

Преимущество:

1. Simple. Довольно легко кодировать и понимать
2. Дополнительное хранилище: довольно минимальное, 2 бит на узел (для хранения + 1,0, -1). Существует также трюк, где вы можете использовать 1 бит на узел, используя один бит вашего ребенка .
3. Постоянная для поиска (смотрите в своем любимом аналитической книге: Кнут и т. Д.) Составляет 1,5 (так что 1,5 журнала). Красно-черные деревья имеют постоянную 2 (так 2 * log (n) для поиска).

Недостатки:

1. Пропуски дороги иш. Логарифм по-прежнему остается для удаления узла, но вам, возможно, придется «повернуть» до корня дерева. Другими словами, большая константа. Красно-черным деревьям нужно делать только 1 поворот.
2. Непросто код. Они, вероятно, являются «упрощенными» семейства деревьев, но все еще есть много или угловые случаи.

Если вы ожидаете, что ваши данные будут отсортированы, BST перейдет в связанный список. НО, если вы ожидаете, что ваши данные будут достаточно случайными, «в среднем», все ваши операции для BST (поиск, удаление, вставка) будут касаться логарифмического. ОЧЕНЬ легко закодировать BSTs: деревья AVL, хотя довольно простые для кодирования, имеют много угловых случаев, и тестирование может быть сложным.

Таким образом, простые двоичные поисковые деревья легко кодировать и получать правильные значения, а если ваши данные довольно случайны, они должны работать очень хорошо (в среднем все операции будут логарифмическими). AVL Tree сложнее кодировать, но гарантируют логарифмическую производительность по цене дополнительного пространства и более сложного кода.