Разница между двоичным деревом поиска и деревом AVL

Тенденции разработки программного обеспечения в 2022 году Изучение

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

Бинарное дерево поиска — это бинарное дерево только с двумя ветвями, в котором каждый узел левого поддерева меньше или равен, а каждый узел правого поддерева больше. Двоичное дерево поиска — это структура данных двоичного дерева на основе узлов. Мы можем выполнять предварительный, упорядоченный и обратный обход с помощью дерева двоичного поиска.

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 вставка и удаление сложны, поскольку для балансировки дерева требуется несколько поворотов.
Читайте также:  Декларативное и императивное программирование: 5 ключевых отличий

 

Оцените статью
bestprogrammer.ru
Добавить комментарий

Adblock
detector