Двоичное дерево поиска также называют упорядоченным или отсортированным двоичным деревом, потому что упорядоченный обход двоичного дерева поиска всегда осуществляется в отсортированном порядке.
Бинарное дерево поиска — это бинарное дерево только с двумя ветвями, в котором каждый узел левого поддерева меньше или равен, а каждый узел правого поддерева больше. Двоичное дерево поиска — это структура данных двоичного дерева на основе узлов. Мы можем выполнять предварительный, упорядоченный и обратный обход с помощью дерева двоичного поиска.
AVL Tree
AVL-дерево — это самобалансирующееся двоичное дерево поиска, в котором разница между высотами левого и правого поддеревьев не может быть больше 1 для всех узлов. Эта разница называется коэффициентом баланса, т.е. 0, 1 и −1.
Чтобы выполнить эту балансировку, мы выполняем следующие повороты несбалансированного/несбалансированного двоичного дерева поиска, чтобы сделать его деревом AVL.
- Левое вращение
- Правое вращение
- Вращение влево вправо
- Правое левое вращение
Ниже приведены различия между двоичным деревом поиска и деревом AVL.
| С. Нет | Бинарное дерево поиска | АВЛ-дерево |
| 1. | В двоичном дереве поиска, в дереве AVL каждый узел не соответствует коэффициенту баланса. | В дереве AVL каждый узел соответствует коэффициенту баланса, т. е. 0, 1, -1. |
| 2. | Каждое дерево двоичного поиска не является деревом AVL. | Каждое дерево AVL представляет собой двоичное дерево поиска. |
| 3. | Простота реализации. | Комплекс для реализации. |
| 4. | Высота или глубина дерева равна O(n). | Высота или глубина дерева O(logn) |
| 5. | Поиск неэффективен при наличии большого количества узлов в дереве двоичного поиска. | Поиск эффективен, потому что поиск нужного узла происходит быстрее из-за балансировки высоты. |
| 6. | Структура дерева бинарного поиска состоит из 3 полей: левого поддерева, данных и правого поддерева. | Древовидная структура AVL состоит из 4 полей: левого поддерева, данных, правого поддерева и коэффициента балансировки. |
| 7. | Это не сбалансированное дерево. | Это сбалансированное дерево. |
| 8. | В дереве бинарного поиска. Вставка и удаление просты, потому что не требуется поворотов. | В дереве AVL вставка и удаление сложны, поскольку для балансировки дерева требуется несколько поворотов. |
