tailieunhanh - Bài giảng Phân tích thiết kế và giải thuật - Chương 5: Cây 2 – 3 – 4

Bài giảng "Phân tích thiết kế và giải thuật - Chương 5: Cây 2 – 3 – 4" cung cấp cho người học các kiến thức: Giới thiệu về cây 2-3-4, tổ chức, tìm kiếm, thêm vào. Đây là một tài liệu hữu ích dành cho các bạn sinh viên và những ai quan tâm dùng làm tài liệu học tập và nghiên cứu. | Bài giảng Phân tích thiết kế và giải thuật - Chương 5 Cây 2 3 4 CÂY 2 3 4 1 1 Cây 2-3-4 Giới thiệu về cây 2-3-4 Tổ chức Tìm kiếm Thêm vào 2 Giới thiệu Đối với cây nhị phân mỗi nút chỉ có một mục dữ liệu và có thể có hai nút con. Nếu chúng ta cho phép một nút có nhiều mục dữ liệu và nhiều nút con thì kết quả là ta được cây nhiều nhánh Giới thiệu về cây 2-3-4 Cây 2-3-4 là cây nhiều nhánh mà mỗi nút của nó có thể có đến bốn nút con và ba mục dữ liệu. Các số 2 3 và 4 trong cụm từ cây 2-3-4 có ý nghĩa là khả năng có bao nhiêu liên kết đến các node con có thể có được trong một node cho trước. 4 Giới thiệu về cây 2-3-4 tt Đối với các node không phải là lá có 3 cách sắp xếp sau Một node với một mục dữ liệu thì luôn luôn có 2 con. Một node với hai mục dữ liệu thì luôn luôn có 3 con. Một node với ba mục dữ liệu thì luôn luôn có 4 con. Nói cách khác nếu số con là L và số mục dữ liệu là D thì L D 1 5 50 75 95 6 Giới thiệu về cây 2-3-4 tt Một node lá thì không có node con nhưng có thể chứa 1 2 hoặc 3 mục dữ liệu. Trong cây 2-3-4 không tồn tại node chỉ có liên kết đơn. Một node với 1 mục dữ liệu luôn luôn phải có 2 liên kết trừ khi nó là node lá node không có liên kết nào . 7 Tổ chức cây 2-3-4 Các mục dữ liệu trong mỗi node được sắp xếp theo thứ tự tăng dần từ trái sang phải sắp xếp từ thấp đến cao . Trong cây tìm kiếm nhị phân NL Tổ chức cây 2-3-4 Trong cây 2-3-4 thì nguyên tắc cũng giống như cây tìm kiếm nhị phân nhưng có thêm một số điểm sau Tất cả các node con của cây con có gốc tại node con thứ 0 thì có các giá trị khoá nhỏ hơn khoá 0. Tất cả các node con của cây con có gốc tại node con thứ 1 thì có các giá trị khoá lớn hơn khoá 0 và nhỏ hơn khoá 1. Tất cả các node con của cây con có gốc tại node con thứ 2 thì có các giá trị khoá lớn hơn khoá 1 và nhỏ hơn khoá 2. Tất cả các node con của cây con có gốc tại node con thứ 3 thì có các giá trị khoá lớn hơn khoá 2. 9 Tìm kiếm Thao tác tìm kiếm trong cây 2-3-4 tương tự như thủ tục tìm kiếm trong cây nhị tìm kiếm bắt .