Chương 4: Cây nhị phân

Giảng viên : Nguyễn Minh Thành Email : thanhnm.itc@itc.edu.vn Chương 4 : CÂY NHỊ PHÂN Nội Dung I. Cấu Trúc Cây 1. Khái việm và ví dụ 2. Định nghĩa 3. Các tính chất 4. Các thuật ngữ liên quan II. Cây Nhị Phân 1. Định nghĩa 2. Cách thức lưu trữ cây III. Cây Nhị Phân Tìm Kiếm 1. Ý nghĩa 2. Định nghĩa 3. Ví dụ 4. Cài đặt 2 I. Cấu Trúc Cây 1. Khái việm và ví dụ 2. Định nghĩa 3. Các tính chất 4. Các thuật ngữ liên quan 3 I.1 Khái Niệm và Ví Dụ 4  Ví dụ 1: bài toán đưa thư  Trên thế giới hơn có ~ 10 tỉ người  Thành, khoa CNTT, CĐ CNTT, TpHCM, Việt Nam.  Cách tìm ra “Thành” nhanh nhất ?  Sử dụng mảng ?  Sứ dụng danh sách liên kết (linked list) ? I.1 Khái Niệm và Ví Dụ 5  Ví dụ 1: bài toán đưa thư I.1 Khái Niệm và Ví Dụ 6  Cây là một cấu trúc dữ liệu quan trọng để biểu diễn và lưu trữ dữ liệu trong bộ nhớ chính và mang tính “kế thừa”  Tính kế thừa :  Các node con phải liên quan đến node cha  Các cây mang tính kế thừa :  Cây gia phả  Cây phân cấp các loài (sinh vật) I.2 Định Nghĩa 7  Một cây (Tree) là  Một tập hợp các phần tử, gọi là các node p1,p2,…,pN  Nếu N=0, cây gọi là cây rỗng (NULL)  Nếu N>0 :  Tồn tại duy nhất một node pk duy nhất gọi là gốc cây  Các nút còn lại được chia thành m tập không giao nhau : T1, T2, … TM  Mỗi Ti cây con của cây I.2 Định Nghĩa 8 I.2 Định Nghĩa 9 I.2 Định Nghĩa 10 I.3 Các Tính Chất Của Cây 11  Nút gốc không có nút cha  Mỗi nút khác chỉ có 1 nút cha  Mỗi nút có thể có nhiều nút con  Không có chu trình I.4 Các Thuật Ngữ Liên Quan 12  Node : là 1 phần tử trong cây. Mỗi node chứa 1 dữ liệu bất kỳ  Nhánh : là đoạn nối giữa 2 nút  Node cha  Node con  Nút anh em : là những node có cùng nút cha  Bậc của 1 node pi : là số node con của pi  Tìm bậc của các node trên cây T trong ví dụ trên ?  Node gốc : node không có node cha  Node lá (node ngoài) : node có bậc = 0 (không có node con)  Node trong (node nhánh) : là node có node con và node cha  Cây con  Trong cây T có bao nhiêu cây con ? I.4 Các Thuật Ngữ Liên Quan 13  Bậc của cây : là bậc lớn nhất của các node trong cây  Bậc () = max { bậc(pi) / pi  }  Tìm bậc của cây T ?  Đường đi (path) giữa node pi và pj : là dảy các nút liên tiếp từ pi đến pj sao cho giữa 2 node kề nhau đều có nhánh.  Độ dài đường đi từ node pi và pj : là số nhánh cần đi qua từ pi đến pj . I.4 Các Thuật Ngữ Liên Quan 14  Mức (level)  Mức (p)=0 nếu p là gốc  Mức (p) = mức (cha(p)) +1 nếu p không phải gốc  Chiều cao của cây (hT): đường đi dài nhất từ node gốc đến node lá  hT = max { path (gốc, pi) / pi là node lá  }  Tính chiều cao của cây T trong ví dụ trên I.4 Các Thuật Ngữ Liên Quan 15  Mức (level)  Mức (p)=0 nếu p là gốc  Mức (p) = mức (cha(p)) +1 nếu p không phải gốc  Chiều cao của cây (hT): đường đi dài nhất từ node gốc đến node lá  hT = max { path (gốc, pi) / pi là node lá  }  Tính chiều cao của cây T trong ví dụ trên II. Cây Nhị Phân 16 1. Định nghĩa 2. Cách thức lưu trữ cây II.1 Định Nghĩa 17  Cây Nhị Phân là cây có bậc = 2 Bậc của các nút trong <=2 Bậc của nút lá = 0 II.1 Định Nghĩa 18  Độ cao của cây nhị phân có N node:  hT(max) = N  hT(min) = [log2N] + 1 II.2 Lưu Trữ Cây 19  Có 2 cách tổ chức cây nhị phân : Lưu trữ bằng mảng Lưu trữ bằng con trỏ cấu trúc  Chi tiết ở phần Cây Nhị Phân Tìm Kiếm III. Cây Nhị Phân Tìm Kiếm 20 1. Định nghĩa 2. Ý nghĩa 3. Cài đặt III.1 Định Nghĩa 21  Cây nhị phân tìm kiếm Là một cây nhị phân Giá trị của một node bất kỳ luôn lớn hơn giá trị của tất cả các node bên trái và nhỏ hơn giá trị tất cả các node bên phải. Giá trị nhỏ nhất nằm ở node trái nhất của cây Giá trị lớn nhất nằm ở node phải nhất của cây III.2 Ý nghĩa 22  Cây nhị phân tìm kiếm giúp tận dụng hết điểm mạnh của mảng và danh sách kết trong việc biểu lưu trữ cây. III.3 Cài đặt 23  Có 2 cách tổ chức cây nhị phân : Lưu trữ bằng mảng Lưu trữ bằng con trỏ cấu trúc  Sử dụng con trỏ cấu trúc (DSLK) là tối ưu hơn III.3 Cài đặt 24  Định nghĩa dữ liệu Typedef struct TNODE { Data Key; Struct TNODE pLeft, pRight; } *TREE; III.3 Cài đặt 25  Các lưu ý khi cài đặt  Bước 1 : Khai báo kiểu dữ liệu biểu diễn cây  Bước 2 : Xây dựng hàm đưa dữ liệu (nhập) vào cây  Bước 3 : Xây dựng các thao tác duyệt, tìm kiếm, huỷ…  Các lưu ý khác  Trước khi tạo node mới phải xin cấp phát vùng nhớ  Trước khi tạo cây mới phải khởi tạo cây rỗng  Trước khi kết thúc chương trình phải huỷ cây (giải phóng bộ nhớ). III.3 Cài đặt 26  Cấu trúc chương trình III.3 Cài đặt 27  Thao tác Khởi tạo cây rỗng void BSTCreate(TREE &t) { t = NULL; }  Thao tác Kiểm tra cây rỗng int BSTIsEmpty(const TREE &t) { if (t==NULL) return 1; return 0; } III.3 Cài đặt 28  Thao tác Xây dựng cây • Nếu node cần thêm < node đang xét thì thêm về bên trái • Nếu node cần thêm < node đang xét thì thêm về bên phải III.3 Cài đặt 29  Thao tác Xây dựng cây III.3 Cài đặt 30  Thao tác Duyệt Cây  Có 3 cách duyệt cây  Duyệt gốc trước (Pre-order) : NLR  Duyệt gốc giữa (In-Order) : LNR  Duyệt gốc sau (Post-Order) : LRN III.3 Cài đặt 31  Thao tác Duyệt Cây  Thứ tự duyệt NLR 7 3 1 6 4 36 15 40 III.3 Cài đặt 32  Thao tác Duyệt Cây  Thứ tự duyệt LNR 1 3 4 6 7 15 36 40 III.3 Cài đặt 33  Thao tác Duyệt Cây  Thứ tự duyệt LRN 1 4 6 3 15 40 36 7 III.3 Cài đặt 34  Thao tác Duyệt Cây  Thứ tự duyệt NLR void NLR(TREE T) { if (T==NULL) return; CoutKey;//”xử lý gốc” NLR(T->pLeft); NLR(T->pRight); } III.3 Cài đặt 35  Thao tác Duyệt Cây  Thứ tự duyệt LNR void NLR(TREE T) { if (T==NULL) return; NLR(T->pLeft); CoutKey;//”xử lý gốc” NLR(T->pRight); } III.3 Cài đặt 36  Thao tác Duyệt Cây  Thứ tự duyệt LRN void NLR(TREE T) { if (T==NULL) return; NLR(T->pLeft); NLR(T->pRight); CoutKey;//”xử lý gốc” } III.3 Cài đặt 37  Xây dựng lại cây sau khi được in ra từ các thao tác Duyệt Cây  Xây dựng cây từ phép duyệt NLR  Chọn giá trị đầu làm node gốc  Lần lượt đưa các giá trị còn lại từ trái sang phải vào cây theo nguyên tắc xây dựng cây.  Xây dựng cây từ phép duyệt LRN  Chọn giá trị cuối cùng làm gốc  Lần lượt đưa các giá trị còn lại từ phải sang trái vào cây theo nguyên tắc xây dựng cây.  III.3 Cài đặt 38  Xây dựng lại cây sau khi được in ra từ các thao tác Duyệt Cây  Xây dựng cây từ phép duyệt LNR  Gọi r là số phần tử của cây  Giá trị ở giữa được tính như sau : m = r div 2  Chọn giá trị ở vị trí m làm gốc  Lần lượt đưa các giá trị bắt đầu từ vị trí m-1 lùi về bên trái theo quy tắc xây dựng cây  Lần lượt đưa các giá trị bắt đầu từ vị trí m+1 lùi về bên trái theo quy tắc xây dựng cây III.3 Cài đặt 39  Các thao tác tìm thông tin của cây  Số node lá  Số node có 1 cây con  Số node có 1 cây con phải  Số node có 1 cây con trái  Số node có 2 cây con  Độ cao của cây  Số node của cây  Các node trên cùng mức  Độ dài đường đi từ gốc đến x III.3 Cài đặt 40  Các thao tác tìm thông tin của cây  Số node lá III.3 Cài đặt 41  Các thao tác tìm thông tin của cây  Số node có 1 cây con III.3 Cài đặt 42  Các thao tác tìm thông tin của cây  Tính độ cao của cây III.3 Cài đặt 43  Các thao tác tìm thông tin của cây  Số node cùng mức k III.3 Cài đặt 44  Các thao tác tìm thông tin của cây  Số node có 1 cây con phải  Số node có 1 cây con trái  Số node có 2 cây con  Số node của cây  Độ dài đường đi từ gốc đến x  Sinh viên tự làm III.3 Cài đặt 45  Các thao tác tìm thông tin của cây  Số node có 1 cây con phải III.3 Cài đặt 46  Các thao tác tìm kiếm  Tìm x  Tìm min  Tim min của cây con phải  Tìm max  Tìm max của cây con trái III.3 Cài đặt 47  Các thao tác tìm kiếm  Tìm x : trả về con trỏ trỏ đến vùng nhớ chứa x III.3 Cài đặt 48  Các thao tác tìm kiếm  Tìm min : phần tử nhỏ nhất chính là phần tử trái nhất của cây III.3 Cài đặt 49  Các thao tác tìm kiếm  Tìm min của cây con phải  Tìm max  Tìm max của cây con trái  Sinh viên tự làm III.3 Cài đặt 50  Thao tác Xoá node  Các node bị xoá có thể :  Node lá  Node có 1 cây con  Node có 2 cây con III.3 Cài đặt 51  Thao tác Xoá node  Xoá node lá  Xoá vùng nhớ của node  Con trỏ của node cha sẽ trỏ đến NULL  Xoá node có 1 cây con  Đổi vị trí node cần huỷ và node con  Xoá node cần huỷ  Xoá node có 2 cây con  Tìm phần tử thế mạng cho node cần xoá (phần tử phải nhất bên trái, hoặc trái nhất bên phải)  Đổi key của node thế mạng với cần xoá  Xoá node thế mạng III.3 Cài đặt 52  Thao tác Xoá node III.3 Cài đặt 53  Thao tác Xoá node III.3 Cài đặt 54  Thao tác Huỷ toàn bộ cây Sinh viên tự làm Hỏi Đáp 55