Cài cây AVL
Nếu bạn cần học về cây nhị phân tìm kiếm tự cân bằng, cây AVL sẽ là cây cơ bản nhất. Cây AVL là cây nhị phân tìm kiếm, với mỗi thao tác chèn, xóa, cây sẽ tự cân bằng lại bằng một số thao tác xoay cây nếu bị mất cân đối. Bởi vậy mà độ cao của cây luôn là log(n). Sau đây tôi xin trình bày về cách cài cây AVL, và những lỗi thường mắc phải khi cài đặt cây.
1. Bắt đầu với cây nhị phân tìm kiếm
Trước hết bạn cần tạo một cây nhị phân tìm kiếm chỉ có thao tác insert. Để kiểm tra độ chính xác của code, bạn cần tạo thêm hàm show để in ra cây nhị phân. Chúng ta nên dùng cách cấp phát động thay vì lưu các phần tử trên mảng để xử lý linh động các trường hợp.
#include <stdio.h>
struct node {
int value;
node *ll, *rr, *pp;
node(int x=0){ ll=rr=pp=0; value=x; }
};
node * root;
void doInsert(node* a, node* b){
if (b==0) { root=a; a->pp=0; return ; }
if (a->value < b->value)
if (b->ll) doInsert(a, b->ll);
else { b->ll=a; a->pp=b; }
if (a->value > b->value)
if (b->rr) doInsert(a, b->rr);
else { b->rr=a; a->pp=b; }
}
void show(node *a){
if (a==0) return ;
printf("(");
show(a->ll);
printf(" %d ", a->value);
show(a->rr);
printf(")");
}
main(){
int z;
while (scanf("%d", &z) > 0){
doInsert(new node(z), root);
show(root); printf("\n");
}
}
Mô tả
struct node
Mỗi node chứa 5 thông tin cần lưu là value (giá trị), ll (cây con trái), rr (cây con phải), pp (nút cha).
Nút lá có height = 1.
Nút gốc có pp=0 (NULL), ll và rr có thể bằng 0 nếu nút không có cây con trái / phải.
void doInsert(node* a, node* b)
Chèn nút a vào cây con gốc b.
void show(node* a)
hiển thị cây con gốc a.
Nhận xét
Code trên là một code BST, đã cho phép chúng ta thực hiện thao tác chèn. Thao tác tìm kiếm thì khá đơn giản nên chúng ta sẽ giải quyết sau. Thao tác xóa thì giữa BST và AVL khác hẳn nhau nên tôi không ghi ở đây.
Các lỗi thường gặp
Runtime Error
- Kiểm tra xem bạn có thiếu dòng này không. if (b==0) { root=a; a->pp=0; return ; }
- Chú ý rằng khi gán root=a, bạn buộc phải gán a->pp=0, việc này không sinh ra lỗi trong BST, nhưng nó sẽ gây lỗi khi phát triển BST lên cây AVL.
2. Thêm hàm height, lljoin, rrjoin, và thêm lệnh bắt lỗi.
Để xoay cây, cân bằng cây, ta phải tính đưuọc chiều cao của cây con gốc u bất kì, vì vậy ta phải tạo hàm height. Hàm lljoin và rrjoin dùng để nối hai nút với nhau. Trước khi ta truy cập bất cứ nút nào thì ta phải kiểm tra nút đó bằng NULL(nil) hay không. Với cấp phát động, ta luôn phải cẩn thận vì rất có thể bị Runtime error. Bởi vậy các điều sau là rất cần lưu ý.
- Không được truy cập a->ll, a->rr, a->pp, a->value khi chưa kiểm tra xem a có bằng 0 hay không.
- Không được thay thế các lệnh doInsert(a,b) thành a->doInsert(b), show(a) thành a->show(), height(a) thành a->height() vì ta không biết a có bằng NULL hay không.
- Gán a->ll=b thì phải gán b->pp=a. Gán root=a thì phải gán a->pp=0.
#include <stdio.h>
#include <algorithm>
using namespace std;
struct node {
int value;
node *ll, *rr, *pp;
node(int x=0){ ll=rr=pp=0; value=x; }
};
node * root;
int height(node* a){
if (a==0) return 0;
return max(
height(a->ll)+1,
height(a->rr)+1
);
}
int abs(int a, int b){ return a>b?a-b:b-a; }
int absdelta(node* a){
if (a==0) return 0;
return abs(height(a->ll), height(a->rr));
}
void lljoin(node* a, node* b){
if (a) a->pp=b;
if (b) b->ll=a;
else root=a;
}
void rrjoin(node* a, node* b){
if (a) a->pp=b;
if (b) b->rr=a;
else root=a;
}
void doInsert(node* a, node* b){
if (b==0) { rrjoin(a, b); return ; }
if (a==0) { puts("Fatal\n"); return ; }
if (a->value == b->value) { return ; }
if (a->value < b->value)
if (b->ll) doInsert(a, b->ll);
else lljoin(a, b);
if (a->value > b->value)
if (b->rr) doInsert(a, b->rr);
else rrjoin(a, b);
}
void show(node *a){
if (a==0) return ;
printf("(");
show(a->ll);
printf(" %d ", a->value);
show(a->rr);
printf(")");
}
main(){
int z;
while (scanf("%d", &z) > 0){
doInsert(new node(z), root);
show(root); printf("\n");
}
}
Mô tả
void lljoin(node* a, node* b)
Nối a vào b, sau khi nối, a là cây con trái của b.
void rrjoin(node* a, node* b)
Nối a vào b, sau khi nối, a là cây con phải của b.
Các lỗi thường gặp
Runtime error
- Kiểm tra để chắc chắn rằng, trước khi truy cập vào nội dung một phẩn tử, phải kiểm tra xem phần tử đấy có bằng 0 hay không.
- Gán a->ll=b thì phải gán b->pp=a. Gán root=a thì phải gán a->pp=0.
Nhận xét
Hàm lljoin, rrjoin thỏa mãn yêu cầu "Gán a->ll=b thì phải gán b->pp=a. Gán root=a thì phải gán a->pp=0". Hai hàm này giúp cho các phép nối rở nên an toàn hơn. Code trên đã được thêm nhiều hàm chẩn đoán.
3. Xoay trái, xoay phải, và thao tác cân bằng cây
Đây là các thao tác quan trọng nhất trong việc cài cây AVL. Để tự cân bằng thì cây AVL sử dụng các thao tác xoay cây. Hình dưới đây mô tả phép xoay cây.
(hình từ Wikipedia)
Việc biến đổi từ hình bên trái sang hình bên phải gọi là xoay trái. Nút xanh đậm (cha của gamma) được đưa vào chỗ của nút xanh nhạt (cha của alpha). Chú ý rằng beta lúc trước là con của nút xanh đậm, lúc sau là con của nút xanh nhạt.
Việc biến đổi từ hình bên phải sang hình bên trái gọi là xoay phải. Nút xanh nhạt (cha của alpha) được đưa vào chỗ của nút xanh đậm (cha của gamma). Chú ý rằng beta lúc trước là con của nút xanh nhạt, lúc sau là con của nút xanh đậm.
lljoin(a,b) là thao tác xoay phải, a là con trái trực tiếp của b. Sau khi xoay, a nhảy vào vị trí cũ của b. Nút b sẽ trở thành con (con phải trực tiếp) của a.
Để xoay trái, ta thực hiện theo mã giả sau.
lljoin(a, b)
c = b->pp;
lljoin(a->rr, b);
rrjoin(b,a);
join(a, c); // nếu b lúc trước là con trái của c thì lljoin(a,c),
// ngược lại thì rrjoin(a,c)
Xoay phải tương tự như xoay trái, chú ý rằng mã giả ở trên chưa kiểm tra xem a,b,c có bằng NULL hay không. Dưới đây sẽ là hàm xoay trái và xoay phải đầy đủ.
void llrotate(node* a, node* b){
if (b==0) { rrjoin(a, b); return ; }
node* c = b->pp;
lljoin(a->rr, b);
rrjoin(b, a);
if (c==0) { rrjoin(a, c); }
else {
if (c->ll==b) lljoin(a, c);
else rrjoin(a, c);
}
}
void rrrotate(node* a, node* b){
if (b==0) { rrjoin(a, b); return ; }
node* c = b->pp;
rrjoin(a->ll, b);
lljoin(b, a);
if (c==0) { rrjoin(a, c); }
else {
if (c->rr==b) rrjoin(a, c);
else lljoin(a, c);
}
}
Các lỗi thường gặp
Runtime error
- Kiểm tra để chắc chắn rằng, trước khi truy cập vào nội dung một phẩn tử, phải kiểm tra xem phần tử đấy có bằng 0 hay không.
Tiếp theo tôi xin được trình bày về thao tác cân bằng cây. Một nút cần phải được cân bằng khi chênh lệch độ cao của hai cây con của nút đó lớn hơn 1. Ta có nhận xét rằng nếu một nút bị lệch trái (height(a->ll) - height(a->rr) > 1) thì ta phải xoay phải (llrotate(a->ll, a)), và ngược lại. Tuy nhiên, thao tác xoay phải này có thể không khiến cây cân bằng mà khiến cây lệch phải! Bởi vậy có 2 trường hợp đặc biệt mà ta cần xét trước khi xoay.
(hình từ Wikipedia)
balance(a)
if (absdelta(a)<=1) return;
balance(a->ll), balance(a->rr),
if (height(a->ll) > height(a->rr)
if (height(a->ll->ll) < height(a->ll->rr)) rrrotate(a->ll->rr, a->ll);
llrotate(a->ll, a);
else if (height(a->rr) > height(a->ll))
if (height(a->rr->rr) < height(a->rr->ll)) llrotate(a->rr->ll, a->rr);
rrrotate(a->rr, a);
Tất nhiên mã giả chưa kiểm tra trường hợp a=0, a->ll=0 và a->rr=0. Dưới đây là code đầy đủ.
void balance(node *a){
if (a==0) return ;
if (absdelta(a)<=1) return;
balance(a->ll);
balance(a->rr);
if (height(a->ll) > height(a->rr)){
if (a->ll==0) { puts("Fatal"); return ; }
if (height(a->ll->ll) < height(a->ll->rr)) rrrotate(a->ll->rr, a->ll);
llrotate(a->ll, a);
}
else if (height(a->rr) > height(a->ll)){
if (a->rr==0) { puts("Fatal\n"); return ; }
if (height(a->rr->rr) < height(a->rr->ll)) llrotate(a->rr->ll, a->rr);
rrrotate(a->rr, a);
}
}
Các lỗi thường gặp
Runtime error
- Kiểm tra để chắc chắn rằng, trước khi truy cập vào nội dung một phẩn tử, phải kiểm tra xem phần tử đấy có bằng 0 hay không.
Cần sửa hàm doInsert một chút để BST của chúng ta trở thành cây AVL.
4. Các thao tác chèn, xóa, tìm kiếm, tăng tốc hàm height
Việc cân bằng lại cây cần được thực hiện sau khi chèn một phần tử vào cây. Đơn giản là ta chỉ việc thêm lệnh balance(b) vào cuối hàm doInsert(a,b).
void doInsert(node* , node* b){
...
balance(b);
}
Thao tác tìm kiếm rất đơn giản.
node* doSearch(int x, node* a){
if (a==0) return 0;
if (x==a->value) return a;
if (x<a->value) return doSearch(x, a->ll);
if (x>a->value) return doSearch(x, a->rr);
}
Thao tác xóa được thực hiện như sau. Giả sử a là nút cần xóa.
- Nếu a chỉ có một con, việc đơn giản là nối con duy nhất của a với cha của a.
- Nếu a có hai con, tráo đổi nội dung (chỉ tráo đổi value, các giá trị ll, rr, pp được giữ nguyên) của nút a với nút phải nhất của cây con trái, gọi nút này là nút b (tức là tráo đổi a->value, b->value). Sau đó xóa b như thuật toán trên (chắc chắn nút b lúc này chỉ có nhiều nhất một con). Phần cài đặt hơi dài nên tôi không viết chi tiết ở đây, hơn nữa không phải bài tập nào cũng có thao tác Delete. Các bạn có thể tìm code đầy đủ cho thao tác xóa tại avl.cpp (1).
Hàm height của chúng ta cần được nâng cấp, nó không thể lúc nào cũng đệ quy để tìm kết quả được. Vì vậy ta thêm giá trị a->height vào nút a. a->height=0 cho thấy là độ cao của a là chưa xác định, nó cần được tính bằng cách đệ quy như ban đầu. a->height=1 cho thấy a là nút lá. Mỗi khi insert, delete, độ cao của các nút trên đường đi từ gốc đến nút đưuọc insert, delete lại thay đổi (không biết tăng giảm bao nhiêu). Vì thế, mỗi khi lljoin hay rrjoin, ta phải cho các nút trên đường đi từ gốc đến nút ta lljoin hay rrjoin, có height=0.
void requireHeightToRoot(node* a){
for (;;){
if (a==0) return;
if (a->height==0) return;
a->height = 0;
a = a->pp;
}
}
#define rhtr requireHeightToRoot
void lljoin(node* a, node* b){
if (a) a->pp=b;
if (b) b->ll=a;
else root=a;
rhtr(a); rhtr(b);
}
void rrjoin(node* a, node* b){
if (a) a->pp=b;
if (b) b->rr=a;
else root=a;
rhtr(a); rhtr(b);
}
Trên đây là tất cả những gì tôi tìm hiểu được về cây AVL. Mong rằng chúng giúp ích cho các bạn. Chúc các bạn thành công.