Khác biệt giữa bản sửa đổi của “Cây 2-3-4”

Trong [[khoa học máy tính]], '''cây 2-3-4''' là [[Cây (cấu trúc dữ liệu)|cây]] nhiều nhánh mà mỗi [[Cây (cấu trúc dữ liệu)|node]] của nó có thể có đến bốn nút con và ba mục dữ liệu.

Cây 2-3-4 là [[cây cân bằng (lý thuyết đồ thị)|cây cân bằng]] giống như [[cây đỏ-đen]], tuy nhiên ít hiệu quả hơn 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 [[Cây (cấu trúc dữ liệu)|nút con]] có thể có được trong một nút cho trước. Đối với các nút không phải là lá, có 3 cách sắp xếp như sau:

* Một nút với một mục dữ liệu thì luôn luôn có 2 nút con.

* Một nút với hai mục dữ liệu thì luôn luôn có 3 nút con.

* Một nút với ba mục dữ liệu thì luôn luôn có 4 nút con.

 

Như vậy, một nút không phải là lá phải luôn luôn có số nút 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.

==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 một số điểm sau:

 

 

Chẳng hạn xuất phát từ cây 2-3-4 sau: Cây gồm một nút gốc với 3 nút con.

Bây giờ chèn "25" vào cây. Vì 25 > giá trị cuối của gốc và nút dưới cùng bên phải là 4-nút, một phép quay đươc thực hiện trước khi chèn. Tách 4-nút (22, 24, 29) bằng cách chuyển 24 lên nút cha.

Tách 3-nút (22,29) thành một phần của con thứ tư của 3-nút.

So sánh nút 25 với nút cha va đi về bên phải. Sau đó chèn vào nút này. Cây bây giờ trở thành cân bằng. Lại có thể chèn một giá trị khác vào cây.

 

 

Nguồn: