Cây AVL là cây tìm kiếm nhị phân tự cân bằng, nơi chênh lệch chiều cao giữa cây con trái và phải không quá 1 đối với mọi nút.
Xoay cây là thao tác thay đổi cấu trúc mà không làm thay thứ tự các phần tử trên cây AVL. Nó di chuyển một nút lên và một nút xuống. Dùng để thay đổi hình dạng cây, giảm chiều cao bằng cách di chuyển cây con nhỏ xuống và cây con lớn lên, cải thiện hiệu năng nhiều thao tác cây. Hướng xoay phụ thuộc vào phía mà các nút cây dịch chuyển, hoặc nói cách khác phụ thuộc vào nút con nào lấy vị trí gốc. Đây là chương trình C++ triển khai cây AVL.
Mô tả hàm:
height(avl *): Tính chiều cao cây AVL cho trước.
difference(avl *): Tính chênh lệch chiều cao giữa các cây con của cây cho trước.
avl *rr_rotat(avl *): Xoay phải-phải là kết hợp xoay phải theo sau bởi xoay phải.
avl *ll_rotat(avl *): Xoay trái-trái là kết hợp xoay trái theo sau bởi xoay trái.
avl *lr_rotat(avl*): Xoay trái-phải là kết hợp xoay trái theo sau bởi xoay phải.
avl *rl_rotat(avl *): Kết hợp xoay phải theo sau bởi xoay trái.
avl * balance(avl *): Thực hiện cân bằng cây bằng cách lấy hệ số cân bằng.
avl * insert(avl*, int): Thực hiện chèn giá trị vào cây.
show(avl*, int): Hiển thị giá trị cây.
inorder(avl *): Duyệt cây theo thứ tự in-order.
preorder(avl *): Duyệt cây theo thứ tự pre-order.
postorder(avl*): Duyệt cây theo thứ tự post-order.
Ví dụ
#include<iostream>
#include<cstdio>
#include<sstream>
#include<algorithm>
#define pow2(n) (1 << (n))
using namespace std;
struct avl {
int d;
struct avl *l;
struct avl *r;
}*r;
class avl_tree {
public:
int height(avl *);
int difference(avl *);
avl *rr_rotat(avl *);
avl *ll_rotat(avl *);
avl *lr_rotat(avl*);
avl *rl_rotat(avl *);
avl * balance(avl *);
avl * insert(avl*, int);
void show(avl*, int);
void inorder(avl *);
void preorder(avl *);
void postorder(avl*);
avl_tree() {
r = NULL;
}
};
int avl_tree::height(avl *t) {
int h = 0;
if (t != NULL) {
int l_height = height(t->l);
int r_height = height(t->r);
int max_height = max(l_height, r_height);
h = max_height + 1;
}
return h;
}
int avl_tree::difference(avl *t) {
int l_height = height(t->l);
int r_height = height(t->r);
int b_factor = l_height - r_height;
return b_factor;
}
avl *avl_tree::rr_rotat(avl *parent) {
avl *t;
t = parent->r;
parent->r = t->l;
t->l = parent;
cout<<"Right-Right Rotation";
return t;
}
avl *avl_tree::ll_rotat(avl *parent) {
avl *t;
t = parent->l;
parent->l = t->r;
t->r = parent;
cout<<"Left-Left Rotation";
return t;
}
avl *avl_tree::lr_rotat(avl *parent) {
avl *t;
t = parent->l;
parent->l = rr_rotat(t);
cout<<"Left-Right Rotation";
return ll_rotat(parent);
}
avl *avl_tree::rl_rotat(avl *parent) {
avl *t;
t= parent->r;
parent->r = ll_rotat(t);
cout<<"Right-Left Rotation";
return rr_rotat(parent);
}
avl *avl_tree::balance(avl *t) {
int bal_factor = difference(t);
if (bal_factor > 1) {
if (difference(t->l) > 0)
t = ll_rotat(t);
else
t = lr_rotat(t);
}
else if (bal_factor < -1) {
if (difference(t->r) > 0)
t= rl_rotat(t);
else
t = rr_rotat(t);
}
return t;
}
avl *avl_tree::insert(avl *r, int v) {
if (r == NULL) {
r= new avl;
r->d = v;
r->l = NULL;
r->r= NULL;
return r;
}
else if (v< r->d) {
r->l= insert(r->l, v);
r = balance(r);
}
else if (v >= r->d) {
r->r= insert(r->r, v);
r = balance(r);
}
return r;
}
void avl_tree::show(avl *p, int l) {
int i;
if (p != NULL) {
show(p->r, l+ 1);
cout<<" ";
if (p == r)
cout << "Root -> ";
for (i = 0; i < l&& p != r; i++)
cout << " ";
cout << p->d;
show(p->l, l + 1);
}
}
void avl_tree::inorder(avl *t) {
if (t == NULL)
return;
inorder(t->l);
cout << t->d << " ";
inorder(t->r);
}
void avl_tree::preorder(avl *t) {
if (t == NULL)
return;
cout << t->d << " ";
preorder(t->l);
preorder(t->r);
}
void avl_tree::postorder(avl *t) {
if (t == NULL)
return;
postorder(t ->l);
postorder(t ->r);
cout << t->d << " ";
}
int main() {
int c, i;
avl_tree avl;
while (1) {
cout << "1.Insert Element into the tree" << endl;
cout << "2.show Balanced AVL Tree" << endl;
cout << "3.InOrder traversal" << endl;
cout << "4.PreOrder traversal" << endl;
cout << "5.PostOrder traversal" << endl;
cout << "6.Exit" << endl;
cout << "Enter your Choice: ";
cin >> c;
switch (c) {
case 1:
cout << "Enter value to be inserted: ";
cin >> i;
r= avl.insert(r, i);
break;
case 2:
if (r == NULL) {
cout << "Tree is Empty" << endl;
continue;
}
cout << "Balanced AVL Tree:" << endl;
avl.show(r, 1);
cout<<endl;
break;
case 3:
cout << "Inorder Traversal:" << endl;
avl.inorder(r);
cout << endl;
break;
case 4:
cout << "Preorder Traversal:" << endl;
avl.preorder(r);
cout << endl;
break;
case 5:
cout << "Postorder Traversal:" << endl;
avl.postorder(r);
cout << endl;
break;
case 6:
exit(1);
break;
default:
cout << "Wrong Choice" << endl;
}
}
return 0;
}
Kết quả
1.Insert Element into the tree 2.show Balanced AVL Tree 3.InOrder traversal 4.PreOrder traversal 5.PostOrder traversal 6.Exit Enter your Choice: 1 Enter value to be inserted: 13 ... (đã rút gọn kết quả mẫu)