Khi một dãy số được sắp xếp theo một trật tự nào đó, nó sẽ có những tính chất đặc biệt. Một trong những tính chất đó được biểu diễn ở dạng cây rất dễ hình dung. Cây AVL được xem như là là một cây tìm kiếm nhị phân tự cân bằng, và là cấu truc dữ liệu đầu tiên có khả năng này. Trong một cây AVL, tại mỗi nút chiều cao của hai cây con sai khác nhau không quá một. Hiệu quả là các phép chèn (insertion), và xóa (deletion) luôn chỉ tốn thời gian O(log n) trong cả trường hợp trung bình và trường hợp xấu nhất. Phép bổ sung và loại bỏ có thể cần đến việc tái cân bằng bằng một hoặc nhiều phép quay.

Ở đây có một khái niệm là Cây cân bằng hoàn toàn, là cây nhị phân tìm kiếm mà tại mỗi nút của nó, số nút của cây con trái chênh lệch không quá một so với số nút của cây con phải. Chính vì vậy một cây rất khó đạt được trạng thái cân bằng hoàn toàn và cũng rất dễ mất cân bằng vì khi thêm hay hủy các nút trên cây có thể làm cây mất cân bằng (xác suất rất lớn), chi phí cân bằng lại cây tăng vì phải thao tác trên toàn bộ cây.
Tuy nhiên nếu cây cân đối thì việc tìm kiếm sẽ nhanh. Đối với cây cân bằng hoàn toàn, trong trường hợp xấu nhất ta chỉ phải tìm qua log2n phần tử (n là số nút trên cây).

Sau đây là ví dụ một cây cân bằng hoàn toàn (CCBHT):
[You must be registered and logged in to see this image.]

CCBHT có n nút có chiều cao h » log2n. Đây chính là lý do cho phép bảo đảm khả năng tìm kiếm nhanh trên CTDL này.

Do CCBHT là một cấu trúc kém ổn định nên trong thực tế không thể sử dụng. Nhưng ưu điểm của nó lại rất quan trọng. Vì vậy, cần đưa ra một CTDL khác có đặc tính giống CCBHT nhưng ổn định hơn.

Như vậy, cần tìm cách tổ chức một cây đạt trạng thái cân bằng yếu hơn và việc cân bằng lại chỉ xảy ra ở phạm vi cục bộ nhưng vẫn phải bảo đảm chi phí cho thao tác tìm kiếm đạt ở mức O(log2n).
Bây giờ ta lại ngẫm xem Cây nhị phân tìm kiếm cân bằng là cây mà tại mỗi nút của nó độ cao của cây con trái và của cây con phải chênh lệch không quá một. Cây AVL đó.

Dưới đây là ví dụ cây cân bằng (lưu ý, cây này không phải là cây cân bằng hoàn toàn):
Dễ dàng thấy CCBHT là cây cân bằng. Thế nhưng điều ngược lại không đúng. Thế mới xoáy.
AVL là tên viết tắt của các tác giả người Nga đã đưa ra định nghĩa của cây cân bằng Adelson-Velskii và Landis (1962). Vì lý do này, người ta gọi cây nhị phân cân băng là cây AVL. Tù nay về sau, chúng ta sẽ dùng thuật ngữ cây AVL thay cho cây cân bằng.

Từ khi được giới thiệu, cây AVL đã nhanh chóng tìm thấy ứng dụng trong nhiều bài toán khác nhau. Vì vậy, nó mau chóng trở nên thịnh hành và thu hút nhiều nghiên cứu. Từ cây AVL, người ta đã phát triển thêm nhiều loại CTDL hữu dụng khác như cây đỏ-đen (Red-Black Tree), B-Tree, …

Một vấn đề quan trọng, như đã đề cập đến ở phần trước, là ta pjải khẳng định cây AVL n nút phải có chiều cao khoảng log2(n).

Để đánh giá chính xác về chiều cao của cây AVL, ta xét bài toán: cây AVL có chiều cao h sẽ phải có tối thiểu bao nhiêu nút ?

Gọi N(h) là số nút tối thiểu của cây AVL có chiều cao h.

Ta có N(0) = 0, N(1) = 1 và N(2) = 2.

Cây AVL tối thiểu có chiều cao h sẽ có 1 cây con AVL tối thiểu chiều cao h-1 và 1 cây con AVL tối thiểu chiều cao h-2. Như vậy:

N(h) = 1 N(h-1) N(h-2) (1)

Ta lại có: N(h-1) > N(h-2)

Nên từ (1) suy ra:

N(h) > 2N(h-2)

N(h) > 2²N(h-4)

…

N(h) > 2^iN(h-2i)

N(h) > 2^h/2-1

h < 2log₂(N(h)) 2

Như vậy, cây AVL có chiều cao O(log₂(n)).
Ví dụ: cây AVL tối thiểu có chiều cao h=4

[You must be registered and logged in to see this image.]

Bây giờ ta lại bàn sâu hơn 1 chút.
Chỉ số cân bằng của một nút:

Định nghĩa: Chỉ số cân bằng của một nút là hiệu của chiều cao cây con phải và cây con trái của nó.

Đối với một cây cân bằng, chỉ số cân bằng (CSCB) của mỗi nút chỉ có thể mang một trong ba giá trị sau đây:

CSCB(p) = 0 <=> Độ cao cây trái (p) = Độ cao cây phải (p)

CSCB(p) = 1 <=> Độ cao cây trái (p) < Độ cao cây phải (p)

CSCB(p) =-1 <=> Độ cao cây trái (p) > Độ cao cây phải (p)

Để tiện trong trình bày, chúng ta sẽ ký hiệu như sau:

p->balFactor = CSCB(p);

Độ cao cây trái (p) ký hiệu là hL

Độ cao cây phải(p) ký hiệu là hR

Để khảo sát cây cân bằng, ta cần lưu thêm thông tin về chỉ số cân bằng tại mỗi nút. Lúc đó, cây cân bằng có thể được khai báo như sau:

Code:

 typedef struct tagAVLNode {
    char balFactor; //Chỉ số cân bằng
    Data key;
    struct tagAVLNode* pLeft;
    struct tagAVLNode* pRight;
    }AVLNode;
    typedef AVLNode *AVLTree;

Để tiện cho việc trình bày, ta định nghĩa một số hăng số sau:

Code:

#define LH -1 //Cây con trái cao hơn
#define EH -0 //Hai cây con bằng nhau
#define RH  1 //Cây con phải cao hơn

CÁC THAO TÁC CƠ BẢN TRÊN CÂY AVL

Ta nhận thấy trường hợp thêm hay hủy một phần tử trên cây có thể làm cây tăng hay giảm chiều cao, khi đó phải cân bằng lại cây. Việc cân bằng lại một cây sẽ phải thực hiện sao cho chỉ ảnh hưởng tối thiểu đến cây nhằm giảm thiểu chi phí cân bằng. Như đã nói ở trên, cây cân bằng cho phép việc cân bằng lại chỉ xảy ra trong giới hạn cục bộ nên chúng ta có thể thực hiện được mục tiêu vừa nêu.

Như vậy, ngoài các thao tác bình thường như trên CNPTK, các thao tác đặc trưng của cây AVL gồm:
Thêm một phần tử vào cây AVL.
Hủy một phần tử trên cây AVL.
Cân bằng lại một cây vừa bị mất cân bằng.

I. CÁC TRƯỜNG HỢP MẤT CÂN
BẰNG


Ta sẽ không khảo sát tính cân bằng của 1 cây nhị phân bất kỳ mà chỉ quan tâm đến các khả năng mất cân bằng xảy rakhi thêm hoặc hủy một nút trên cây AVL.

Như vậy, khi mất cân bằng, độ lệch chiều cao giữa 2 cây con sẽ là 2. Ta có 6 khả năng sau:

[You must be registered and logged in to see this image.]Trường hợp 1: cây T lệch về bên trái (có 3 khả năng)

[You must be registered and logged in to see this image.]

[You must be registered and logged in to see this image.]Trường hợp 2: cây T lệch về bên phải

Ta có các khả năng sau:[You must be registered and logged in to see this image.]
Ta có thể thấy rằng các trường hợp lệch về bên phải hoàn toàn đối xứng với các trường hợp lệch về bên trái. Vì vậy ta chỉ cần khảo sát trường hợp lệch về bên trái. Trong 3 trường hợp lệch về bên trái, trường hợp T1 lệch phải là phức tạp nhất.
Các trường hợp còn lại giải quyết rất đơn giản.

Sau đây, ta sẽ khảo sát và giải quyết từng trường hợp nêu trên.

[You must be registered and logged in to see this image.]T/h 1.1: cây T1 lệch về bên trái. Ta thực hiện phép quay đơn Left-Left

[You must be registered and logged in to see this image.]

T/h 1.2: cây T1 không lệch. Ta thực hiện phép quay đơn Left-Left

[You must be registered and logged in to see this image.]

T/h 1.3: cây T1 lệch về bên phải. Ta thực hiện phép quay kép Left-Right

Do T1 lệch về bên phải ta không thể áp dụng phép quay đơn đã áp dụng trong 2 trường hợp trên vì khi đó cây T sẽ chuyển từ trạng thái mất cân bằng do lệch trái thành mất cân bằng do lệch phải Þ
cần áp dụng cách khác.

Hình vẽ dưới đây minh họa phép quay kép áp dụng cho trường hợp này:


Lưu ý rằng, trước khi cân bằng cây T có chiều cao h+2 trong cả 3 trường hợp 1.1, 1.2 và 1.3. Sau khi cân bằng, trong 2 trường hợp 1.1 và 1.3 cây có chiều cao h+1; còn ở trường hợp 1.2 cây vẫn có chiều cao h+2. Và trường hợp này cũng là trường hợp duy nhất sau khi cân bằng nút T cũ có chỉ số cân bằng ¹ 0.

Thao tác cân bằng lại trong tất cả các trường hợp đều cóù độ phức tạp O(1).

Với những xem xét trên, xét tương tự cho trường hợp cây T lệch về bên phải, ta có thể xây dựng 2 hàm quay đơn và 2 hàm quay kép sau:

Code:



//quay đơn Left-Left

void rotateLL(AVLTree &T)

{ AVLNode* T1 = T->pLeft;

T->pLeft = T1->pRight;

T1->pRight = T;

switch(T1->balFactor) {

case LH: T->balFactor = EH;

T1->balFactor = EH; break;

case EH: T->balFactor = LH;

T1->balFactor = RH; break;

}

T = T1;

}

//quay đơn Right-Right

void rotateRR(AVLTree &T)

{ AVLNode* T1 = T->pRight;

T->pRight = T1->pLeft;

T1->pLeft = T;

switch(T1->balFactor) {

case RH: T->balFactor = EH;

T1->balFactor = EH; break;

case EH: T->balFactor = RH; break;

T1->balFactor = LH; break;

}

T = T1;

}

//quay kép Left-Right

void rotateLR(AVLTree &T)

{ AVLNode* T1 = T->pLeft;

AVLNode* T2 = T1->pRight;

T->pLeft = T2->pRight;

T2->pRight = T;

T1->pRight = T2->pLeft;

T2->pLeft = T1;

switch(T2->balFactor) {

case LH: T->balFactor = RH;

T1->balFactor = EH; break;

case EH: T->balFactor = EH;

T1->balFactor = EH; break;

case RH: T->balFactor = EH;

T1->balFactor = LH; break;

}

T2->balFactor = EH;

T = T2;

}

//quay kép Right-Left

void rotateRL(AVLTree &T)

{ AVLNode* T1 = T->pRight;

AVLNode* T2 = T1->pLeft;

T->pRight = T2->pLeft;

T2->pLeft = T;

T1->pLeft = T2->pRight;

T2->pRight = T1;

switch(T2->balFactor) {

case RH: T->balFactor = LH;

T1->balFactor = EH; break;

case EH: T->balFactor = EH;

T1->balFactor = EH; break;

case LH: T->balFactor = EH;

T1->balFactor = RH; break;

}

T2->balFactor = EH;

T = T2;

}


Để thuận tiện, ta xây dựng 2 hàm cân bằng lại khi cây bị lệch trái hay lệch phải như sau:

Code:



//Cân băng khi cây bị lêch về bên trái

int balanceLeft(AVLTree &T)

{ AVLNode* T1 = T->pLeft;

switch(T1->balFactor) {

case LH: rotateLL(T); return 2;

case EH: rotateLL(T); return 1;

case RH: rotateLR(T); return 2;

}

return 0;

}

//Cân băng khi cây bị lêch về bên phải

int balanceRight(AVLTree &T)

{ AVLNode* T1 = T->pRight;

switch(T1->balFactor) {

case LH: rotateRL(T); return 2;

case EH: rotateRR(T); return 1;

case RH: rotateRR(T); return 2;

}

return 0;

}


II.THÊM MỘT PHẦN TỬ TRÊN CÂY AVL:

Việc thêm một phần tử vào cây AVL diễn ra tương tự như trên CNPTK. Tuy nhiên, sau khi thêm xong, nếu chiều cao của cây thay đổi, từ vị trí thêm vào, ta phải lần ngược lên gốc để kiểm tra xem có nút nào bị mất cân bằng không. Nếu có, ta phải cân bằng lại ở nút này.

Việc cân bằng lại chỉ cần thực hiện 1 lần tại nơi mất cân bằng. (Tại sao ? Hd: chú ý những khả năng mất cân bằng có thể)

Hàm insert trả về giá trị –1, 0, 1 khi không đủ bộ nhớ, gặp nút cũ hay thành công. Nếu sau khi thêm, chiều cao cây bị tăng, giá trị 2 sẽ được trả về:

Code:



int insertNode(AVLTree &T, DataType X)

{ int res;

if(T) {

if(T->key == X) return 0; //đã có

if(T->key > X) {

res = insertNode(T->pLeft, X);

if(res < 2) return res;

switch(T->balFactor) {

case RH: T->balFactor = EH;

return 1;

case EH: T->balFactor = LH;

return 2;

case LH: balanceLeft(T); return 1;

}

}ELSE {

res = insertNode(T-> pRight, X);

if(res < 2) return res;

switch(T->balFactor) {

case LH: T->balFactor = EH;

return 1;

case EH: T->balFactor = RH;

return 2;

case RH: balanceRight(T); return 1;

}

}

}

T = new TNode;

if(T == NULL) return -1; //thiếu bộ nhớ

T->key = X; T->balFactor = EH;

T->pLeft = T->pRight = NULL;

return 2; // thành công, chiều cao tăng

}


III. HỦY MỘT PHẦN TỬ TRÊN CÂY AVL:

Cũng giống như thao tác thêm một nút, việc hủy một phần tử X ra khỏi cây AVL thực hiện giống như trên CNPTK. Chỉ sau khi hủy, nếu tính cân bằng của cây bị vi phạm ta sẽ thực hiện việc cân bằng lại.

Tuy nhiên việc cân bằng lại trong thao tác hủy sẽ phức tạp hơn nhiều do có thể xảy ra phản ứng dây chuyền. (Tại sao ?)

Hàm delNode trả về giá trị 1, 0 khi hủy thành công hoặc không có X trong cây. Nếu sau khi huỷ, chiều cao cây bị giảm, giá trị 2 sẽ được trả về:

Code:



int delNode(AVLTree &T, DataType X)

{ int res;

if(T==NULL) return 0;

if(T->key > X) {

res = delNode (T->pLeft, X);

if(res < 2) return res;

switch(T->balFactor) {

case LH: T->balFactor = EH;

return 2;

case EH: T->balFactor = RH;

return 1;

case RH: return balanceRight(T);

}

}

if(T->key < X) {

res = delNode (T->pRight, X);

if(res < 2) return res;

switch(T->balFactor) {

case RH: T->balFactor = EH;

return 2;

case EH: T->balFactor = LH;

return 1;

case LH: return balanceLeft(T);

}

}ELSE { //T->key == X

AVLNode* p = T;

if(T->pLeft == NULL) {

T = T->pRight; res = 2;

}ELSE if(T->pRight == NULL) {

T = T->pLeft; res = 2;

}ELSE { //T có cả 2 con

res=searchStandFor(p,T->pRight);

if(res < 2) return res;

switch(T->balFactor) {

case RH: T->balFactor = EH;

return 2;

case EH: T->balFactor = LH;

return 1;

case LH: return balanceLeft(T);

}

}

delete p;

return res;

}

}

//Tìm phần tử thế mạng

int searchStandFor(AVLTree &p, AVLTree &q)

{ int res;

if(q->pLeft) {

res = searchStandFor(p, q->pLeft);

if(res < 2) return res;

switch(q->balFactor) {

case LH: q->balFactor = EH;

return 2;

case EH: q->balFactor = RH;

return 1;

case RH: return balanceRight(T);

}

}ELSE {

p->key = q->key;

p = q;

q = q->pRight;

return 2;

}

}


IV. NHẬN XÉT

[You must be registered and logged in to see this image.] Thao tác thêm một nút có độ phức tạp O(1). Thao tác hủy một nút có độ phức tạp O(h). Với cây cân bằng trung bình 2 lần thêm vào cây thì cần một lần cân bằng lại; 5 lần hủy thì cần một lần cân bằng lại.

[You must be registered and logged in to see this image.] Việc huỷ 1 nút có thể phải cân bằng dây chuyền các nút từ gốc cho đên phần tử bị huỷ trong khi thêm vào chỉ cần 1 lần cân bằng cục bộ.

[You must be registered and logged in to see this image.]
Độ dài đường tìm kiếm trung bình trong cây cân bằng gần bằng cây cân bằng hoàn toàn log₂n, nhưng việc cân bằng lại đơn giản hơn nhiều.

[You must be registered and logged in to see this image.] Một cây cân bằng không bao giờ cao hơn 45% cây cân bằng hoàn toàn tương ứng dù số nút trên cây là bao nhiêu.
(Thu thập)

Bây giờ ta hãy quan sát cái cây nhị phân để làm bài tập cho dễ nhé:
[You must be registered and logged in to see this image.]
Nhận xét:
Khi lấy Q làm tâm, ta quay thằng P qua đầu nút Q theo chiều kim đồng hồ ta quan tâm thấy cái gì?
Thứ nhất là ban đầu cái thằng Q có 2 con là P và C. Để ý ảnh hưởng nhé. Khi quay, con trái P cũng có 2 con A và B lúc này ta sẽ nhận thấy:
* Về vị trí đã nhé, thì:
1. Đầu tiên ta cắt bỏ thằng Q ra khỏi vị trí gốc nối với nó.
2. Ta cắt tiếp thằng con trái của thằng Q rời khỏi nó (thằng P đó).
3. Ta nối thằng P vào gốc mà nối Q ban đầu.
4. Ta cắt bỏ con phải của thằng P (thằng B đó).
5. Ta nối thằng Q vào vị trí làm con phải của thằng P.
6. Ta nối thằng B làm con trái của thằng Q
* Về cao độ của nút: (Có lẽ gọi như thế thì dễ hơn, vì nút lá có cao độ =0, còn các nút ở giữa thì cao độ luôn là Max(Cao độ con trái với Cao độ con phải) + 1.
Xét lại theo bài của thầy thôi.

Đây là phần mô phỏng AVL để các bạn nhập vào các giá trị nguyên, căn cứ vào các giá trị này nó sẽ vẽ ra cây AVL giúp chúng ta dễ hình dung. Lưu ý máy của bạn phải cài Java mới xem được phần mô phỏng này. [You must be registered and logged in to see this link.]




Đánh giá trị vào ô nhập, sau đó chọn Add.

Bài này hay quá.

Anh xem diễn đàn mình có thể chèn được javascript vào không hỗ trợ em vơi.

Thanks anh Admin nhiều nhiều.

Sau khi admin hướng dẫn em mạnh dạn gửi 1 bài cho mọi người tham khảo.

Bài trên chèn bằng Java đó thôi. Nháy vào nút [You must be registered and logged in to see this image.] để chuyển sang HTML. Sau đó dùng các thẻ ví dụ IFRAME mà chèn. Java có thể vào Admin Control tạo một Java class mới, sau đó copy code dán vào. Lấy đường link đưa vào là xong.

Để trả lời bài tập của thầy giáo, nhập dãy tăng dần sau đó random một dãy ngẫu nhiên có các con số đó. Thử ở phần trên xem nó xoay thế nào thì chép vào giấy, mai báo cáo thầy. Thế thôi.

Anh cường ơi.
Các bài thầy giáo giao dich bằng tiếng anh..có phải viết chương trình không ah>
Em làm bài Study of AVL tree range index based on P2P network anh ah
Anh có bài dịch và chương trình ngoài hệ quân sự không anh?
Em học trong Vinh mà.
có gì nhờ anh giúp đỡ em với.
Em cảm ơn anh nhiều ah

Admin:
Viết chương trình hay không là do giáo viên quyết định. Nếu không nói gì, thì ngầm định các bạn phải chuẩn bị 3 phần:
- 1 dữ liệu văn bản (thường là file *.DOC*) để nộp cho thầy.
- 1 dữ liệu dạng trình chiếu (thường file *.PPT*) để báo cáo trước thầy, nếu chưa báo cáo hoặc báo cáo xong rồi, thì chỉnh sửa để gửi cho thầy
- 1 dữ liệu chương trình hoàn chỉnh để binh hoạ báo cáo, cũng nộp thầy nốt. Cái này viết bằng code gì cũng được, miễn là nó phải chạy đúng theo trình bày của bạn ở 2 dạng dữ liệu trên.

Bản dịch theo nhóm tự phân công dịch để hiểu, bạn có thể liên hệ với các nhóm đã đăng ký trùng với bạn để tham khảo. Ngoài ra, khi dùng NET bạn có một công cụ nữa là Google để tìm kiếm, download và cắt dán, cái này tự mình tìm theo tiêu chí của mình, cả nhóm 4 không làm trùng đề tài với bạn, nên không có.

em đang làm đề tài minh họa các thao tác trên cây AVL, Admin hay thành viên nào biết cách, hướng dẫn mình làm với, mình tính sẽ viết bằng C#, cám ơn các bạn!

Ban QT:
Cách 1. Hướng dẫn như trên bạn cần đọc chi tiết. Căn cứ vào hướng dẫn trên bạn có thể code lại.
Cách 2. Bạn down phần java về để được code, sau đó Convert sang C#

[You must be registered and logged in to see this link.]

cám ơn bác Admin, bài viết rất bổ ích

Các ảnh minh họa ở phần đầu không hiển thị , admin có thể sửa lại không !