Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 6 - Trần Minh Thái (2016)

Bài giảng "Cấu trúc dữ liệu và giải thuật - Chương 6: Cây nhiều nhánh B-Tree" trình bày khái niệm về cây nhiều nhánh B-Tree, đặc điểm và cấu trúc, chèn phần tử vào cây, xóa phần tử khỏi cây. 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: Chương 6 - Trần Minh Thái (2016) Chương 6. Cây nhiều nhánh: B-TreeTrầnMinhTháiEmail:minhthai@huflit.edu.vnWebsite:www.minhthai.edu.vn 1Nội dung1. Khái niệm2. Đặc điểm và cấu trúc3. Chèn phần tử vào cây4. Xóa phần tử khỏi cây 2Cây nhiều nhánh: M-Phân• Mỗi node có tối đa M node con• Một cây M-Phân đầy đủ có chiều cao logMN• Ví dụ cây 5-Phân đầy đủ: 3Khái niệm• Thứ tự các khóa tương tự cây nhị phân tìm kiếm• Mỗi node có M-1 khóa• M càng lớn cây càng thấp• Giữ tính chất cân bằng trên cây tìm kiếm M-Phân: B-Cây 4B-TreeB-Tree bậc M là cây M-Phân tìm kiếm có các tính chất:• Mỗi node (ngoại trừ gốc) có ít nhất M/2 node con• Node gốc (nếu không phải nút lá) có ít nhất 2 nút con• Mọi nút lá đều nằm cùng một mức• Các khóa và cây con được sắp xếp theo cây tìm kiếm 5B-Tree• Hạn chế số thao tác đọc mỗi lần tìm kiếm trên cây• Thích hợp cho việc tìm kiếm trên bộ nhớ ngoài• Chiều cao cây = logMN, tăng M chiều cao cây giảm rất nhanh 6Chèn node vào câyÝ tưởng: Tìm vị trí khóa có thể thêm vào cây. Việctìm kiếm sẽ kết thúc tại một lá. Khóa mới sẽ đượcthêm vào nút lá:1. Nếu chưa đầy  Việc thêm hoàn tất2. Nếu đầy  Phân đôi nút lá cần thêm: • Tách nút lá ra làm hai nút cạnh nhau trong cùng một mức • Chuyển phần tử giữa lên nút chaQuá trình phân đôi các nút có thể được lan truyềnngược về gốc và kết thúc khi có một nút cha nào đócần được thêm một khóa từ dưới lên 7mà chưa đầy Ví dụ • Cho B-tree bậc 5 rỗng • Hãy xây dựng B-Tree theo thứ tự từ trái sang phải cho dãy số sau:1 1 8 2 2 5 1 2 1 7 5 1 4 6 3 2 2 5 5 45 2 5 4 8 7 2 6 8 8 6 9 3 5 81 1 8 2 2 5 1 2 1 7 5 1 4 6 3 2 2 5 5 45 2 5 4 8 7 2 6 8 8 6 9 3 5 Chèn1 1 Chèn12 1 12 Chèn8 1 8 12 Chèn2 1 2 8 12 91 1 8 2 2 5 1 2 1 7 5 1 4 6 3 2 2 5 5 45 2 5 4 8 7 2 6 8 8 6 9 3 5 Donútgốcđãđầy(4phầntử) Chèn25vàonútgốc sẽtáchnútgốcthành2nútvàđưakhóa ởgiữalêntrên tạothànhnútgốcmới 1 2 8 12 25 8 1 2 12 25 101 1 8 2 2 5 1 2 1 7 5 1 4 6 3 2 2 5 5 45 2 5 4 8 7 2 6 8 8 6 9 3 5 Thêm5 8 1 2 5 12 25 Thêm14 8 1 2 5 12 14 25 111 1 8 2 2 5 1 2 1 7 5 1 4 6 3 2 2 5 5 45 2 5 4 8 7 2 6 8 8 6 9 3 5 Thêm28 8 1 2 5 12 14 25 28 Thêm17,donútlábênphảiđãđầynênphânđôivàđưa nútgiữalêntrênnútcha(nútgốc) 8 17 1 2 5 12 14 25 28 121 1 8 2 2 5 1 2 1 7 5 1 4 6 3 2 2 5 5 45 2 5 4 8 7 2 6 8 8 6 9 3 5 Thêm7 8 17 1 2 5 7 12 14 25 28 Thêm52 8 17 1 2 5 7 12 14 25 28 52 131 1 8 2 2 5 1 2 1 7 5 1 4 6 3 2 2 5 5 45 2 5 4 8 7 2 6 8 8 6 9 3 5 Thêm16 8 17 1 2 5 7 12 14 16 25 28 52 Thêm48 8 171 2 5 7 12 14 16 25 28 48 52 141 1 8 2 2 5 1 2 1 7 5 1 4 6 3 2 2 5 5 45 2 5 4 8 7 2 6 8 8 6 9 3 5 Thêm68,donútlábênphảiđãđầynênphânđôinútlá vàđưanútgiữalênnútcha(nútgốc) 8 17 481 2 5 7 12 14 16 25 28 52 68 Thêm3,donútlábêntráiđãđầynênphânđôinútlávà đưanútgiữalênnútcha(nútgốc) 3 8 17 481 2 5 7 12 14 16 25 28 52 68 151 1 8 2 2 5 1 2 1 7 5 1 4 6 3 2 2 5 5 45 2 5 4 8 7 2 6 8 8 6 9 3 5 Thêm26 3 8 17 48 1 2 5 7 12 14 16 25 2 28 52 68 6 Thêm29 3 8 17 481 2 5 7 12 14 16 2 2 2 2 52 68 ...