Деревья AVL: ротация, вставка, удаление с помощью C++ Пример

Что такое деревья AVL?

AVL деревья — это двоичные деревья поиска, в которых разница между высотой левого и правого поддерева равна -1, 0 или +1.

Деревья AVL также называют самобалансирующимся двоичным деревом поиска. Эти деревья помогают поддерживать логарифмическое время поиска. Он назван в честь своих изобретателей (АВЛ) Адельсона, Вельски и Лэндиса.

Как работает дерево AVL?

Чтобы лучше понять необходимость AVL-деревьев, давайте рассмотрим некоторые недостатки простых двоичных деревьев поиска.

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

АВЛ Работа с деревом — Визуализация дерева AVL

Высота дерева растет линейно, когда мы вставляем ключи в порядке возрастания их значений. Таким образом, операция поиска в худшем случае занимает O(n).

Для поиска элемента требуется линейное время; следовательно, нет смысла использовать Двоичное дерево поиска состав. С другой стороны, если высота дерева сбалансирована, время поиска увеличивается.

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

Здесь ключи те же, но поскольку они вставляются в другом порядке, они занимают разные позиции, и высота дерева остается сбалансированной. Следовательно, поиск не займет более O(log n) для любого элемента дерева. Теперь очевидно, что если вставка выполнена правильно, высоту дерева можно сохранить сбалансированной.

В деревьях AVL мы проверяем высоту дерева во время операции вставки. Изменения внесены для поддержания сбалансированной высоты без нарушения фундаментальных свойств двоичного дерева поиска.

Коэффициент баланса в деревьях AVL

Коэффициент баланса (BF) — это фундаментальный атрибут каждого узла в деревьях AVL, который помогает отслеживать высоту дерева.

Свойства фактора баланса

Коэффициент баланса в деревьях AVL — Коэффициент баланса AVL-дерева

Коэффициент баланса известен как разница между высотой левого и правого поддерева.
Коэффициент баланса (узел) = высота (узел->слева) – высота (узел->справа)
Допустимые значения BF: –1, 0 и +1.
Значение –1 указывает, что правое поддерево содержит одно лишнее, т. е. дерево тяжелое справа.
Значение +1 указывает, что левое поддерево содержит одно лишнее, т. е. дерево тяжелое слева.
Значение 0 показывает, что дерево содержит равные узлы с каждой стороны, т. е. дерево идеально сбалансировано.

Ротации АВЛ

Чтобы сбалансировать само AVL Tree, при вставке или удалении узла из дерева выполняются ротации.

Мы выполняем следующее вращение LL, вращение RR, вращение LR и вращение RL.

Влево – вращение влево
Вправо – правое вращение
Право-левое вращение
Вращение влево-вправо

Влево – вращение влево

Этот поворот выполняется, когда новый узел вставляется в левый дочерний элемент левого поддерева.

Выполняется одиночный поворот вправо. Этот тип вращения определяется, когда узел имеет коэффициент балансировки +2, а его левый дочерний элемент имеет коэффициент балансировки +1.

Вправо – правое вращение

Этот поворот выполняется, когда новый узел вставляется в правый дочерний элемент правого поддерева.

Выполняется одиночный поворот влево. Этот тип вращения определяется, когда узел имеет коэффициент балансировки -2, а его правый дочерний узел имеет коэффициент балансировки -1.

Право-левое вращение

Этот поворот выполняется, когда новый узел вставляется в правый дочерний элемент левого поддерева.

Это вращение выполняется, когда коэффициент балансировки узла равен –2, а его правый дочерний узел имеет коэффициент балансировки +1.

Вращение влево-вправо

Этот поворот выполняется, когда новый узел вставляется в левый дочерний элемент правого поддерева.

Это вращение выполняется, когда узел имеет коэффициент балансировки +2, а его левый дочерний узел имеет коэффициент балансировки -1.

Вставка в деревья AVL

Операция вставки почти такая же, как в простых бинарных деревьях поиска. После каждой вставки мы балансируем высоту дерева. Операция вставки занимает O(log n) худшей временной сложности.

Шаг 1: вставьте узел в дерево AVL, используя тот же алгоритм вставки, что и BST. В приведенном выше примере вставьте 160.

Шаг 2: после добавления узла коэффициент баланса каждого узла обновляется. После вставки 160 коэффициент баланса каждого узла обновляется.

Шаг 3: Теперь проверьте, не нарушает ли какой-либо узел диапазон коэффициента балансировки. Если коэффициент балансировки нарушен, затем выполните вращения, используя приведенный ниже случай. В приведенном выше примере нарушается фактор балансировки 350 и здесь становится применим случай 1, мы выполняем LL-вращение и дерево снова балансируется.

Если BF(узел) = +2 и BF(узел -> левый дочерний элемент) = +1, выполните вращение LL.
Если BF(узел) = -2 и BF(узел -> правый дочерний элемент) = 1, выполните вращение RR.
Если BF(узел) = -2 и BF(узел -> правый дочерний элемент) = +1, выполните вращение RL.
Если BF(узел) = +2 и BF(узел -> левый дочерний элемент) = -1, выполните вращение LR.

Удаление в деревьях AVL

Удаление также очень простое. Мы удаляем, используя ту же логику, что и в простых двоичных деревьях поиска. После удаления мы при необходимости реструктурируем дерево, чтобы сохранить его сбалансированную высоту.

Шаг 1: Найдите элемент в дереве.

Шаг 2: Удалите узел в соответствии с удалением BST.

Шаг 3: Возможны два случая:

Дело 1: Удаление из правого поддерева.

1А. Если BF(узел) = +2 и BF(узел -> левый дочерний элемент) = +1, выполните вращение LL.
1Б. Если BF(узел) = +2 и BF(узел -> левый дочерний элемент) = -1, выполните вращение LR.
1С. Если BF(узел) = +2 и BF(узел -> левый дочерний элемент) = 0, выполните вращение LL.

Кейс 2: Удаление из левого поддерева.

2А. Если BF(узел) = -2 и BF(узел -> правый дочерний элемент) = -1, выполните вращение RR.
2Б. Если BF(узел) = -2 и BF(узел -> правый дочерний элемент) = +1, выполните вращение RL.
2С. Если BF(узел) = -2 и BF(узел -> правый дочерний элемент) = 0, выполните вращение RR.

C++ Пример деревьев AVL

Ниже приведена C++ который реализует деревья AVL:

#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;

struct node {
    struct node *left;
    int data;
    int height;
    struct node *right;

};

class AVL
{
private:
    
public:
    struct node * root;
    AVL(){
        this->root = NULL;

    }

    int calheight(struct node *p){

            if(p->left && p->right){
            if (p->left->height < p->right->height)
                return p->right->height + 1;
            else return  p->left->height + 1;
            }
            else if(p->left && p->right == NULL){
               return p->left->height + 1;
            }
            else if(p->left ==NULL && p->right){
               return p->right->height + 1;
            }
            return 0;

    }

    int bf(struct node *n){
            if(n->left && n->right){
                return n->left->height - n->right->height; 
            }
            else if(n->left && n->right == NULL){
                return n->left->height; 
            }
            else if(n->left== NULL && n->right ){
                return -n->right->height;
            }
    }

    struct node * llrotation(struct node *n){
        struct node *p;
        struct node *tp;
        p = n;
        tp = p->left;

        p->left = tp->right;
        tp->right = p;

        return tp; 
    }


    struct node * rrrotation(struct node *n){
        struct node *p;
        struct node *tp;
        p = n;
        tp = p->right;

        p->right = tp->left;
        tp->left = p;

        return tp; 
    }


    struct node * rlrotation(struct node *n){
        struct node *p;
        struct node *tp;
        struct node *tp2;
        p = n;
        tp = p->right;
        tp2 =p->right->left;

        p -> right = tp2->left;
        tp ->left = tp2->right;
        tp2 ->left = p;
        tp2->right = tp; 
        
        return tp2; 
    }

    struct node * lrrotation(struct node *n){
        struct node *p;
        struct node *tp;
        struct node *tp2;
        p = n;
        tp = p->left;
        tp2 =p->left->right;

        p -> left = tp2->right;
        tp ->right = tp2->left;
        tp2 ->right = p;
        tp2->left = tp; 
        
        return tp2; 
    }

    struct node* insert(struct node *r,int data){
        
        if(r==NULL){
            struct node *n;
            n = new struct node;
            n->data = data;
            r = n;
            r->left = r->right = NULL;
            r->height = 1; 
            return r;             
        }
        else{
            if(data < r->data)
            r->left = insert(r->left,data);
            else
            r->right = insert(r->right,data);
        }

        r->height = calheight(r);

        if(bf(r)==2 && bf(r->left)==1){
            r = llrotation(r);
        }
        else if(bf(r)==-2 && bf(r->right)==-1){
            r = rrrotation(r);
        }
        else if(bf(r)==-2 && bf(r->right)==1){
            r = rlrotation(r);
        }
        else if(bf(r)==2 && bf(r->left)==-1){
            r = lrrotation(r);
        }        

        return r;

        }

    void levelorder_newline(){
        if (this->root == NULL){
            cout<<"\n"<<"Empty tree"<<"\n";
            return;            
        }
        levelorder_newline(this->root);
    }

    void levelorder_newline(struct node *v){
        queue <struct node *> q;
        struct node *cur;
        q.push(v);
        q.push(NULL);      

        while(!q.empty()){
            cur = q.front();
            q.pop();
            if(cur == NULL && q.size()!=0){
                cout<<"\n";
                
                q.push(NULL);
                continue;
            }
            if(cur!=NULL){
                cout<<" "<<cur->data;

                if (cur->left!=NULL){
                q.push(cur->left);
                }
                if (cur->right!=NULL){
                    q.push(cur->right);
                }
            }
            
            
        }
    }
 
    struct node * deleteNode(struct node *p,int data){

        if(p->left == NULL && p->right == NULL){
                if(p==this->root)
                    this->root = NULL;
            delete p;
            return NULL;
        }

        struct node *t;
        struct node *q;
        if(p->data < data){
            p->right = deleteNode(p->right,data);
        }
        else if(p->data > data){
            p->left = deleteNode(p->left,data);
        }
        else{
            if(p->left != NULL){
                q = inpre(p->left);
                p->data = q->data;
                p->left=deleteNode(p->left,q->data);
            }
            else{
                q = insuc(p->right);
                p->data = q->data;
                p->right = deleteNode(p->right,q->data);
            }
        }

        if(bf(p)==2 && bf(p->left)==1){ p = llrotation(p); }                  
        else if(bf(p)==2 && bf(p->left)==-1){ p = lrrotation(p); }
        else if(bf(p)==2 && bf(p->left)==0){ p = llrotation(p); }
        else if(bf(p)==-2 && bf(p->right)==-1){ p = rrrotation(p); }
        else if(bf(p)==-2 && bf(p->right)==1){ p = rlrotation(p); }
        else if(bf(p)==-2 && bf(p->right)==0){ p = llrotation(p); }

        
        return p;
    }

     struct node* inpre(struct node* p){
        while(p->right!=NULL)
            p = p->right;
        return p;    
    }

    struct node* insuc(struct node* p){
        while(p->left!=NULL)
            p = p->left;

        return p;    
    }

    ~AVL(){

    }
};


int main(){

    AVL b;
    int c,x;

    do{
        cout<<"\n1.Display levelorder on newline";
        cout<<"\n2.Insert";
        cout<<"\n3.Delete\n";
        cout<<"\n0.Exit\n";
        cout<<"\nChoice: ";

        cin>>c;

        switch (c)
        {
        case 1:
            b.levelorder_newline();
            // to print the tree in level order
            break;
                  
        case 2:
            cout<<"\nEnter no. ";
            cin>>x;
            b.root = b.insert(b.root,x);
            break;
        
        case 3:
            cout<<"\nWhat to delete? ";
            cin>>x;
            b.root = b.deleteNode(b.root,x);
            break;
            
        case 0:
            break;
        }

     } while(c!=0);
  
}

Запуск примера приведенного выше кода:

Скопируйте приведенный выше код и вставьте «avl.cpp».
Скомпилируйте код:

g++ avl.cpp -o run

Запустите код.

./run

Преимущества деревьев AVL

Высота дерева AVL всегда сбалансирована. Высота никогда не превышает log N, где N — общее количество узлов в дереве.
Он обеспечивает лучшую сложность поиска по сравнению с простыми деревьями бинарного поиска.
Деревья AVL обладают возможностями самобалансировки.

Итого

Деревья AVL — это самобалансирующиеся двоичные деревья поиска.
Коэффициент баланса является фундаментальным атрибутом деревьев AVL.
Коэффициент баланса узла определяется как разница между высотой левого и правого поддерева этого узла.
Допустимые значения коэффициента баланса: -1, 0 и +1.
Операции вставки и удаления требуют выполнения поворотов после нарушения коэффициента балансировки.
Временная сложность операций вставки, удаления и поиска равна O(log N).
Деревья AVL соответствуют всем свойствам деревьев двоичного поиска.
Левое поддерево имеет узлы, меньшие корневого узла. Правое поддерево имеет узлы, которые всегда больше корневого узла.
Деревья AVL используются там, где операции поиска выполняются чаще, чем операции вставки и удаления.

Вы могли бы: