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

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

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

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

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

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

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


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

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

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

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

АВЛ Работа с деревом

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

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

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

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

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


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

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

Ротации АВЛ

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

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

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

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

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


Дерево AVL слева – вращение влево

Дерево AVL слева – вращение влево

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

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

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

Дерево AVL вправо – вращение вправо

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

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

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

Дерево AVL, вращение вправо – влево

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

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

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

Дерево AVL, вращение влево-вправо

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

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

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


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

Реализация вставки дерева AVL

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

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

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

  1. Если BF(узел) = +2 и BF(узел -> левый дочерний элемент) = +1, выполните вращение LL.
  2. Если BF(узел) = -2 и BF(узел -> правый дочерний элемент) = 1, выполните вращение RR.
  3. Если BF(узел) = -2 и BF(узел -> правый дочерний элемент) = +1, выполните вращение RL.
  4. Если 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.

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

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

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

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

Пример 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);
  
}

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

  1. Скопируйте приведенный выше код и вставьте «avl.cpp».
  2. Скомпилируйте код:
g++ avl.cpp -o run
  1. Запустите код.
./run

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

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

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

Выводы

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