Cấu trúc dữ liệu và giải thuật I - Bài 13

CÂY CÂN BẰNG Mục tiêu Trình bày khái niệm cây cân bằng và các ưu điểm của cây cân bằng. Tìm hiểu một số kiểu cây cân bằng Nội dung I. Cây nhị phân cân bằng hoàn toàn 1.Định nghĩa 2.Đánh giá
Nội dung trích xuất từ tài liệu:
Cấu trúc dữ liệu và giải thuật I - Bài 13BÀI 13 CÂY CÂN BẰNG Mục tiêu Trình bày khái niệm cây cân bằng và các ưu điểm của cây cân bằng. Tìm hiểu một số kiểu cây cân bằng Nội dung I. Cây nhị phân cân bằng hoàn toàn 1.Định nghĩa 2.Đánh giá II.Cây nhị phân cân bằng (AVL tree) 1.Định nghĩa 2. Lịch sử 3..Đánh giá chiều cao của cây AVL 4.Cấu trúc dữ liệu 5.Đánh giáI.CÂY NHỊ PHÂN CÂN BẰNG HOÀN TOÀN I.1Định nghĩaCâ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âycon trái chênh lệch không quá một so với số nút của cây con phải. I.2 Đánh giá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 lớn 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):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ăngtì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ốngCCBHT 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ằnglạ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).II. CÂY NHỊ PHÂN CÂN BẰNG (AVL) II.1 Định nghĩa: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.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. Điều ngược lại không đúng. II.2 Lịch sử cây cân bằng (AVL Tree)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ằngAdelson-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ánkhá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âyAVL, 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, … II.3 Chiều cao của cây AVLMột vấn đề quan trọng, như đã đề cập đến ở phần trước, là ta pjải khẳng định cây AVL nnú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 caoh 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âycon 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) > 22N(h-4)…N(h) > 2iN(h-2i) N(h) > 2h/2-1 h < 2log2(N(h)) + 2Như vậy, cây AVL có chiều cao O(log2(n)).Ví dụ: cây AVL tối thiểu có chiều cao h=4 II.4 Cấu trúc dữ liệu cho cây AVLChỉ 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 contrá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ộttrong 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: 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: #define LH -1 //Cây con trái cao hơn #define EH -0 //Hai cây con bằng nhau 1 //Cây con phải cao hơn #define RH II.5 Đánh giá cây AVL Cây cân bằng là CTDL ổn định hơn hẳn CCBHT vì chỉ khi thêm hủy làm cây thay đổichiều cao các trường hợp mất cân bằng mới có khả năng xảy ra. Cây AVL với chiều cao được khốn ...