Самобалансирующиеся деревья полезны в одном аспекте. Допустим, бинарное дерево поиска искажено, тогда вставка, удаление и поиск занимают O(n) времени.
Теперь, используя дерево AVL, временная сложность может быть уменьшена до O (log n).
Дерево AVL поддерживает максимальную высоту между левым поддеревом и правым поддеревом корня.
Для вставки выполняются два шага -
- Вставьте следующие условия бинарного дерева поиска.
- Примените вращение, чтобы удовлетворить условия AVL.
Есть четыре случая, чтобы удовлетворить условиям AVL:
- Левый левый корпус — выполнить правое вращение.
- Левый правый случай — выполнить левое вращение, а затем правое вращение.
- Правый правый случай — выполнить левое вращение.
- Правый левый случай — выполнить правое вращение, а затем левое вращение.
Для вставки максимум два вращения на каждом уровне, поэтому максимально возможная операция в худшем случае составляет 2 log n, поэтому временная сложность для вставки всегда будет O (log n).
Точно так же временная сложность будет O (log n) для поиска и удаления.
