Bài giảng Cấu trúc dữliệu và giải thuật: B-Cây - Đậu Ngọc Hà Dương

Bài giảng Cấu trúc dữliệu và giải thuật: B-Cây - Đậu Ngọc Hà Dương có nội dung trình bày về cây tìm kiếm m-nhánh, B-cây, các thao tác trên B-cây, cây B+, tập tin chỉ mục IDX trong FoxPro,... Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữliệu và giải thuật: B-Cây - Đậu Ngọc Hà DươngCấutrúcdữliệuvàgiảithuật B-Cây Giảng viên: Đậu Ngọc Hà Dương Nội dung trình bày2 Cấutrúcdữliệuvàgiảithuật–HCMUS20103 Cây tìm kiếm m-nhánh  mwaysearchtree  mwaytree Cấutrúcdữliệuvàgiảithuật–HCMUS2010 Định nghĩa4  Câytìmkiếmmnhánhlàcâycótínhchất:  Có tối đa m-1 khóa trong mỗi node (v1, v2,.., vk) (k m-1).  Các giá trị khóa trong node được tổ chức có thứ tự (v1 < v2 < ... < vk).  Một node có k khóa thì sẽ có k + 1 cây con (các cây con có thể rỗng).  Các cây con đặt giữa hai giá trị khóa.  Hai cây con nằm ở hai đầu của dãy khóa  Mỗi khóa sẽ có cây con trái và cây con phải. Cấutrúcdữliệuvàgiảithuật–HCMUS2010  Các giá trị của cây con trái sẽ nhỏ hơn giá trị của khóa. Ví dụ5 16 25 10 14 20 33 42 11 28 49 Câytìmkiếm3nhánh Cấutrúcdữliệuvàgiảithuật–HCMUS2010 Thao tác trên cây6  Tìmkiếm  Thêmphầntử  Xóaphầntử Cấutrúcdữliệuvàgiảithuật–HCMUS2010 Tìm kiếm7  Tổngquáthóatừtrườnghợpcâynhịphântìm kiếm  X là giá trị cần tìm  Nếu X < v1 thì tìm X bên nhánh trái của v1.  Ngược lại, nếu X > vk thì tìm X bên nhánh phải của vk.  Nếu X = vi thì thông báo tìm thấy.  Nếu vi < X < vi+1 thì tìm X tại cây con nằm giữa vi và vi+1. Cấutrúcdữliệuvàgiảithuật–HCMUS2010 Thêm phần tử8  Tổngquáthóatừtrườnghợpcâynhịphântìm kiếm  X là giá trị cần thêm vào cây.  Duyệt cây tìm X trên cây.  Nếu X đã tồn tại trên cây thì không thêm.  Nếu X chưa tồn tại (tìm thấy node rỗng) thì  Nếu node cha (của node rỗng tìm thấy) còn có thể thêm X vào thì thêm X vào node cha.  Ngược lại, tạo node mới và thêm X vào node đó. Cấutrúcdữliệuvàgiảithuật–HCMUS2010 Thêm phần tử9 16 25 10 14 20 33 42 11 13 28 49 Thêmvàogiátrị13 Cấutrúcdữliệuvàgiảithuật–HCMUS2010 Thêm phần tử10 16 25 10 14 20 33 42 11 28 37 49 Thêmvàogiátrị37 Cấutrúcdữliệuvàgiảithuật–HCMUS2010 Xóa phần tử11  Tươngtựcâynhịphântìmkiếm  Tìm vị trí của phần tử X cần xóa.  Nếu X nằm giữa hai cây con rỗng thì xóa X.  Nếu X có cây con, thay thế X bằng:  Phần tử lớn nhất bên cây con trái của X hoặc  Phần tử nhỏ nhất bên cây con phải của X Cấutrúcdữliệuvàgiảithuật–HCMUS2010 Xóa phần tử12 16 25 10 14 20 33 42 11 28 49 Xóagiátrị20 Cấutrúcdữliệuvàgiảithuật–HCMUS2010 Xóa phần tử13 16 25 10 14 33 42 11 28 49 Xóagiátrị25 Cấutrúcdữliệuvàgiảithuật–HCMUS2010 Xóa phần tử14 16 28 10 14 33 42 11 25 49 Xóagiátrị25 Cấutrúcdữliệuvàgiảithuật–HCMUS2010 Xóa phần tử15 16 28 10 14 33 42 11 49 Xóagiátrị25 Cấutrúcdữliệuvàgiảithuật–HCMUS201016 B-Cây  Btree Cấutrúcdữliệuvàgiảithuật–HCMUS2010 Định nghĩa17  Bcâybậcmlà1câytìmkiếmmnhánh(m>2) thỏa:  Nút gốc có ít nhất 1 khóa ...