Дерева AVL: обертання, вставка, видалення з C++ Приклад
Сара Чен
Що таке дерева AVL?
AVL дерева це двійкові дерева пошуку, в яких різниця між висотою лівого та правого піддерева становить -1, 0 або +1.
Дерева AVL також називають самобалансуючим бінарним деревом пошуку. Ці дерева допомагають підтримувати логарифмічний час пошуку. Він названий на честь своїх винахідників (AVL) Адельсона, Вельського та Ландіса.
Як працює AVL Tree?
Щоб краще зрозуміти потребу в деревах AVL, розглянемо деякі недоліки простих бінарних дерев пошуку.
Розглянемо наступні ключі, вставлені в заданому порядку в бінарному дереві пошуку.
Висота дерева лінійно зростає, коли ми вставляємо ключі в порядку зростання їх значення. Таким чином, операція пошуку в гіршому випадку займає O(n).
Для пошуку елемента потрібен лінійний час; тому немає сенсу використовувати Бінарне дерево пошуку структура. З іншого боку, якщо висота дерева збалансована, ми отримуємо кращий час пошуку.
Давайте тепер розглянемо ті самі ключі, але вставлені в іншому порядку.
Тут ключі однакові, але оскільки вони вставлені в іншому порядку, вони займають різні позиції, а висота дерева залишається збалансованою. Отже, пошук не займатиме більше O(log n) для будь-якого елемента дерева. Тепер очевидно, що якщо вставлення виконано правильно, висота дерева може бути збалансованою.
У деревах AVL ми перевіряємо висоту дерева під час операції вставки. Внесено зміни, щоб підтримувати збалансовану висоту без порушення основних властивостей бінарного дерева пошуку.
Фактор балансу в деревах AVL
Коефіцієнт балансу (BF) є фундаментальним атрибутом кожного вузла в деревах AVL, який допомагає контролювати висоту дерева.
Властивості фактора балансу
- Коефіцієнт балансу відомий як різниця між висотою лівого та правого піддерева.
- Фактор балансу (вузол) = висота (вузол->ліворуч) – висота (вузол->праворуч)
- Дозволені значення BF: –1, 0 і +1.
- Значення –1 вказує на те, що праве піддерево містить одне додаткове, тобто дерево важке справа.
- Значення +1 вказує, що ліве піддерево містить одне зайве, тобто дерево залишається важким.
- Значення 0 показує, що дерево містить рівні вузли з кожного боку, тобто дерево ідеально збалансоване.
Обертання AVL
Щоб збалансувати дерево AVL, при вставці або видаленні вузла з дерева виконуються обертання.
Ми виконуємо наступне обертання 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(node) = -2 і BF(node -> right-child) = 1, виконайте обертання RR.
- Якщо BF(вузол) = -2 і BF(вузол -> правий дочірній) = +1, виконайте поворот RL.
- Якщо BF(вузол) = +2 і BF(вузол -> лівий дочірній) = -1, виконайте обертання LR.
Видалення в деревах AVL
Видалення також є дуже простим. Ми видаляємо за тією ж логікою, що й у простих бінарних деревах пошуку. Після видалення ми за потреби реструктуруємо дерево, щоб зберегти його збалансовану висоту.
Крок 1: Знайдіть елемент у дереві.
Крок 2: Видаліть вузол відповідно до видалення BST.
Крок 3: Можливі два випадки: -
Справа 1: Видалення з правого піддерева.
- 1А. Якщо BF(вузол) = +2 і BF(вузол -> лівий дочірній) = +1, виконайте обертання LL.
- 1B. Якщо BF(вузол) = +2 і BF(вузол -> лівий дочірній) = -1, виконайте обертання LR.
- 1С. Якщо BF(вузол) = +2 і BF(вузол -> лівий дочірній) = 0, виконайте обертання LL.
Справа 2: Видалення з лівого піддерева.
- 2А. Якщо BF(node) = -2 і BF(node -> right-child) = -1, виконайте обертання RR.
- 2B. Якщо BF(вузол) = -2 і BF(вузол -> правий дочірній) = +1, виконайте поворот RL.
- 2C. Якщо BF(node) = -2 і BF(node -> right-child) = 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 використовуються там, де операція пошуку виконується частіше, ніж операції вставки та видалення.
