✅ AVL Tree в структуре данных - Топ 3 операции, выполняемые на дереве AVL

Введение в дерево AVL в структуре данных

Введение в дерево AVL в структуре данных

Дерево AVL в структуре данных относится к дереву Adelson, Velski & Landis. Это расширенная версия дерева двоичного поиска. Он имеет все функции, что и в дереве двоичного поиска, но отличается только тем, что поддерживает разницу между высотой левого поддерева и правого поддерева, а также гарантирует, что его значение в дереве равно <= 1, это известно как баланс фактор.

Balance Factor = height(left-subtree) − height(right-subtree)

Например: рассмотрим следующие деревья

В вышеприведенном примере высота правого поддерева = 2 и левого = 3, поэтому BF = 2, то есть <= 1, поэтому дерево называется сбалансированным.

Зачем нам нужно дерево AVL в DS?

При работе с бинарным деревом поиска мы сталкиваемся со сценарием, в котором элементы расположены в отсортированном порядке. В таких случаях все элементы массива располагаются на одной стороне корня, это приводит к увеличению временной сложности поиска элемента в массиве, и сложность становится равной O (n), то есть сложность дерева в худшем случае., Чтобы разрешить такие проблемы и сократить время поиска, Adelson, Velski & Landis изобрели деревья AVL.

Пример:

На рисунке выше высота левого поддерева = 3 была равна

Высота правого поддерева = 0

Таким образом, коэффициент баланса = 3-0 = 3. Таким образом, поиск элемента в таком дереве имеет O (n) сложности, которая похожа на линейный поиск. Чтобы избежать этого сложного поиска, было введено дерево AVL, где каждый узел в дереве должен поддерживать

коэффициент уравновешивания <= 1, в противном случае для балансировки такого дерева должны использоваться различные методы вращения.

Struct AVLNode ( int data; struct AVLNode *left, *right; int ball factor; );

Типы вращений

Если коэффициент баланса для дерева не удовлетворяет условию <= 1, то для него необходимо выполнить ротацию, чтобы превратить его в сбалансированное дерево.

Есть 4 типа вращения:

1. Левое вращение: если добавление узла справа от дерева приводит к его дисбалансу, то в этом случае необходимо выполнить левое вращение.

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

3. Поворот влево-вправо: этот тип вращения представляет собой комбинацию из двух описанных выше вращений. Этот тип поворота происходит, когда один элемент добавляется к правому поддереву левого дерева.

В таком случае сначала выполните левое вращение на поддереве, а затем правое вращение левого дерева.

4. Вращение вправо-влево: этот тип вращения также состоит из последовательности более 2 вращений. Этот тип вращения необходим, когда элемент добавляется слева от правого поддерева, и дерево становится несбалансированным. В таком случае мы сначала выполняем вращение вправо на правом поддереве, а затем вращение влево на правом дереве.

Операции над деревом AVL в DS

Ниже 3 операции, которые могут быть выполнены над деревом AVL:

1. Поиск

Эта операция аналогична выполнению поиска в дереве двоичного поиска. Следующие шаги, как показано ниже:

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

Остальное иди к нужному ребенку и сравнивай еще раз.

Следуйте процессам B и C, пока не найдете элемент и не выйдите.

Этот процесс имеет O (log n) сложности.

Пример:

	Рассмотрим это дерево, где нам нужно выполнить поиск значения узла 9. Сначала - пусть x = 9, корневое значение (12)> x, затем значение должно быть в левом поддереве корневого элемента.
	Теперь х сравнивается со значением узла 3 x> 3, таким образом, мы должны перейти к правильному поддереву.
	Теперь x сравнивается с узлом (9), где 9 == 9 возвращает true. Таким образом, поиск элементов завершается в дереве.

2. Вставка

При вставке элемента в дерево AVL нам нужно найти конкретный элемент местоположения, который нужно вставить, а затем элемент присоединяется так же, как вставка в BST, но после этого проверяется, сбалансировано ли дерево или нет т. е. коэффициент баланса узла <= 1. И конкретные повороты выполняются по мере необходимости.

Сложность O (log n).
Пример: рассмотрим приведенное ниже дерево,

	Каждый узел имеет коэффициент баланса 0, -1 или 1, таким образом, дерево сбалансировано. Теперь давайте посмотрим, что происходит, когда вставляется узел со значением 1. Первое дерево пройдено, чтобы найти место, куда его нужно вставить… Таким образом, 1 <2 записывается как левый потомок узла (2).
	После вставки узел (9) выходит из равновесия с коэффициентом баланса = 2. Теперь он подвергается повороту вправо.
	Дерево становится сбалансированным после вращения вправо, и, таким образом, операция вставки завершается успешно.

3. Удаление

Удаление элемента в дереве AVL также включает в себя поиск элемента в дереве и затем его удаление. Операция поиска аналогична BST, и после нахождения удаляемого элемента элемент удаляется из дерева, и элементы корректируются, чтобы снова сделать его BST. После того, как эти элементы проверены, чтобы иметь коэффициент баланса 0, -1 или 1, и, таким образом, выполняются подходящие повороты, чтобы сделать его сбалансированным.

Сложность, если O (log n).

	Рассмотрим данное дерево, у которого все имеют коэффициент баланса 0, -1 или 1. Теперь давайте удалим узел со значением 16. Первое дерево обходит, чтобы найти узел со значением 16, аналогичным алгоритму поиска.
	Узел 16 будет заменен предшествующим предшественником этого узла, который является самым большим элементом из левого поддерева, т.е. 12 Дерево стало неуравновешенным, поэтому необходимо выполнить LL - вращение.
	Теперь каждый узел стал сбалансированным.

Вывод - дерево AVL в структуре данных

Дерево AVL является потомком дерева двоичного поиска, но преодолевает его недостаток, заключающийся в увеличении сложности в случае сортировки элементов. Он контролирует коэффициент баланса дерева, чтобы быть 0 или 1 или -1. В случае, если дерево становится неуравновешенным, выполняются соответствующие методы вращения, чтобы сбалансировать дерево.

AVL Tree в структуре данных - Топ 3 операции, выполняемые на дереве AVL