Cây 2-3-4
Bách khoa toàn thư mở Wikipedia
Cây 2 - 3 - 4 là cây nhiều nhánh mà mỗi node của nó có thể có đến bốn node con và ba mục dữ liệu.
Cây 2 - 3 - 4 là cây cân bằng giống cây đỏ-đen. Tuy nhiên, ít hiệu quả hơn cây đỏ - đen nhưng ngược lại dễ lập trình hơn.
Các số 2, 3, 4 trong cụm từ 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ó 3 cách sắp xếp như 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à l và số mục dữ liệu là d, thì: l = d + 1
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 bốn 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à hai liên kết, trừ lnode lá (node không có liên kết nào).
[sửa] Tổ chức
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).
Một đặc tính quan trọng của bất kỳ cấu trúc cây là mối liên hệ giữa các liên kết với giá trị khoá của cây con bên trái có khoá nhỏ hơn khoá 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 khoá của node đang xét. Trong cây 2 - 3 - 4 thì nguyên tắc cũng giống như trên, nhưng thêm 1 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ó tất 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.
Trong tất cả cây 2 - 3 - 4, các lá đều nằm trên cùng một mức. Các node ở mức trên thường không đầy đủ, nghĩa là chúng có thể chứa chỉ 1 hoặc 2 mục dữ liệu thay vì 3 mục.
Lưu ý rằng: cây 2 - 3 - 4 là cây cân bằng. Nó vẫn giữ được sự cân bằng khi thêm vào các phần tử có thứ tự (tăng dần hoặc giảm dần).
