Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 8b: Cây - Văn Chí Nam

©FIT-HCMUS 1 Giảng viên: Văn Chí Nam – Nguyễn Thị Hồng Nhung – Đặng Nguyễn Đức Tiến Cấu trúc dữ liệu và giải thuật – HCMUS 2015 2 Các thao tác trên B-cây B-Cây Cây tìm kiếm m-nhánh CuuDuongThanCong.com https://fb.com/tailieudientucntt ©FIT-HCMUS 2 m-way search tree m-way tree Cấu trúc dữ liệu và giải thuật – HCMUS 2015 3 Cấu trúc dữ liệu và giải thuật – HCMUS 2015 4  Cây tìm kiếm m-nhá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ác giá trị của cây con trái sẽ nhỏ hơn giá trị của khóa.  Các giá trị của cây con phải sẽ lớn hơn giá trị của khóa. CuuDuongThanCong.com https://fb.com/tailieudientucntt ©FIT-HCMUS 3 Cấu trúc dữ liệu và giải thuật – HCMUS 2015 5 16 25 10 14 20 33 42 11 4928 Cây tìm kiếm 3-nhánh Cấu trúc dữ liệu và giải thuật – HCMUS 2015 6  Tìm kiếm  Thêm phần tử  Xóa phần tử CuuDuongThanCong.com https://fb.com/tailieudientucntt ©FIT-HCMUS 4 Cấu trúc dữ liệu và giải thuật – HCMUS 2015 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 2015 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 đó. CuuDuongThanCong.com https://fb.com/tailieudientucntt ©FIT-HCMUS 5 Cấu trúc dữ liệu và giải thuật – HCMUS 2015 9 16 25 10 14 20 33 42 11 4928 Thêm vào giá trị 13 13 Cấu trúc dữ liệu và giải thuật – HCMUS 2015 10 16 25 10 14 20 33 42 11 4928 Thêm vào giá trị 37 37 CuuDuongThanCong.com https://fb.com/tailieudientucntt ©FIT-HCMUS 6 Cấu trúc dữ liệu và giải thuật – HCMUS 2015 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 2015 12 16 25 10 14 20 33 42 11 4928 Xóa giá trị 20 CuuDuongThanCong.com https://fb.com/tailieudientucntt ©FIT-HCMUS 7 Cấu trúc dữ liệu và giải thuật – HCMUS 2015 13 16 25 10 14 33 42 11 4928 Xóa giá trị 25 Cấu trúc dữ liệu và giải thuật – HCMUS 2015 14 16 28 10 14 33 42 11 4925 Xóa giá trị 25 CuuDuongThanCong.com https://fb.com/tailieudientucntt ©FIT-HCMUS 8 Cấu trúc dữ liệu và giải thuật – HCMUS 2015 15 16 28 10 14 33 42 11 49 Xóa giá trị 25 B-tree Cấu trúc dữ liệu và giải thuật – HCMUS 2015 16 CuuDuongThanCong.com https://fb.com/tailieudientucntt ©FIT-HCMUS 9 Cấu trúc dữ liệu và giải thuật – HCMUS 2015 17  B-cây bậc m là 1 cây tìm kiếm m-nhá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 2015 18 51 6242 6 12 26 55 60 7064 9045 1 2 4 7 8 13 15 18 25 27 29 46 48 53 Một B-cây có bậc là 5 CuuDuongThanCong.com https://fb.com/tailieudientucntt ©FIT-HCMUS 10 Cấu trúc dữ liệu và giải thuật – HCMUS 2015 19 51 6242 6 12 26 55 60 7064 9045 1 2 4 13 15 18 25 27 29 46 48 53 Có phải là B-cây? Cấu trúc dữ liệu và giải thuật – HCMUS 2015 20  Tìm kiếm  Thực hiện tương tự trên cây tìm kiếm m-nhánh.  Thêm phần tử  Xóa phần tử CuuDuongThanCong.com https://fb.com/tailieudientucntt ©FIT-HCMUS 11 Cấu trúc dữ liệu và giải thuật – HCMUS 2015 21  Thêm phần tử vào node lá.  Nếu node lá bị tràn thì  Tách thành 2 node mới.  Khóa chính giữa được đưa lên node cha.  Thực hiện tương tự nếu node cha bị tràn.  Nếu node gốc bị tràn thì tạo một node gốc mới (có 1 khóa duy nhất là khóa chính giữa của node cũ) Cấu trúc dữ liệu và giải thuật – HCMUS 2015 22  Tạo B-cây bậc 5 gồm các phần tử theo thứ tự sau:  1, 12, 8, 2, 25, 5, 14, 28, 17 CuuDuongThanCong.com https://fb.com/tailieudientucntt ©FIT-HCMUS 12 Cấu trúc dữ liệu và giải thuật – HCMUS 2015 23 1 12 8 2 25 5 14 28 17 1 128 122 8 12 Thêm 1 Thêm 12 Thêm 8 Thêm 2 Cấu trúc dữ liệu và giải thuật – HCMUS 2015 24 1 12 8 2 25 5 14 28 17 1 25128 12 Thêm 25 2 1 2 8 12 25 CuuDuongThanCong.com https://fb.com/tailieudientucntt ©FIT-HCMUS 13 Cấu trúc dữ liệu và giải thuật – HCMUS 2015 25 1 12 8 2 25 5 14 28 17 Thêm 5, 14, 28 1 2 8 12 145 25 28 Cấu trúc dữ liệu và giải thuật – HCMUS 2015 26 1 12 8 2 25 5 14 28 17 Thêm 17 1 2 8 12 145 17 25 28 8 17 12 14 25 281 2 5 CuuDuongThanCong.com https://fb.com/tailieudientucntt ©FIT-HCMUS 14 Cấu trúc dữ liệu và giải thuật – HCMUS 2015 27  Thực hiện tương tự cây tìm kiếm m-nhánh.  Xét hai trường hợp:  Khóa thuộc node lá  Khóa thuộc node trong Cấu trúc dữ liệu và giải thuật – HCMUS 2015 28  Khóa thuộc node lá:  Xóa khóa khỏi node chứa khóa.  Sau khi xóa, nếu node chứa khóa mới xóa có số khóa không đủ (ít hơn m/2-1 khóa) thì:  Mượn khóa từ node bên cạnh (Node bên cạnh dư khóa).  Nhập khóa với node bên cạnh cùng với khóa cha (Node bên cạnh KHÔNG dư khóa). CuuDuongThanCong.com https://fb.com/tailieudientucntt ©FIT-HCMUS 15 Cấu trúc dữ liệu và giải thuật – HCMUS 2015 29  Khóa thuộc node trong:  Khóa bị xóa có các node bên nhánh con trái và nhánh con phải có số khóa tối thiểu (m/2-1 khóa): nhập khóa của 2 node con.  Ngược lại: tìm phần tử thế mạng và thực hiện cân bằng lại cây như trường hợp xóa khóa thuộc node lá. Cấu trúc dữ liệu và giải thuật – HCMUS 2015 30  Cho B-cây bậc 5: 12 29 52 2 7 9 15 22 56 69 7231 43 Xóa khóa 2 CuuDuongThanCong.com https://fb.com/tailieudientucntt ©FIT-HCMUS 16 Cấu trúc dữ liệu và giải thuật – HCMUS 2015 31  Cho B-cây bậc 5: 12 29 52 7 9 15 22 56 69 7231 43 Cấu trúc dữ liệu và giải thuật – HCMUS 2015 32  Cho B-cây bậc 5: 12 29 52 7 9 15 22 56 69 7231 43 Xóa khóa 52 CuuDuongThanCong.com https://fb.com/tailieudientucntt ©FIT-HCMUS 17 Cấu trúc dữ liệu và giải thuật – HCMUS 2015 33  Cho B-cây bậc 5: 12 29 56 7 9 15 22 52 69 7231 43 Xóa khóa 52. Thay thế bằng 56 Cấu trúc dữ liệu và giải thuật – HCMUS 2015 34  Cho B-cây bậc 5: 12 29 56 7 9 15 22 69 7231 43 CuuDuongThanCong.com https://fb.com/tailieudientucntt ©FIT-HCMUS 18 Cấu trúc dữ liệu và giải thuật – HCMUS 2015 35  Cho B-cây bậc 5: 12 29 56 7 9 15 22 69 7231 43 Xóa khóa 72 Cấu trúc dữ liệu và giải thuật – HCMUS 2015 36  Cho B-cây bậc 5: 12 29 56 7 9 15 22 6931 43 Ít khóa -> Nhập node CuuDuongThanCong.com https://fb.com/tailieudientucntt ©FIT-HCMUS 19 Cấu trúc dữ liệu và giải thuật – HCMUS 2015 37  Cho B-cây bậc 5: 12 29 7 9 15 22 695631 43 Cấu trúc dữ liệu và giải thuật – HCMUS 2015 38  Cho B-cây bậc 5: 12 29 7 9 15 22 695631 43 Xóa khóa 22 CuuDuongThanCong.com https://fb.com/tailieudientucntt ©FIT-HCMUS 20 Cấu trúc dữ liệu và giải thuật – HCMUS 2015 39  Cho B-cây bậc 5: 12 29 7 9 15 695631 43 Mượn khóa Cấu trúc dữ liệu và giải thuật – HCMUS 2015 40  Cho B-cây bậc 5: 12 31 7 9 15 29 695643 CuuDuongThanCong.com https://fb.com/tailieudientucntt ©FIT-HCMUS 21 Cấu trúc dữ liệu và giải thuật – HCMUS 2015 41  Cho B-cây bậc 5: Xóa khóa 8 Nhập 2 node con của 8 lại 1 2 25 26 29 45 52 53 28 48 16 5 7 12 14 3 8 Cấu trúc dữ liệu và giải thuật – HCMUS 2015 42  Cho B-cây bậc 5: Nhận xét? Node 3 bị thiếu khóa 1 2 25 26 29 45 52 53 28 48 16 14125 7 3 CuuDuongThanCong.com https://fb.com/tailieudientucntt ©FIT-HCMUS 22 Cấu trúc dữ liệu và giải thuật – HCMUS 2015 43  Cho B-cây bậc 5: tạo node mới → hạ độ cao cây 1 2 25 26 29 45 52 5314125 7 48283 16 Cấu trúc dữ liệu và giải thuật – HCMUS 2015 44  Cho B-cây bậc 5 như dưới đây:  Xóa 28 rồi xóa 48 8 17 12 14 262 5 16 28 527 531 3 2925 55 6845 48 CuuDuongThanCong.com https://fb.com/tailieudientucntt ©FIT-HCMUS 23 Cấu trúc dữ liệu và giải thuật – HCMUS 2015 45  B-cây là dạng cây cân bằng, phù hợp với việc lưu trữ trên đĩa.  B-cây tiêu tốn số phép truy xuất đĩa tối thiểu cho các thao tác.  Có thể quản lý số phần tử rất lớn. Cấu trúc dữ liệu và giải thuật – HCMUS 2015 46  Xây dựng cấu trúc chỉ mục trong các hệ quản trị cơ sở dữ liệu CuuDuongThanCong.com https://fb.com/tailieudientucntt ©FIT-HCMUS 24 Cấu trúc dữ liệu và giải thuật – HCMUS 2015 47 CuuDuongThanCong.com https://fb.com/tailieudientucntt