|
'''1. Cây 2 - 3 - 4'''
:''' 1.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.
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.
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 haimột mục dữ liệu thì luôn luôn có 32 con. ▼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::* Một node khôngvới phảihai làmục ládữ cóliệu 3thì cáchluôn sắpluôn xếpcó như3 sau:con.
-::* Một node với mộtba mục dữ liệu thì luôn luôn có 24 con.
▲ - Một node với hai mục dữ liệu thì luôn luôn có 3 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
- 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
: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.'' ▼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
: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.''
▲ 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).
| 