Bài giảng Cấu trúc dữ liệu: Chương 5 - Trường ĐH Mở TP. HCM

Chia sẻ: Cuchoami2510 | Ngày: | Loại File: PDF | Số trang:23

Thêm vào BST

Báo xấu

25
lượt xem 5
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: Chương 5 B-Tree, cung cấp cho người học những kiến thức như: B-Cây; Thêm phần tử vào B-Cây; Xóa phần tử khỏi B-Cây. 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: Chương 5 - Trường ĐH Mở TP. HCM

11/07/2020 11/07/2020 1 1  B-Cây  Thêm phần tử vào B-Cây  Xóa phần tử khỏi B-Cây 11/07/2020 2 2 1
11/07/2020 Giới thiệu ❖B-cây (B-Trees) xử lý tốt trên đĩa hoặc các thiết bị lưu trữ ngoài 11/07/2020 3 3 B-Cây ❖Mỗi node có thể chứa n khóa, các khóa này sắp xếp theo thứ tự tăng dần ❖Mỗi node trong có n + 1 con trỏ trỏ tới các node con ❖Node lá không có node con và có cùng mức 22 32 24 28 37 4242 9 12 17 20 11/07/2020 4 4 2
11/07/2020 B-Cây ❖Một B-Cây bậc t (t ≥ 2) ➢Mỗi node (trừ node gốc) có tối thiểu t khóa và có tối thiểu t con ➢Mỗi node có tối đa 2t khóa, vì vậy một node trong có tối đa 2t + 1 con ➢Một node gọi là đầy khi chứa 2t khóa ❖Ví dụ ➢B-tree đơn giản nhất có t = 2, mỗi node trong có hoặc 3, 4, 5 con 11/07/2020 5 5 Thêm phần tử ❖Thao tác thêm phần tử (Insert): thêm 1 khóa x vào cây ➢Thêm v vào 1 nút lá ➢Nếu nút lá đầy: tách nút lá ra làm đôi, và chuyển phần tử giữa lên nút cha 11/07/2020 6 6 3
11/07/2020 Thêm phần tử ❖Thêm các phần tử sau vào B-cây bậc t = 2 22; 42 12 32 17; 37 9 28 20 24; 7; 44 15 48 29 10 34; 40 26 47 27; ➢Thêm 22 22 ➢Thêm 42 22 42 ➢Thêm 12 12 22 42 ➢Thêm 12 12 22 32 42 11/07/2020 7 7 Thêm phần tử ❖22; 42 12 32 17; 37 9 28 20 24; 7; 44 15 48 29 1012 34; 40 26 47 27; 22 32 42 ➢Thêm 12 ➢Thêm 17 thì trang này bị đầy (một trang B-cây cấp 2 chứa tối đa bốn phần tử). • Dãy các khóa là 12 17 22 32 42 nên trang này bị tách ra thành hai trang: • Một trang chứa khóa (12 17) và một trang chứa khóa (32 42), và cấp phát thêm trang mới chứ khóa 22 (trang cha). 11/07/2020 8 8 4
11/07/2020 Thêm phần tử ❖22; 42 12 32 17; 37 9 28 20 24; 7; 44 15 48 29 10 34; 40 26 47 27; ➢Thêm 17 12 1212 17 1722 2237 32 3242 42 42 11/07/2020 9 9 Thêm phần tử ❖22; 42 12 32 17; 37 9 28 20 24; 7; 44 1 5 48 29 10 34; 40 26 47 27; ➢Thêm 37 9 28 20 24 22 32 3237 4242 12 17 Phạm 37 9 28 20 24 11/07/2020 10 10 5
11/07/2020 Thêm phần tử ❖22; 42 12 32 17; 37 9 28 20 24; 7; 44 15 48 29 10 34; 40 26 47 27; ❖Kết quả thêm 24 22 32 24 28 37 4242 9 12 17 20 11/07/2020 11 11 Thêm phần tử ❖22; 42 12 32 17; 37 9 28 20 24; 7; 44 15 48 29 10 34; 40 26 47 27; ❖Thêm 7 -> Phạm 22 32 24 28 37 4242 7 9 12 17 20 12 22 32 11/07/2020 17 20 24 28 37 4242 12 7 9 12 6
11/07/2020 Thêm phần tử ❖22; 42 12 32 17; 37 9 28 20 24; 7; 44 1 5 48 29 10 34; 40 26 47 27; ❖Thêm : 44 15 48 29 10 12 22 32 17 20 24 28 37 4242 7 9 12 22 32 11/07/2020 37 4242 44 48 13 7 9 10 15 17 20 24 28 29 13 Thêm phần tử ❖22; 42 12 32 17; 37 9 28 20 24; 7; 44 15 48 29 10 34; 40 26 47 27; ❖Thêm: 34 12 22 32 7 9 10 15 17 20 24 28 29 34 37 4242 44 48 12 22 32 42 7 9 10 15 17 20 24 28 29 34 37 44 48 11/07/2020 14 14 7
11/07/2020 Thêm phần tử ❖22; 42 12 32 17; 37 9 28 20 24; 7; 44 15 48 29 10 34; 40 26 47 27; ❖Thêm: 40 26 47 12 22 32 42 7 9 10 15 17 20 24 28 29 34 37 44 48 12 22 32 42 7 11/07/2020 9 10 15 17 20 24 26 28 29 34 37 40 44 4715 48 15 Thêm phần tử ❖22; 42 12 32 17; 37 9 28 20 24; 7; 44 15 48 29 10 34; 40 26 47 27; ❖Thêm: 27 -> Phạm 12 22 32 42 7 9 10 15 17 20 24 26 28 29 34 37 40 44 47 48 27 11/07/2020 16 16 8
11/07/2020 Thêm phần tử ❖22; 42 12 32 17; 37 9 28 20 24; 7; 44 15 48 29 10 34; 40 26 47 27; ❖Thêm: 27 -> Phạm 12 22 32 42 7 9 10 15 17 20 24 26 28 29 34 37 40 44 47 48 27 27 12 22 32 42 11/07/2020 17 7 9 10 15 17 20 24 26 28 29 34 37 40 44 47 48 17 Xóa phần tử ❖Xóa thứ tự các nút có khóa: 27 47 26;40 34; 10 29 48 15 44; 7 24 20 28; 9 37 17; ở cây dưới 27 12 22 32 42 7 9 10 15 17 20 24 26 28 29 34 37 40 44 47 48 11/07/2020 18 18 9
11/07/2020 Xóa phần tử ❖27 47 26;40 34; 10 29 48 15 44; 7 24 20 28; 9 37 17; 27 12 22 32 42 7 9 10 15 17 20 24 26 28 29 34 37 40 44 47 48 ❖Xóa 27 ta mang 26 lên thay thế, khi ấy nút 24,26 chỉ còn lại 24 (phạm). Khi đó ta mượn trang trái 1 khóa đẩy lên cha, và lấy 22 của cha xuống 11/07/2020 19 19 Xóa phần tử ❖27 47 26;40 34; 10 29 48 15 44; 7 24 20 28; 9 37 17; 26 12 20 32 42 7 9 10 15 17 22 24 28 29 34 37 40 44 47 48 11/07/2020 20 20 10
11/07/2020 Xóa phần tử ❖27 47 26;40 34; 10 29 48 15 44; 7 24 20 28; 9 37 17; 26 12 20 32 42 7 9 10 15 17 22 24 28 29 34 37 40 44 47 48 11/07/2020 21 21 Xóa phần tử ❖27 47 26;40 34; 10 29 48 15 44; 7 24 20 28; 9 37 17; 26 12 20 32 42 7 9 10 15 17 22 24 28 29 34 37 40 44 48 11/07/2020 22 22 11
11/07/2020 Xóa phần tử ❖27 47 26;40 34; 10 29 48 15 44; 7 24 20 28; 9 37 17; 26 12 20 32 42 7 9 10 15 17 22 24 28 29 34 37 40 44 48 ❖Xóa 26, lấy 24 lên thay thế, lúc đó nút 22,24 còn 1 khóa (phạm). Khi này ta nhập 15,17,20,22 thành 1 nút. Và khi ấy cha chi còn 12 (phạm). Ta tiếp tục gộp 12,26,32,42 lại 11/07/2020 23 23 Xóa phần tử ❖27 47 26;40 34; 10 29 48 15 44; 7 24 20 28; 9 37 17; 12 24 32 42 7 9 10 15 17 20 22 28 29 34 37 40 44 48 11/07/2020 24 24 12
11/07/2020 Xóa phần tử ❖27 47 26;40 34; 10 29 48 15 44; 7 24 20 28; 9 37 17; 12 24 32 42 7 9 10 15 17 20 22 28 29 34 37 40 44 48 12 24 32 42 7 9 11/07/202010 15 17 20 22 28 29 34 37 44 48 25 25 Xóa phần tử ❖27 47 26;40 34; 10 29 48 15 44; 7 24 20 28; 9 37 17; 12 24 32 42 7 9 10 15 17 20 22 28 29 34 37 44 48 ❖Xóa khóa 34: Nút 34, 37 chỉ còn lại 34. Gộp 37,42,44,48 thành 1 trang 11/07/2020 26 26 13
11/07/2020 Xóa phần tử ❖27 47 26;40 34; 10 29 48 15 44; 7 24 20 28; 9 37 17; 12 24 32 7 9 10 15 17 20 22 28 29 37 42 44 48 11/07/2020 27 27 Xóa phần tử ❖27 47 26;40 34; 10 29 48 15 44; 7 24 20 28; 9 37 17; 12 24 32 7 9 10 15 17 20 22 28 29 37 42 44 48 12 24 32 7 9 15 17 20 22 28 29 37 42 44 48 11/07/2020 28 28 14
11/07/2020 Xóa phần tử ❖27 47 26;40 34; 10 29 48 15 44; 7 24 20 28; 9 37 17; 12 24 32 7 9 15 17 20 22 28 29 37 42 44 48 ❖Xóa 29, trang 28,29 còn lại 28 (phạm), mượn 37 trang phải. Do đó 37 lên cha, 32 xuống thế 29 11/07/2020 29 29 Xóa phần tử ❖27 47 26;40 34; 10 29 48 15 44; 7 24 20 28; 9 37 17; 12 24 32 7 9 15 17 20 22 28 29 37 42 44 48 12 24 37 7 9 15 17 20 22 28 32 42 44 48 11/07/2020 30 30 15
11/07/2020 Xóa phần tử ❖27 47 26;40 34; 10 29 48 15 44; 7 24 20 28; 9 37 17; 12 24 37 7 9 15 17 20 22 28 32 42 44 48 12 24 37 7 9 15 17 20 22 28 32 42 44 11/07/2020 31 31 Xóa phần tử ❖27 47 26;40 34; 10 29 48 15 44; 7 24 20 28; 9 37 17; 12 24 37 7 9 15 17 20 22 28 32 42 44 12 24 37 7 9 17 20 22 28 32 42 44 11/07/2020 32 32 16
11/07/2020 Xóa phần tử ❖27 47 26;40 34; 10 29 48 15 44; 7 24 20 28; 9 37 17; 12 24 37 7 9 17 20 22 28 32 42 44 ❖Xóa 44 (phạm), gộp trang phải lại 11/07/2020 33 33 Xóa phần tử ❖27 47 26;40 34; 10 29 48 15 44; 7 24 20 28; 9 37 17; 12 24 37 7 9 17 20 22 28 32 42 44 12 24 7 9 17 20 22 28 32 37 42 11/07/2020 34 34 17
11/07/2020 Xóa phần tử ❖27 47 26;40 34; 10 29 48 15 44; 7 24 20 28; 9 37 17; 12 24 ❖Xóa 7, mượn trang bên phải 7 9 17 20 22 28 32 37 42 17 24 9 12 20 22 28 32 37 42 11/07/2020 35 35 Xóa phần tử ❖27 47 26;40 34; 10 29 48 15 44; 7 24 20 28; 9 37 17; 17 24 9 12 20 22 28 32 37 42 ❖Xóa 24, ta đem khóa 22 lên thay thế. khi đó trang 20,22 chỉ còn 20 (phạm), Nên ta phải đem khóa 22 trở lại trang 20,22. Mang 28 lên thếm 11/07/2020 36 36 18
11/07/2020 Xóa phần tử ❖27 47 26;40 34; 10 29 48 15 44; 7 24 20 28; 9 37 17; 17 24 9 12 20 22 28 32 37 42 17 28 9 12 20 22 32 37 42 11/07/2020 37 37 Xóa phần tử ❖27 47 26;40 34; 10 29 48 15 44; 7 24 20 28; 9 37 17; 17 28 9 12 20 22 32 37 42 ❖Xóa 20: mượn trang phải 1 phần tử. Tức mang 32 lên cha, 28 xuống nút có 1 khóa là 22 11/07/2020 38 38 19
11/07/2020 Xóa phần tử ❖27 47 26;40 34; 10 29 48 15 44; 7 24 20 28; 9 37 17; 17 28 9 12 20 22 32 37 42 17 32 9 12 22 28 37 42 11/07/2020 39 39 Xóa phần tử ❖27 47 26;40 34; 10 29 48 15 44; 7 24 20 28; 9 37 17; 17 32 9 12 22 28 37 42 17 9 12 22 32 37 42 11/07/2020 40 40 20