Cây AVL: Xoay, chèn, xóa bằng C++ Ví dụ
Sarah Chen
Cây AVL là gì?
Cây AVL là các cây tìm kiếm nhị phân trong đó chênh lệch giữa chiều cao của cây con bên trái và bên phải là -1, 0 hoặc +1.
Cây AVL còn được gọi là cây tìm kiếm nhị phân tự cân bằng. Những cây này giúp duy trì thời gian tìm kiếm logarit. Nó được đặt theo tên của các nhà phát minh (AVL) Adelson, Velsky và Landis.
Cây AVL hoạt động như thế nào?
Để hiểu rõ hơn về sự cần thiết của cây AVL, chúng ta hãy xem xét một số nhược điểm của cây tìm kiếm nhị phân đơn giản.
Hãy xem xét các khóa sau được chèn theo thứ tự nhất định vào cây tìm kiếm nhị phân.
Chiều cao của cây tăng kích thước tuyến tính khi chúng ta chèn các khóa theo thứ tự giá trị tăng dần của chúng. Do đó, hoạt động tìm kiếm trong trường hợp xấu nhất sẽ mất O(n).
Phải mất thời gian tuyến tính để tìm kiếm một phần tử; do đó không có tác dụng gì khi sử dụng Cây tìm kiếm nhị phân cấu trúc. Mặt khác, nếu chiều cao của cây được cân bằng, chúng ta sẽ có thời gian tìm kiếm tốt hơn.
Bây giờ chúng ta hãy xem xét các phím tương tự nhưng được chèn theo một thứ tự khác.
Ở đây, các phím giống nhau nhưng vì được chèn theo thứ tự khác nên chúng chiếm các vị trí khác nhau và chiều cao của cây vẫn cân bằng. Do đó việc tìm kiếm sẽ không mất nhiều hơn O(log n) cho bất kỳ phần tử nào của cây. Bây giờ rõ ràng là nếu việc chèn được thực hiện chính xác thì chiều cao của cây có thể được giữ cân bằng.
Trong cây AVL, chúng tôi kiểm tra chiều cao của cây trong quá trình chèn. Các sửa đổi được thực hiện để duy trì chiều cao cân bằng mà không vi phạm các thuộc tính cơ bản của Cây tìm kiếm nhị phân.
Hệ số cân bằng trong cây AVL
Hệ số cân bằng (BF) là thuộc tính cơ bản của mọi nút trong cây AVL giúp theo dõi chiều cao của cây.
Thuộc tính của yếu tố cân bằng
- Hệ số cân bằng được gọi là độ chênh lệch giữa chiều cao của cây con bên trái và cây con bên phải.
- Hệ số cân bằng(nút) = chiều cao(nút->trái) – chiều cao(nút->phải)
- Các giá trị được phép của BF là –1, 0 và +1.
- Giá trị –1 chỉ ra rằng cây con bên phải chứa thêm một cây con, tức là cây bên phải nặng.
- Giá trị +1 chỉ ra rằng cây con bên trái chứa thêm một cây con, tức là cây bị nặng.
- Giá trị 0 cho thấy cây bao gồm các nút bằng nhau ở mỗi bên, tức là cây hoàn toàn cân bằng.
Xoay AVL
Để làm cho Cây AVL tự cân bằng, khi chèn hoặc xóa một nút khỏi cây, các phép quay được thực hiện.
Chúng ta thực hiện phép xoay LL, phép xoay RR, phép xoay LR và phép xoay RL sau đây.
- Xoay trái – Xoay trái
- Phải – Xoay Phải
- Xoay phải – trái
- Xoay Trái – Phải
Xoay trái – Xoay trái
Việc xoay này được thực hiện khi một nút mới được chèn vào nút con bên trái của cây con bên trái.
Một vòng quay bên phải được thực hiện. Kiểu xoay này được xác định khi một nút có hệ số cân bằng là +2 và nút con trái của nó có hệ số cân bằng là +1.
Phải – Xoay Phải
Việc xoay này được thực hiện khi một nút mới được chèn vào con bên phải của cây con bên phải.
Một vòng quay trái duy nhất được thực hiện. Kiểu xoay này được xác định khi một nút có hệ số cân bằng là -2 và nút con phải của nó có hệ số cân bằng là -1.
Xoay phải – trái
Việc xoay này được thực hiện khi một nút mới được chèn vào nút con bên phải của cây con bên trái.
Việc xoay này được thực hiện khi một nút có hệ số cân bằng là –2 và nút con bên phải của nó có hệ số cân bằng là +1.
Xoay Trái – Phải
Việc xoay này được thực hiện khi một nút mới được chèn vào con trái của cây con bên phải.
Việc xoay này được thực hiện khi một nút có hệ số cân bằng là +2 và nút con trái của nó có hệ số cân bằng là -1.
Chèn vào cây AVL
Hoạt động chèn gần giống như trong cây tìm kiếm nhị phân đơn giản. Sau mỗi lần chèn, chúng ta cân bằng chiều cao của cây. Hoạt động chèn mất độ phức tạp thời gian tệ nhất là O(log n).
Bước 1: Chèn nút vào cây AVL bằng thuật toán chèn tương tự của BST. Trong ví dụ trên, chèn 160.
Bước 2: Sau khi nút được thêm vào, hệ số cân bằng của mỗi nút sẽ được cập nhật. Sau khi chèn 160, hệ số cân bằng của mỗi nút sẽ được cập nhật.
Bước 3: Bây giờ hãy kiểm tra xem có nút nào vi phạm phạm vi của hệ số cân bằng hay không nếu hệ số cân bằng bị vi phạm, sau đó thực hiện phép quay bằng trường hợp dưới đây. Trong ví dụ trên, hệ số cân bằng 350 bị vi phạm và trường hợp 1 được áp dụng ở đó, chúng tôi thực hiện phép quay LL và cây được cân bằng trở lại.
- Nếu BF(nút) = +2 và BF(nút -> con trái) = +1, thực hiện xoay LL.
- Nếu BF(nút) = -2 và BF(nút -> con phải) = 1, thực hiện xoay RR.
- Nếu BF(nút) = -2 và BF(nút -> con phải) = +1, thực hiện xoay RL.
- Nếu BF(nút) = +2 và BF(nút -> con trái) = -1, thực hiện xoay LR.
Xóa trong cây AVL
Việc xóa cũng rất đơn giản. Chúng tôi xóa bằng cách sử dụng logic tương tự như trong cây tìm kiếm nhị phân đơn giản. Sau khi xóa, chúng tôi cơ cấu lại cây nếu cần để duy trì chiều cao cân bằng.
Bước 1: Tìm phần tử trong cây.
Bước 2: Xóa nút, theo Xóa BST.
Bước 3: Có hai trường hợp có thể xảy ra: -
Trường hợp 1: Xóa từ cây con bên phải.
- 1A. Nếu BF(nút) = +2 và BF(nút -> con trái) = +1, thực hiện xoay LL.
- 1B. Nếu BF(nút) = +2 và BF(nút -> con trái) = -1, thực hiện xoay LR.
- 1C. Nếu BF(nút) = +2 và BF(nút -> con trái) = 0, thực hiện phép quay LL.
Trường hợp 2: Xóa khỏi cây con bên trái.
- 2A. Nếu BF(nút) = -2 và BF(nút -> con phải) = -1, thực hiện xoay RR.
- 2B. Nếu BF(nút) = -2 và BF(nút -> con phải) = +1, thực hiện xoay RL.
- 2C. Nếu BF(nút) = -2 và BF(nút -> con phải) = 0, thực hiện xoay RR.
C++ Ví dụ về cây AVL
Dưới đây là C++ thực hiện cây 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);
}
Ví dụ chạy đoạn mã trên:
- Sao chép mã ở trên và dán vào “avl.cpp”.
- Biên dịch mã:
g++ avl.cpp -o run
- Chạy mã.
./run
Ưu điểm của cây AVL
- Chiều cao của cây AVL luôn cân bằng. Chiều cao không bao giờ vượt quá log N, trong đó N là tổng số nút trong cây.
- Nó cung cấp độ phức tạp về thời gian tìm kiếm tốt hơn khi so sánh với cây tìm kiếm nhị phân đơn giản.
- Cây AVL có khả năng tự cân bằng.
Tổng kết
- Cây AVL là cây tìm kiếm nhị phân tự cân bằng.
- Hệ số cân bằng là thuộc tính cơ bản của cây AVL
- Hệ số cân bằng của một nút được định nghĩa là sự khác biệt giữa chiều cao của cây con bên trái và bên phải của nút đó.
- Các giá trị hợp lệ của hệ số cân bằng là -1, 0 và +1.
- Thao tác chèn và xóa yêu cầu thực hiện phép quay sau khi vi phạm hệ số cân bằng.
- Độ phức tạp thời gian của thao tác chèn, xóa và tìm kiếm là O(log N).
- Cây AVL tuân theo tất cả các thuộc tính của Cây tìm kiếm nhị phân.
- Cây con bên trái có các nút nhỏ hơn nút gốc. Cây con bên phải có các nút luôn lớn hơn nút gốc.
- Cây AVL được sử dụng khi thao tác tìm kiếm diễn ra thường xuyên hơn so với thao tác chèn và xóa.
