:'''Cây 2 - 3 - 4 ''' là [[Cây (lý thuyết đồ thị)|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'''
:Cây 2 - 3 - 4 là cây cân bằng giống [[cây Đỏ đỏ- Đenđen]]. Tuy nhiên, ít hiệu quả hơn cây Đỏđỏ - Đenđen nhưng ngược lại dễ lập trình hơn. ▼'''1. 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 node của nó có thể có đến bốn node con và ba mục dữ liệu.
: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: ▼▲: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.
::* 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
▲: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ới vậy, mộtmọi node không phải là láthì phải luôn luônkhông có số node con nhiềunhưng hơncó thể chứa 1, so2 vớihoặc số3 mục dựdữ liệu, củakhông nócó node rỗng. NóiMột cáchcây khác,2 đối- với3 mọi- node4 vớicó sốthể concó làđến lbốn vàcây sốcon mụcnên dữđược liệugọi là d,''cây thì:nhiều lnhánh =bậc d + 14.''
: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)''. ▼: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.''
==Tổ chức==
▲: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)''.
: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: ▼'''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).''
::* 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. ▼▲: 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ứ 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.
▲::* 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.
:TrongLưu tấtý cảrằng: cây 2 - 3 - 4, cáclà lácây đềucân nằmbằng. trênNó cùngvẫn mộtgiữ mức.được Cácsự nodecân ởbằng mứckhi trênthêm thườngvào khôngcác đầyphần đủ, nghĩa là chúngtử có thểthứ chứatự chỉ''(tăng 1dần hoặc 2 mục dữ liệu thay vì 3giảm mụcdần)''.
: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)''.
[[Thể loại: Cây (khoa học máy tính)]]
[[de:2-3-4-Baum]]
| 