tailieunhanh - Bài giảng Cấu trúc dữ liệu và giải thuật 1: Chương 8

Bài giảng Cấu trúc dữ liệu và giải thuật 1: Chương 8 trình bày các nội dung chính sau: Cây B-tree, cây nhiều nhánh tìm kiếm, thêm node mới, tách node, . Mời các bạn cùng tham khảo để nắm nội dung chi tiết. | CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 1 CÂY B-TREE Giới thiệu Cây là một cách tiếp cận hoàn chỉnh để tổ chức dữ liệu trong bộ nhớ. Vậy cây có thể làm việc tốt với hệ thống tập tin hay không CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 B-tree là cấu trúc dữ liệu phù hợp cho việc lưu trữ ngoài do và đưa ra năm 1972. 2 Cây nhiều nhánh tìm kiếm Một cây nhiều nhánh bậc m là cây mà mỗi node có nhiều nhất m cây con. Gọi count count Cây nhiều nhánh tìm kiếm Tất cả các node con của cây con có gốc tại node con thứ i thì có các giá trị khoá lớn hơn khoá key i-1 và nhỏ hơn khoá key i 0CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 Cây nhiều nhánh tìm kiếm Cây nhiều nhánh tìm kiếm Multiway Search Trees bậc 5 5 Định nghĩa B-tree Định nghĩa Một B-tree bậc m là cây nhiều nhánh tìm kiếm thỏa các điều kiện sau i Tất cả các node lá cùng mức. ii Tất cả các node trung gian trừ node gốc có nhiều nhất m cây con và có ít nhất m 2 cây con khác rỗng . iii Mỗi node hoặc là node lá hoặc có k 1 cây con k là CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 số khoá của node này . iv Node gốc có nhiều nhất m cây con hoặc có thể có 2 cây con Node gốc có 1 khoá và không phải là node lá hoặc không chứa cây con nào node gốc có 1 khoá và cũng là node lá . 6 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 Định nghĩa B-tree B-tree bậc 5 có 3 mức 7 Khai báo Khai báo typedef struct int count số khoá của node hiện hành int Key Order-1 mảng lưu trữ các khoá của node CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 int Branch Order các con trỏ chỉ đến các cây con Order-Bậc của cây BNode Kiểu dữ liệu của node typedef struct BNode pBNode con trỏ node pBNode Root con tro node goc 8 Các Phép toán C0 K1 C2 K2 Cm-1 Km Cm Các trường hợp xảy ra khi tìm 1 node X. Nếu X không tìm thấy sẽ có 3 trường hợp sau xảy ra Ki lt X lt Ki 1. Tiếp tục tìm kiếm trân cây con Ci CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 Km lt X. Tiếp tục tìm kiếm trên Cm X lt K1. tiếp tục tìm kiếm trên C0 Quá trình này tiếp tục cho đến khi node được tìm thấy. Nếu đã đi đến node lá mà vẫn không tìm thấy khoá việc