Xem mẫu
Chương 6. Cây nhiều nhánh: B-Tree
Trần Minh Thái
Email: minhthai@huflit.edu.vn Website: www.minhthai.edu.vn
1
Nội dung
1. Khái niệm
2. Đặc điểm và cấu trúc
3. Chèn phần tử vào cây
4. Xóa phần tử khỏi cây
2
Câ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 đủ:
3
Khá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
4
B-Tree
B-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
5
...
- tailieumienphi.vn
nguon tai.lieu . vn