tailieunhanh - Cấu trúc dữ liệu : Cây 2-3-4 part 1

1. Giới thiệu về cây 2-3-4 Chúng ta sẽ xem xét các đặc tính của cây 2-3-4 và mối quan hệ khá gần gũi giữa cây 23-4 và cây đỏ-đen. Hình 1 trình bày một cây 2-3-4 đơn giản. Mỗi node có thể lưu trữ 1, 2 hoặc 3 mục dữ liệu. | BÀI 7 CÂY 2-3-4 1. Giới thiệu về cây 2-3-4 Chúng ta sẽ xem xét các đặc tính của cây 2-3-4 và mối quan hệ khá gần gũi giữa cây 23-4 và cây đỏ-đen. Hình 1 trình bày một cây 2-3-4 đơn giản. Mỗi node có thể lưu trữ 1 2 hoặc 3 mục dữ liệu. Hình 1 cây 2-3-4 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. Đối với các node không phải là lá có thể 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. Như vậy một node không phải là lá phải luôn luôn có số node con nhiều hơn 1 so với số mục dữ liệu của nó. Nói cách khác đối với mọi node với số con là k và số mục dữ liệu là d thì k d 1 1 4- node Hình 2. các trường hợp của cây 2-3-4 Với mọi node lá thì không có node con nhưng có thể chứa 1 2 hoặc 3 mục dữ liệu không có node rỗng. Một cây 2-3-4 có thể có đến 4 cây con nên được gọi là cây nhiều nhánh bậc 4. Trong cây 2-3-4 mỗi node có ít nhất là 2 liên kết trừ node lá node không có liên kết nào . Hình 2 trình bày các trường hợp của cây 2-3-4. Một node với 2 liên kết gọi là một 2-node một node với 3 liên kết gọi là một 3-node và một node với 4 liên kết gọi là một 4-node nhưng ở đây không có node là 1-node. 2. 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 tất cả node của cây con bên trái có khoá nhỏ hơn khóa của node đang xét và tất cả node của cây con bên phải có khoá lớn hơn hoặc bằng khóa của 2 node đang xét. Trong cây 2-3-4 thì nguyên tắc cũng giống như trê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