Khác biệt giữa bản sửa đổi của “Cây 2-3-4”
Nội dung được xóa Nội dung được thêm vào
nKhông có tóm lược sửa đổi |
nKhông có tóm lược sửa đổi |
||
Dòng 16:
: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)''.
:'''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).''
: 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)''.
[[Thể loại: Cây|Cây 2 - 3 - 4]]
| |||