Cây tìm kiếm nhị phân (BST) là cây nhị phân đã sắp xếp, nơi mọi nút có hai tính chất:
- Cây con phải của nút có khóa lớn hơn khóa nút cha.
- Cây con trái của nút có khóa nhỏ hơn hoặc bằng khóa nút cha.
- Mỗi nút không có quá hai nút con.
Xoay cây là thao tác thay đổi cấu trúc mà không làm thay thứ tự phần tử trên cây nhị phân. Nó di chuyển một nút lên, 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, cây con lớn lên, cải thiện hiệu năng nhiều thao tác. Hướng xoay phụ thuộc vào phía nút cây dịch chuyển, hoặc nút con nào lấy vị trí gốc. Đây là chương trình C++ thực hiện xoay trái trên cây tìm kiếm nhị phân (lưu ý: tiêu đề nói xoay phải nhưng nội dung giống bài xoay trái).
Thuật toán
Begin
Tạo cấu trúc avl khai báo dữ liệu d, con trỏ trái l, con trỏ phải r.
Khai báo lớp avl_tree với các hàm:
height() - Tính chiều cao cây bằng hàm max.
Difference() - Tính chênh lệch chiều cao.
rr_rotat() - Xoay phải-phải.
ll_rotat() - Xoay trái-trái.
lr_rotat() - Xoay trái-phải.
rl_rotat() - Xoay phải-trái.
balance() - Cân bằng cây bằng hệ số cân bằng. Đặt difference vào bal_factor. Nếu bal_factor>1 cân bằng cây con trái. Nếu bal_factor<-1 cân bằng cây con phải.
insert() - Chèn phần tử vào cây.
show() - In cây.
inorder() - In duyệt inorder.
preorder() - In duyệt preorder.
postorder() - In duyệt postorder.
Trong main(), thực hiện switch và gọi hàm theo lựa chọn.
End.
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)