Giáo trình Cấu trúc dữ liệu nâng cao I và II

trường next chỉ phần tử kế bị xung đột. Các phần tử bị xung đột được kết nối nhau qua trường kết nối next. *) Bảng băm với phương pháp dò tuần tự: Khi thêm phần tử vào bảng băm nếu bị đụng độ thì sẽ dò địa chỉ kế tiếp… cho đến khi gặp địa chỉ trống đầu tiên thì thêm phần tử vào địa chỉ này. *) Bảng băm với phương pháp dò bậc hai: ví dụ khi thêm phần tử vào bảng băm này, nếu băm lần đầu bị xung đột thì sẽ dò đến địa chi mới, ở lần dò thứ i sẽ xét phần tử cách i2 cho đến khi gặp địa chỉ trống đầu tiên thì thêm phần tử vào địa chỉ này. *) Bảng băm với phương pháp băm kép: bảng băm này dùng hai hàm băm khác nhau, băm lần đầu với hàm băm thứ nhất nếu bị xung đột thì xét địa chỉ khác bằng hàm băm thứ hai. Ưu điểm của các Bảng băm: Bảng băm là một cấu trúc dung hòa giữa thời gian truy xuất và dung lượng bộ nhớ: - Nếu không có sự giới hạn về bộ nhớ thì chúng ta có thể xây dựng bảng băm với mỗi khóa ứng với một địa chỉ với mong muốn thời gian truy xuất tức thời. - Nếu dung lượng bộ nhớ có giới hạn thì tổ chức một số khóa có cùng địa chỉ, khi đó tốc độ truy xuất sẽ giảm. Bảng băm dược ứng dụng nhiều trong thực tế, rất thích hợp khi tổ chức dữ liệu có kích thước lớn và được lưu trữ ở bộ nhớ ngoài. 5 6 3. Các phương pháp tránh xảy ra đụng độ 2.4.1. Bảng băm với phương pháp kết nối trực tiếp (Direct chaining Method) Bảng băm được cài đặt bằng các danh sách liên kết, các phần tử trên bảng băm được “băm” thành M danh sách liên kết (từ danh sách 0 đến danh sách M–1). Các phần tử bị xung đột tại địa chỉ i được kết nối trực tiếp với nhau qua danh sách liên kết i. Chẳng hạn, với M=10, các phần tử có hàng đơn vị là 9 sẽ được băm vào danh sách liên kết i = 9. Khi thêm một phần tử có khóa k vào bảng băm, hàm băm f(k) sẽ xác định địa chỉ i trong khoảng từ 0 đến M-1 ứng với danh sách liên kết i mà phần tử này sẽ được thêm vào. Khi tìm một phần tử có khóa k vào bảng băm, hàm băm f(k) cũng sẽ xác định địa chỉ i trong khoảng từ 0 đến M-1 ứng với danh sách liên kết i có thể chứa phần tử này. Như vậy, việc tìm kiếm phần tử trên bảng băm sẽ được qui về bài toán tìm kiếm một phần tử trên danh sách liên kết. Để minh họa ta xét bảng băm có cấu trúc như sau: - Tập khóa K: tập số tự nhiên - Tập địa chỉ M: gồm 10 địa chỉ (M={0, 1, …, 9} - Hàm băm h(key) = key % 10. 30, 50,60,11,21,31,… Hình 1.6. bảng băm với phương pháp kết nối trực tiếp Hình trên minh họa bảng băm vừa mô tả. Theo hình vẽ, bảng băm đã "băm" phần tử trong tập khoá K theo 10 danh sách liên kết khác nhau, mỗi danh sách liên kết gọi là một bucket: · Bucket 0 gồm những phần tử có khóa tận cùng bằng 0. · Bucket i(i=0 | … | 9) gồm những phần tử có khóa tận cùng bằng i. · Khi khởi động bảng băm, con trỏ đầu của các bucket là NULL. Theo cấu trúc này, với tác vụ insert, hàm băm h(k) sẽ được dùng để tính địa chỉ của khoá k, tức là xác định bucket chứa phần tử và đặt phần tử cần chèn vào bucket này. Với tác vụ search, hàm băm sẽ được dùng để tính địa chỉ và tìm phần tử trên bucket tương ứng + i=h(k) => thuoc danh sach thu I (bucket[i] + tim kiem khoa K tren danh sach bucket[i] Cài đặt bảng băm dùng phương pháp kết nối trực tiếp : 7 8 a. Khai báo cấu trúc bảng băm: #define M 100 struct nodes { int key; struct nodes *next }; typedef struct nodes *NODEPTR; //khai bao kieu con tro chi nut /*khai bao mang bucket chua M con tro dau cua Mbucket */ NODEPTR bucket[M]; BT: xay dung bang bam theo PP ket noi truc tiep b.Các phép toán: - Tính giá trị hàm băm: Giả sử chúng ta chọn hàm băm dạng %: h(key)=key % M. - Phép toán initbuckets: khởi tạo các bucket băng Null. - Phép toán emmptybucket(b): kiểm tra bucket b có bị rỗng không? - Phép toán emmpty: Kiểm tra bảng băm có rỗng không? - Phép toán insert: Thêm phần tử có khóa k vào bảng băm. + i=h(k) + ktra bucket [i]: neu rong =>cc o nho cho bucket, gan khoa k them phan tu co khoa k vao ds theo thu tu tang dan. - Phép toán remove: Xóa phần tử có khóa k trong bảng băm. - Phép toán clear: Xóa tất cả các phần tử trong bảng băm. - Phép toán traversebucket: Xử lý tất cả các phần tử trong bucket b. - Phép toán traverse: Xử lý tất cả các phần tử trong bảng băm. - Phép toán search: Tìm kiếm một phần tử trong bảng băm, nếu không tìm thấy hàm này trả về hàm NULL, nếu tìm thấy hàm này trả về địa chỉ của phần tử có khóa k. B1: Tìm danh sách liên kết có thể chứa khóa k b = h(k); p = bucket[b]; B2: Tìm khóa k trong danh sách liên kết p. 9 Nhận xét bảng băm dùng phương pháp kết nối trực tiếp: Bảng băm dùng phương pháp kết nối trực tiếp sẽ "băm” n phần tử vào danh sách liên kết (M bucket). Để tốc độ thực hiện các phép toán trên bảng hiệu quả thì cần chọn hàm băm sao cho băm đều n phần tử của bảng băm cho M bucket, lúc này trung bình mỗi bucket sẽ có n/M phần tử. Chẳng hạn, phép toán search sẽ thực hiện việc tìm kiếm tuần tự trên bucket nên thời gian tìm kiếm lúc này có bậc 0(n/M) – nghĩa là, nhanh gấp M lần so với việc tìm kiếm trên một danh sách liên kết có n phần tử. Nếu chọn M càng lớn thì tốc độ thực hiện các phép toán trên bảng băm càng nhanh, tuy nhiên lại càng dùng nhiều bộ nhớ. Do vậy, cần điều chỉnh M để dung hòa giữa tốc độ truy xuất và dung lượng bộ nhớ. · Nếu chọn M=n thì năng xuất tương đương với truy xuất trên mảng (có bậc O(1)), tuy nhiên tốn nhiều bộ nhớ. 2.4.2. Bảng băm với phương pháp kết nối hợp nhất Mô tả: - Cấu trúc dữ liệu: Tương tự như trong trường hợp cài đặt bằng phương pháp kết nối trực tiếp, bảng băm trong trường hợp này được cài đặt bằng danh sách liên kết dùng mảng, có M phần tử. Các phần tử bị xung đột tại một địa chỉ được kết nối nhau qua một danh sách liên kết. Mỗi phần tử của bảng băm gồm hai trường: · Trường key: chứa khóa của mỗi phần tử · Trường next: con trỏ chỉ đến phần tử kế tiếp nếu có xung đột. - Khởi động: Khi khởi động, tất cả trường key của các phần tử trong bảng băm được gán bởi giá trị NullKey, còn tất cả các trường next được gán –1. - Thêm mới một phần tử: Khi thêm mới một phần tử có khóa key vào bảng băm, hàm băm hkey) sẽ xác định địa chỉ i trong khoảng từ 0 đến M-1. · Nếu chưa bị xung đột thì thêm phần tử mới vào địa chỉ này. · Nếu bị xung đột thì phần tử mới được cấp phát là phần tử trống phía cuối mảng. Cập nhật liên kết next sao cho các phần tử bị xung đột hình thành một danh sách liên kết. - Tìm kiếm: Khi tìm kiếm một phần tử có khóa key trong bảng băm, hàm băm h(key) sẽ giúp giới hạn phạm vi tìm kiếm bằng cách xác định địa chỉ i trong 10 khoảng từ 0 đến M-1, và việc tìm kiếm phần tử khóa có khoá key trong danh sách liên kết sẽ xuất phát từ địa chỉ i. Để minh họa cho bảng băm với phương pháp kết nối hợp nhất, xét ví dụ sau: Giả sử, khảo sát bảng băm có cấu trúc như sau: - Tập khóa K: tập số tự nhiên - Tập địa chỉ M: gồm 10 địa chỉ (M={0, 1, …, 9} - Hàm băm f(key) = key % 10. VD: Key : 11 12 21 1 13 Hash: 1 2 1 1 3 Add Key Next Add Key Next 0 NullKey -1 0 NullKey -1 1 NullKey -1 1 11 9 … NullKey -1 2 12 -1 M-1 NullKey -1 3 13 -1 … NullKey -1 8 1 -1 9 21 8 Khai báo cấu trúc bảng băm: #define NULLKEY –1 #define M 100 typedef struct node { int key; //khoa cua nut tren bang bam int next; //con tro chi nut ke tiep khi co xung dot } NODE; 11 NODE hashtable[M]; //Khai bao bang bam Cài đặt bảng băm dùng phương pháp kết nối hợp nhất: 2.4.3. Bảng băm với phương pháp dò tuần tự Mô tả: - Cấu trúc dữ liệu: Bảng băm trong trường hợp này được cài đặt bằng danh sách kề có M phần tử, mỗi phần tử của bảng băm là một mẫu tin có một trường key để chứa khoá của phần tử. Khi khởi động bảng băm thì tất cả trường key được gán NullKey; - Khi thêm phần tử có khoá key vào bảng băm, hàm băm h(key) sẽ xác định địa chỉ i trong khoảng từ 0 đến M-1: · Nếu chưa bị xung đột thì thêm phần tử mới vào địa chỉ này. · Nếu bị xung đột thì hàm băm lại lần 1, hàm h1 sẽ xét địa chỉ kế tiếp, nếu lại bị xung đột thì hàm băm thì hàm băm lại lần 2, hàm h2 sẽ xét địa chỉ kế tiếp nữa, …, và quá trình cứ thế cho đến khi nào tìm được địa chỉ trống và thêm phần tử mới vào địa chỉ này. - Khi tìm một phần tử có khoá key trong bảng băm, hàm băm h(key) sẽ xác định địa chỉ i trong khoảng từ 0 đến M-1, tìm phần tử khoá key trong bảng băm xuất phát từ địa chỉ i. Hàm băm lại lần i được biểu diễn bằng công thức sau: f(key)=(f(key)+i) %M với f(key) là hàm băm chính của bảng băm. Lưu ý địa chỉ dò tìm kế tiếp là địa chỉ 0 nếu đã dò đến cuối bảng. Giả sử, khảo sát bảng băm có cấu trúc như sau: - Tập khóa K: tập số tự nhiên - Tập địa chỉ M: gồm 10 địa chỉ (M={0, 1, …, 9} - Hàm băm h(key) = key % 10. 12 Hình thể hiện thêm các nut 32, 53, 22, 92, 17, 34, 24, 37, 56 vào bảng băm. 0 NULL 0 NULL 0 NULL 0 NULL 0 56 1 NULL 1 NULL 1 NULL 1 NULL 1 NULL 2 32 2 32 2 32 2 32 2 32 3 53 3 53 3 53 3 53 3 53 4 NULL 4 22 4 22 4 22 4 22 5 NULL 5 92 5 92 5 92 5 92 6 NULL 6 NULL 6 34 6 34 6 34 7 NULL 7 NULL 7 17 7 17 7 17 8 NULL 8 NULL 8 NULL 8 24 8 24 9 NULL 9 NULL 9 NULL 9 37 9 37 Khai báo cấu trúc bảng băm: #define NULLKEY –1 #define M 100 struct node { int key; //khoa cua nut tren bang bam }; struct node hashtable[M]; //Khai bao bang bam co M nut Cài đặt bảng băm dùng phương pháp dò tuyến tính: 13 2.4.4. Bảng băm với phương pháp dò bậc hai Mô tả: - Bảng băm trong trường hợp này được cài đặt bằng danh sách kề có M phần tử, mỗi phần tử của bảng băm là một mẫu tin có một trường key để chứa khóa các phần tử. - Khi khởi động bảng băm thì tất cả trường key bị gán NULLKEY. Khi thêm phần tử có khóa key vào bảng băm, hàm băm h(key) sẽ xác định địa chỉ i trong khoảng từ 0 đến M-1. · Nếu chưa bị xung đột thì thêm phần tử mới vào địa chỉ i này. · Nếu bị xung đột thì hàm băm lại lần 1 h1 sẽ xét địa chỉ cách i là 12, nếu lại bị xung đột thì hàm băm lại lần 2 h2 sẽ xét địa chỉ cách i 22 ,… , quá trình cứ thế cho đến khi nào tìm được trống và thêm phần tử vào địa chỉ này. - Khi tìm kiếm một phần tử có khóa key trong bảng băm thì xét phần tử tại địa chỉ i=f(key), nếu chưa tìm thấy thì xét phần tử cách i 12, 22, …, quá trình cứ thế cho đến khi tìm được khóa (trường hợp tìm thấy) hoặc rơi vào địa chỉ trống (trường hợp không tìm thấy). - Hàm băm lại lần thứ i được biểu diễn bằng công thức sau: fi(key)=( f(key) + i2 ) % M với f(key) là hàm băm chính của bảng băm. Nếu đã dò đến cuối bảng thì trở về dò lại từ đầu bảng. Bảng băm minh họa có cấu trúc như sau: - Tập khóa K: tập số tự nhiên - Tập địa chỉ M: gồm 10 địa chỉ (M={0, 1, …, 9} - Hàm băm f(key) = key % 10. Khai báo cấu trúc bảng băm: #define NULLKEY –1 #define M 101 14 /* M la so nut co tren bang bam,du de chua cac nut nhap vao bang bam,chon M la so nguyen to */ //Khai bao nut cua bang bam struct node { int key; //Khoa cua nut tren bang bam }; //Khai bao bang bam co M nut struct node hashtable[M]; int N; Cài đặt bảng băm dùng phương pháp dò bậc hai: Hàm băm: Giả sử chúng ta chọn hàm băm dạng%: f(key)=key %10. int hashfunc(int key) { return(key% 10); } Phép toán initialize void initialize() { int i; for(i=0; i<M;i++) hashtable[i].key = NULLKEY; N=0; //so nut hien co khoi dong bang 0 } Phép toán empty: int empty() { return(N ==0 ?TRUE :FALSE); } 15 Phép toán full: int full() { return(N = = M-1 ?TRUE :FALSE); } Phép toán search: Tìm phần tử có khóa k trên bảng băm,nếu không tìm thấy hàm này trả về trị M, nếu tìm thấy hàm này trả về địa chỉ tìm thấy. int search(int k) { int i, d; i = hashfuns(k); d = 1; while(hashtable[i].key!=k&&hashtable[i].key !=NULLKEY) { //Bam lai (theo phuong phap bac hai) i = (i+d) % M; d = d+2; } hashtable[i].key =k; N = N+1; return(i); } 2.4.5. Bảng băm với phương pháp băm kép Mô tả: Phương pháp băm kép dùng hai hàm băm bất kì, ví dụ chọn hai hàm băm như sau: h1(key)= key %M. h2(key) =(M-2)-key %(M-2). 16 Bảng băm trong trường hợp này được cài đặt bằng danh sách kề có M phần tử, mỗi phần tử của bảng băm là một mẫu tin có một trường key để lưu khoá các phần tử. - Khi khởi động bảng băm, tất cả trường key được gán NULLKEY. - Khi thêm phần tử có khoá key vào bảng băm, thì i=h1(key) và j=h2(key) sẽ xác định địa chỉ i và j trong khoảng từ 0 đến M-1: · Nếu chưa bị xung đột thì thêm phần tử mới tại địa chỉ i này. · Nếu bị xung đột thì hàm băm lại lần 1 h1 sẽ xét địa chỉ mới i+j, nếu lại bị xung đột thì hàm băm lại lần 2 h2 sẽ xét địa chỉ i+2j, …, quá trình cứ thế cho đến khi nào tìm được địa chỉ trống và thêm phần tử vào địa chi này. - Khi tìm kiếm một phần tử có khoá key trong bảng băm, hàm băm i=h1(key) và j=h2(key) sẽ xác định địa chỉ i và j trong khoảng từ 0 đến M-1. Xét phần tử tại địa chỉ i, nếu chưa tìm thấy thì xét tiếp phần tử i+j, i+2j, …, quá trình cứ thế cho đến khi nào tìm được khoá (trường hợp tìm thấy) hoặc bị rơi vào địa chỉ trống (trường hợp không tìm thấy). Bảng băm dùng hai hàm băm khác nhau, hàm băm lại của phương pháp băm kép được tính theo hai giá trị: i (kết quả hàm băm thứ nhất) và j (kết qủa hàm băm thứ hai) theo một công thức bất kì. Nếu đã dò đến cuối bảng thì trở về dò lại từ đầu bảng. Bảng băm minh họa có cấu trúc như sau: - Tập khóa K: tập số tự nhiên - Tập địa chỉ M: gồm 11 địa chỉ (M={0, 1, …, 10} - Chọn hàm băm f1(key)=key % 11 và f2(key)=9-key %9. Khai báo #define NULLKEY –1 #define M 101 /*M la so nut co tren bang bam,du de chua cac nut nhap vao bang bam,chon M la so nguyen to */ struct node { int key;//khoa cua nut tren bang bam }; struct node hashtable[M]; //khai bao bang bam co M nut Bài 4:CÂY, CÂY NHỊ PHÂN, CÂY NHỊ PHÂN TÌM KIẾM 1. Cấu trúc cây 1.1. Định nghĩa 1: Cây là một tập hợp T các phần tử (nút trên cây) trong đó có 1 nút đặc biệt T0 được gọi là gốc, các nút còn khác được chia thành những tập rời nhau T1, T2 , ... , Tn theo quan hệ phân cấp trong đó Ti cũng là một cây. Nút ở cấp i sẽ quản lý một số nút ở cấp i+1. Quan hệ này người ta còn gọi là quan hệ cha-con. 1.2. Một số khái niệm cơ bản - Bậc của một nút: là số cây con của nút đó . - Bậc của một cây: là bậc lớn nhất của các nút trong cây. Cây có bậc n thì gọi là cây n-phân. - Nút gốc: nút không có nút cha. - Nút lá: nút có bậc bằng 0 . - Nút nhánh: nút có bậc khác 0 và không phải là gốc . - Mức của một nút: Mức (T0 ) = 1. Gọi T1, T2, T3, ... , Tn là các cây con của T0 Mức (T1) = Mức (T2) = ... = Mức (Tn) = Mức (T0) + 1. - Độ dài đường đi từ gốc đến nút x: là số nhánh cần đi qua kể từ gốc đến x. - Chiều cao h của cây: mức lớn nhất của các nút lá. 1.3. Một số ví dụ về đối tượng các cấu trúc dạng cây - Sơ đồ tổ chức của một doanh nghiệp - Sơ đồ tổ chức cây thư mục 1 2. CÂY NHỊ PHÂN 2.1 Định nghĩa Cây nhị phân là cây mà mỗi nút có tối đa 2 cây con Cây nhị phân có thể ứng dụng trong nhiều bài toán thông dụng. Ví dụ dưới đây cho ta hình ảnh của một biểu thức toán học: 2 2.2. Một số tính chất của cây nhị phân: - Số nút ở mức I  2I-1. - Số nút ở mức lá  2h-1, với h là chiều cao của cây. - Chiều cao của cây h  log2N (N - số nút trên trong cây). 2.3. Biểu diễn cây nhị phân T Cây nhị phân là một cấu trúc bao gồm các phần tử (nút) được kết nối với nhau theo quan hệ “cha-con” với mỗi cha có tối đa 2 con. Để biểu diễn cây nhị phân ta chọn phương pháp cấp phát liên kết. Ứng với một nút, ta dùng một biến động lưu trữ các thông tin: + Thông tin lưu trữ tại nút. + Địa chỉ nút gốc của cây con trái trong bộ nhớ. + Địa chỉ nút gốc của cây con phải trong bộ nhớ. Khai báo như sau: typedef struct tagTNODE { Data Key;//Data là kiểu dữ liệu ứng với thông tin lưu tại nút struct tagNODE *pLeft, *pRight; 3 }TNODE; typedef TNODE *TREE; 2.4. Các thao tác trên cây nhị phân Thăm các nút trên cây theo thứ tự trước (Node-Left-Right) void NLR(TREE Root) { if (Root != NULL) { ; //Xử lý tương ứng theo nhu cầu NLR(Root->pLeft); NLR(Root->pRight); } } Thăm các nút trên cây theo thứ tự giữa (Left- Node-Right) void LNR(TREE Root) { if (Root != NULL) { LNR(Root->Left); ; //Xử lý tương ứng theo nhu cầu LNR(Root->Right); } } Thăm các nút trên cây theo thứ tự sau (Left-Right-Node) void LRN(TREE Root) { 4 if (Root != NULL) { LRN(Root->Left); LRN(Root->Right); ; //Xử lý tương ứng theo nhu cầu } } Ứng dụng phương pháp này trong việc tính tổng kích thước của thư mục. Ứng dụng tính toán giá trị của biểu thức. (3 + 1)3/(9 – 5 + 2) – (3(7 – 4) + 6) = –13 5 2.5. Biểu diễn cây tổng quát bằng cây nhị phân Nhược điểm của các cấu trúc cây tổng quát là bậc của các nút trên cây có thể rất khác nhau  việc biểu diễn gặp nhiều khó khăn và lãng phí. Hơn nữa, việc xây dựng các thao tác trên cây tổng quát phức tạp hơn trên cây nhị phân nhiều. Vì vậy, nếu không quá cần thiết phải sử dụng cây tổng quát, người ta sẽ biến đổi cây tổng quát thành cây nhị phân. Ta có thể biến đổi một cây bất kỳ thành một cây nhị phân theo qui tắc sau: - Giữ nút con trái nhất làm con trái. - Các nút con còn lại biển đổi thành nút con phải. VD: Giả sử có cây tổng quát như hình sau: Cây nhị phân tương ứng sẽ như sau: 2.6. Một cách biểu diễn cây nhị phân khác Đôi khi, trên cây nhị phân, người ta quan tâm đến cả quan hệ chiều cha con. Khi đó, cấu trúc cây nhị phân có thể định nghĩa lại như sau: 6 typedef struct tagTNode { DataType Key; struct tagTNode* pParent; struct tagTNode* pLeft; struct tagTNode* pRight; }TNODE; typedef TNODE *TREE; 3. CÂY NHỊ PHÂN TÌM KIẾM 3.1. Định nghĩa: Cây nhị phân tìm kiếm (CNPTK) là cây nhị phân trong đó tại mỗi nút, khóa của nút đang xét lớn hơn khóa của tất cả các nút thuộc cây con trái và nhỏ hơn khóa của tất cả các nút thuộc cây con phải. Dưới đây là một ví dụ về cây nhị phân tìm kiếm: Nhờ ràng buộc về khóa trên CNPTK, việc tìm kiếm trở nên có định hướng. Hơn nữa, do cấu trúc cây việc tìm kiếm trở nên nhanh đáng kể. Chi phí tìm kiếm trung bình chỉ khoảng log2N. 7 Trong thực tế, khi xét đến cây nhị phân chủ yếu người ta xét CNPTK. 3.2. Các thao tác trên cây 3.2.1. Thăm các nút trên cây 3.2.2. Tìm một phần tử x trong cây TToán: Dễ dàng thấy rằng số lần so sánh tối đa phải thực hiện để tìm phần tử X là bằng h, với h là chiều cao của cây. Ví dụ: Tìm phần tử 55 3.3.3. Thêm một phần tử x vào cây Việc thêm một phần tử X vào cây phải bảo đảm điều kiện ràng buộc của CNPTK. Ta có thể thêm vào nhiều vị trí khác nhau trên cây, nhưng nếu thêm vào một nút lá thì sẽ dễ nhất do ta có thể thực hiện quá trình tương tự thao tác tìm kiếm. Khi chấm dứt quá trình tìm kiếm ta sẽ tìm được vị trí cần thêm. 8 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: int insertNode(TREE &T, Data X) { if(T) { if(T->Key == X) return 0; //đã có if(T->Key > X) return insertNode(T->pLeft, X); else return insertNode(T->pRight, X); } T = new TNode; if(T == NULL) return -1; //thiếu bộ nhớ T->Key = X; T->pLeft =T->pRight = NULL; return 1; //thêm vào thành công } 2.4. Hủy một phần tử có khóa x Việc hủy một phần tử X ra khỏi cây phải bảo đảm điều kiện ràng buộc của CNPTK. Có 3 trường hợp khi hủy nút X có thể xảy ra: X - nút lá. X - chỉ có 1 cây con (trái hoặc phải). X có đủ cả 2 cây con Trường hợp thứ nhất: chỉ đơn giản hủy X vì nó không móc nối đến phần tử nào khác. 9 Trường hợp thứ hai: trước khi hủy X ta móc nối cha của X với con duy nhất của nó. Trường hợp cuối cùng: ta không thể hủy trực tiếp do X có đủ 2 con  Ta sẽ hủy gián tiếp. Thay vì hủy X, ta sẽ tìm một phần tử thế mạng Y. Phần tử này có tối đa một con. Thông tin lưu tại Y sẽ được chuyển lên lưu tại X. Sau đó, nút bị hủy thật sự sẽ là Y giống như 2 trường hợp đầu. Vấn đề là phải chọn Y sao cho khi lưu Y vào vị trí của X, cây vẫn là CNPTK. 10 11 Có 2 p Phần tử lớn nhất (phải nhất) trên cây con trái. áng tôi sẽ chọn phần tử (phải nhất con trái làm phân tử thế mạng. VD: 2.5. Đ rên CNPTK đều có độ phức t ìm kiếm khi đó sẽ tương đương tìm kiếm nhị phân trên mảng tiến cấu trúc của CNPTK để đạt được chi phí cho các thao tác là log2(n). hần tử thỏa mãn yêu cầu: Phần tử nhỏ nhất (trái nhất) trên cây con phải. Việc chọn lựa phần tử nào là phần tử thế mạng hoàn toàn phụ thuộc vào ý thích của người lập trình. Ở đây, ch trên cây Cần hủy phần tử 18. ÁNH GIÁ Tất cả các thao tác Tìm kiếm, Thêm mới, Xóa t ạp trung bình O(h), với h là chiều cao của cây Trong trong trường hợp tốt nhất, CNPTK có n nút sẽ có độ cao h = log2(n). Chi phí t có thứ tự. Tuy nhiên, trong trường hợp xấu nhất, cây có thể bị suy biến thành 1 DSLK. Lúc đó các thao tác trên sẽ có độ phức tạp O(n). Vì vậy cần có cải CÂY CÂN BẰNG 1.CÂY NHỊ PHÂN CÂN BẰNG HOÀN TOÀN 1.1. Định nghĩa 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. 1.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, chi phí cân bằng lại cây cao vì phải thao tác trên toàn bộ cây. Đố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ă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. 1 2. CÂY NHỊ PHÂN CÂN BẰNG (AVL Tree) 2.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 nhị phân cân bằng : Dễ dàng thấy CCBHT là cây cân bằng. Điều ngược lại có thể không đúng không đúng. 2.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ằ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ừ 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, … 2.3. Chiều cao của cây AVL 2 Một vấn đề quan trọng, như đã đề cập đến ở phần trước, là ta phải khẳng định cây AVL có 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 có chiều cao h sẽ có 1 cây con AVL chiều cao h-1 và 1 cây con AVL 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) i =h/2 N(h)>2h/2 h < 2log2(N(h)) Như 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 3 2.4. Cấu trúc dữ liệu cho cây AVL Chỉ số cân bằng của một nút: 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ể nhận 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) Xét nút P, ta dùng các ký hiệu sau: P->balFactor = CSCB(P); Độ cao cây trái P ký hiệu là hleft Độ cao cây phải P ký hiệu là hright Để 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 4 { tor; //Chỉ số cân bằng struct tagAVLNode* pRight; VLNode; pedef AVLNode *AVLTree; ĩa một số hăng số sau: efine RH 1 //Cây con phải cao hơn 2.5. Đ cây thay đổi chiều cao các trường hợp mất cân bằng mới có khả năng xảy ra. , thêm, hủy với chi phí O (log2(n)) và bảo đảm không suy biến thành (n). 3. CÁC THAO TÁC CƠ BẢN TRÊN CÂY AVL n cây có thể làm câ char balFac Data key; struct tagAVLNode* pLeft; } A ty Để tiện cho việc trình bày, ta định ngh #define LH -1 //Cây con trái cao hơn #define EH -0 //Hai cây con bằng nhau #d ánh giá cây AVL Cây cân bằng là CTDL ổn định hơn CCBHT vì khi thêm, hủy làm Cây AVL với chiều cao được khống chế sẽ cho phép thực thi các thao tác tìm O Ta nhận thấy trường hợp thêm hay hủy một phần tử trê y tăng hay giảm chiều