Giáo trình cấu trúc dữ liệu và giải thuật_Chương 5: Cây nhiều nhánh tìm kiếm

Tham khảo tài liệu giáo trình cấu trúc dữ liệu và giải thuật_chương 5: cây nhiều nhánh tìm kiếm, công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
Giáo trình cấu trúc dữ liệu và giải thuật_Chương 5: Cây nhiều nhánh tìm kiếmChương 5: CÂY NHIỀU NHÁNH TÌM KIẾMCây nhị phân là cây bậc 2, mỗi nút của cây nhị phân có tối đa là hai nhánh cây con. Còncây nhiều nhánh là cây có bậc lớn hơn 2, mỗi nút trên cây nhiều nhánh thường cónhiều khoá và có nhiều hơn hai nhánh cây con.Cây nhiều nhánh có rất nhiều loại, trong chương này chúng ta chỉ nghiên cứu câynhiều nhánh tìm kiếm thông qua hai loại cây như sau: Cây nhiều nhánh tìm kiếm trênxuống (top-down multiway search tree) và cây B-Tree.1. GIỚI THIỆU CÂY NHIỀU NHÁNH1.1 Định nghĩa cây nhiều nhánhCây nhiều nhánh là một cấu trúc gồm một tập hữu hạn các nút cùng kiểu dữ liệu (tậpcác nút này có thể là tập rỗng), tập nút này được phân thành các tập con như sau: • Tập thứ nhất có một nút gọi là nút gốc. • Các tập con còn lại tự thân hình thành các cây nhiều nhánh, gọi là các nhánh cây con của nút gốc, các nhánh cây con này cũng có thể là cây rỗng.Người ta thường dùng đồ thị để biểu diễn các cây nhiều nhánh, mỗi nút của cây đượcminh hoạ bằng một vòng tròn, trong vòng tròn có ghi các khoá của nút.Các khái niệm trên cây nhị phân trong chương trước cũng được áp dụng cho cây nhiềunhánh như: bậc của cây, bậc của nút, đường đi …1.2 Định nghĩa cây nhiều nhánh tìm kiếmỞ chương trước, chúng ta đã nghiên cứu và cài đặt cây nhị phân tìm kiếm (BinarySearch Tree), cây nhiều nhánh tìm kiếm cũng giống như cây nhị phân tìm kiếm nhưngtổng quát hơn. Mỗi nút trên cây nhiều nhánh tìm kiếm có nhiều khoá và nhiều nhánhcây con, số khoá ít hơn số nhánh cây con là 1. Ví dụ nút có 3 khoá thì có 4 nhánh câycon, nút có 4 khoá thì có 5 nhánh cây con…Xét hình minh hoạ sau: 1Hình trên minh hoạ một nút trên cây nhiều nhánh tìm kiếm. Giả sử nút này có bậc m:nút có m – 1 khoá và có m nhánh cây con. Gọi: k0, k1, k2, …, km-2 là m – 1 khoá (theo thứ tự tăng dần của nút). s0, s1, s2, …, sm-1 là m nhánh cây con của nútNhánh cây con si gọi là nhánh cây con bên trái của khoá ki và nút gốc của nhánh cây consi gọi là nút con bên trái của khoá ki.Tương tự, nhánh cây con si còn được gọi là nhánh cây con bên phải của khoá k i-1 và nútgốc của nhánh cây con si gọi là nút con bên phải của khoá ki-1.Định nghĩa cây nhiều nhánh tìm kiếmCây nhiều nhánh tìm kiếm là cây nhiều nhánh mà ở mỗi nút của cây thoả mãn các tínhchất sau: • Tất cả các khoá trên nhánh cây con s0 đều nhỏ hơn hay bằng khoá k0. • Tất cả các khoá trên nhánh cây con si (1Khi thêm một khoá vào cây trên-xuống chúng ta phải tìm nút lá phù hợp để chèn khoámới vào nút lá này. Nếu nút lá chưa đầy thì ta chèn khoá vào, còn nếu nút lá này đã đầythì chúng ta phải cấp phát một nút lá mới để chứa khoá, nút lá mới này là con của nútlá cũ.Hình vẽ sau mô tả việc thêm 2 khoá 17 và 80 vào cây trên-xuống ở trên:2.2 Cài đặt cây trên - xuống2.2.1 Khai báo cấu trúcGọi ORDER là bậc của cây trên xuống.Gọi numtrees là số nhánh của cây con của một nút (numtrees struct node{ int numtrees;//so cay con cua mot nut int key[ORDER -1];//cac khoa cua mot node struct node *son[ORDER];//cac con tro chi den cac nut con cua mot node cha};typedef struct node *NODEPTR;NODEPTR ptree;2.2.2 Các tác vụ • Tác vụ makenode Tác vụ này dùng để tạo nút mới cho cây trên xuống. Nút mới tạo là nút có một khoá và hai nhánh cây con. Hàm makenode được gọi khi thêm khoá vào cây trên xuống trong các trường hợp: cây đang bị rỗng và chúng ta thêm khoá đầu tiên vào cây đó hoặc là nút lá để chèn khoá vào đã đầy, chúng ta phải cấp phát một nút lá mới để chứa khoá, nút lá mới là con của nút lá trước. NODEPTR makenode(int k){ int i; NODEPTR p; p=getnode(); p->numtrees=2; p->key[0]=k; //nut moi chua co cac nut con for(i=0;ison[i]=NULL; return p; } • Tác vụ tìm kiếm một khoá trên nút Trả về vị trí nhỏ nhất của khoá trong nút p bắt đầu lớn hơn hay bằng k. Trường hợp k lớn hơn tất cả các khoá trong nút p thì trả về vị trí p->numtrees – 1. int nodesearch(NODEPTR p, int k){ int i; for(i=0;inumtrees -1&&p->key[i] - Hàm search() trả về con trỏ p chỉ nút có chứa khoá k. - Biến position trả về vị trí của khoá k có trong nút p. Nếu không có khoá k trên cây, lúc này p=NULL và q (nút cha của p) chỉ nút lá có thể thêm khoá k vào. - Biến found trả về giá trị FALSE - Hàm search trat về con trỏ q chỉ vị trí của nút lá có thể thêm khoá k. - Biến Position trả về vị trí có thể chèn khoá k vào nút lá q. NODEPTR search(int k, int *pposition, int *pfound){ int i; NODEPTR p,q; q=NULL; p=ptree; while(p!=NULL){ i=nodesearch(p,k); if(i< p->numtrees-1 && k==p->key[i]){//found *pfound=TRUE; *pposition=i; return p; } q=p; p=p->son[i]; } *pfound=FALSE; *pposition=i; return q; }• Tác vụ duyệt cây void traverse(NODEPTR proot){ int i, nt; if(proot==NULL) return; else{ nt=proot->numtrees; for(i=0;ison[i]); printf(%8d,proot->key[i]); } ...