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

Chia sẻ: Bạch Đăng Kỳ | Ngày: | Loại File: PPTX | Số trang:81

Thêm vào BST

Báo xấu

12
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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ấu trúc dữ liệu và giải thuật B-Cây Giảng viên: Đậu Ngọc Hà Dương
Nội dung trình bày 2 Cấu trúc dữ liệu và giải thuật – HCMUS 2010
3 Cây tìm kiếm m-nhánh  mway search tree  mway tree Cấu trúc dữ liệu và giải thuật – HCMUS 2010
Định nghĩa 4  Cây tìm kiếm mnhánh là cây có tính chấ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ấu trúc dữ liệu và giải thuật – HCMUS 2010  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ây tìm kiếm 3nhánh Cấu trúc dữ liệu và giải thuật – HCMUS 2010
Thao tác trên cây 6  Tìm kiếm  Thêm phần tử  Xóa phần tử Cấu trúc dữ liệu và giải thuật – HCMUS 2010
Tìm kiếm 7  Tổng quát hóa từ trường hợp cây nhị phân tì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ấu trúc dữ liệu và giải thuật – HCMUS 2010
Thêm phần tử 8  Tổng quát hóa từ trường hợp cây nhị phân tì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ấu trúc dữ liệu và giải thuật – HCMUS 2010
Thêm phần tử 9 16 25 10 14 20 33 42 11 13 28 49 Thêm vào giá trị 13 Cấu trúc dữ liệu và giải thuật – HCMUS 2010
Thêm phần tử 10 16 25 10 14 20 33 42 11 28 37 49 Thêm vào giá trị 37 Cấu trúc dữ liệu và giải thuật – HCMUS 2010
Xóa phần tử 11  Tương tự cây nhị phân tìm kiế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ấu trúc dữ liệu và giải thuật – HCMUS 2010
Xóa phần tử 12 16 25 10 14 20 33 42 11 28 49 Xóa giá trị 20 Cấu trúc dữ liệu và giải thuật – HCMUS 2010
Xóa phần tử 13 16 25 10 14 33 42 11 28 49 Xóa giá trị 25 Cấu trúc dữ liệu và giải thuật – HCMUS 2010
Xóa phần tử 14 16 28 10 14 33 42 11 25 49 Xóa giá trị 25 Cấu trúc dữ liệu và giải thuật – HCMUS 2010
Xóa phần tử 15 16 28 10 14 33 42 11 49 Xóa giá trị 25 Cấu trúc dữ liệu và giải thuật – HCMUS 2010
16 B-Cây  Btree Cấu trúc dữ liệu và giải thuật – HCMUS 2010
Định nghĩa 17  Bcây bậc m là 1 cây tìm kiếm mnhánh (m>2) thỏa:  Nút gốc có ít nhất 1 khóa  Tất cả các cây con rỗng ở cùng một mức.  Tất cả các node (trừ node gốc) có ít nhất m/2 cây con (có ít nhất m/2 -1 khóa).  Giá trị m thường là lẻ. Cấu trúc dữ liệu và giải thuật – HCMUS 2010
Ví dụ 18 26 Một Bcây có bậc là 5 6 12 42 51 62 1 2 4 7 8 13 15 18 25 27 29 45 46 48 53 55 60 64 70 90 Cấu trúc dữ liệu và giải thuật – HCMUS 2010
Ví dụ 19 26 Có phải là Bcây? 6 12 42 51 62 1 2 4 13 15 18 25 27 29 45 46 48 53 55 60 64 70 90 Cấu trúc dữ liệu và giải thuật – HCMUS 2010
Tính chất 20  Gọi độ cao của cây: h h 1  Số khóa tối đa của Bcây bậc m: m 1 Cấu trúc dữ liệu và giải thuật – HCMUS 2010