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ần Minh Thái

Chương 6. Cây nhiều nhánh: B-TreeTrần Minh TháiEmail: minhthai@huflit.edu.vnWebsite: www.minhthai.edu.vn1Nội dungKhái niệmĐặc điểm và cấu trúcChèn phần tử vào câyXóa phần tử khỏi cây2Cây nhiều nhánh: M-PhânMỗi node có tối đa M node conMột cây M-Phân đầy đủ có chiều cao logMN Ví dụ cây 5-Phân đầy đủ:3Khái niệmThứ 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ây4B-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 conNode gốc (nếu không phải nút lá) có ít nhất 2 nút conMọi nút lá đều nằm cùng một mứcCác khóa và cây con được sắp xếp theo cây tìm kiếm5B-TreeHạn chế số thao tác đọc mỗi lần tìm kiếm trên câyThích hợp cho việc tìm kiếm trên bộ nhớ ngoàiChiều cao cây = logMN, tăng M chiều cao cây giảm rất nhanh6Chèn node vào câyÝ tưởng: Tìm vị trí khóa có thể thêm vào cây. Việc tìm kiếm sẽ kết thúc tại một lá. Khóa mới sẽ được thêm vào nút lá:Nếu chưa đầy  Việc thêm hoàn tấtNế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ứcChuyể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ền ngượ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 mà chưa đầy7Ví dụCho B-tree bậc 5 rỗngHãy xây dựng B-Tree theo thứ tự từ trái sang phải cho dãy số sau:8112822551428177521648683262953554519Chèn 1 112Chèn 12 1812Chèn 8 12812Chèn 2 1128225514281775216486832629535545101128225514281775216486832629535545Do nút gốc đã đầy (4 phần tử)  Chèn 25 vào nút gốc sẽ tách nút gốc thành 2 nút và đưa khóa ở giữa lên trên tạo thành nút gốc mới12812258122512111128225514281775216486832629535545Thêm 581225125Thêm 148121425125121128225514281775216486832629535545Thêm 28812142528125Thêm 17, do nút lá bên phải đã đầy nên phân đôi và đưa nút giữa lên trên nút cha (nút gốc)81712141252528131128225514281775216486832629535545Thêm 7817121412572528Thêm 5281712141257252852141128225514281775216486832629535545Thêm 168171214161257252852Thêm 48817121416125725284852151128225514281775216486832629535545Thêm 68, do nút lá bên phải đã đầy nên phân đôi nút lá và đưa nút giữa lên nút cha (nút gốc)81748121416125725285268Thêm 3, do nút lá bên trái đã đầy nên phân đôi nút lá và đưa nút giữa lên nút cha (nút gốc)381748121416572528526812161128225514281775216486832629535545Thêm 2638174812141657252628526812Thêm 293817481214165725262829526812171128225514281775216486832629535545Thêm 53381748121416572526282952536812Thêm 5538174812141657252628295253556812181128225514281775216486832629535545Thêm 45, do nút lá thứ 3 đầy nên phân đôi và đưa nút giữa lên trên nút cha, nút cha cũng đầy nên phân đôi tiếp nút cha và đưa nút giữa lên trên, tạo thành nút gốc mới2848121416572526525355681238294517Bài tập áp dụngCho dãy số: 1, 3, 9, 2, 4, 10, 25, 30, 11, 40, 21, 8, 7, 6, 19, 5, 30, 12, 15, 16Hãy trình bày từng bước vẽ cây B-Tree bậc 419Xóa khóa trên câyNếu khóa cần xóa nằm ở nút lá  XóaNếu khóa cần xóa không nằm ở nút lá  Xóa khóa cần xóa, đưa khóa có giá trị gần nhất từ nút lá lên thay thế cho khóa đã xóa20Xóa khóa trên câyNếu trong trường hợp (1) hay (2), nút lá còn lại quá ít khóa thì xét các nút anh em kế cận nút đang xét:Nếu một trong các nút anh em kế cận nút đang xét có số lượng khóa nhiều hơn số lượng tối thiểu, đưa một khóa của nút anh em lên nút cha và đưa khóa ở nút cha xuống nút lá có khóa quá ítNếu tất cả các nút anh em kế cận nút đang xét đều có số lượng khóa vừa đủ số lượng tối thiểu, chọn một nút anh em kế cận và hợp nhất nút anh em này với nút lá có khóa quá ít. Nếu nút cha trở nên thiếu khóa, lặp lại quá trình này21Xóa 68222848121416572526525355681238294517Nút lá28481214165725265253551238294517Vẫn còn đủ lượng theo yêu cầuTrường hợp 1Xóa 82328481214165725265253551238294517Không phải nút lá2848525265253551237294517Trường hợp 2121416Còn quá ít khóaXóa 8242848525265253551237294517Trường hợp 4121416Hợp nhất2848252652535512357294517121416Còn quá ít khóaXóa 825Trường hợp 4Hợp nhất28482526525355123572945171214167172848252652535512352945121416Bài tập áp dụngHãy trình bày từng bước lần lượt xóa các node 1, 2, 3, 4, 5, 1126Cho B-Tree bậc 3