Cây 2-3-4

[mrszerono12]

CÂY 2-3-4
1. Giới thiệu về cây 2-3-4
Chúng ta sẽ xem xét các đặc tính của cây 2-3-4 và mối quan hệ khá gần gũi giữa cây 2-3-4 và cây đỏ-đen.
Hình 1 trình bày một cây 2-3-4 đơn giản. Mỗi node có thể lưu trữ 1, 2 hoặc 3 mục dữ liệu.

	[IMG]file:///C:/Users/user/AppData/Local/Temp/msohtmlclip1/01/clip_image001.gif[/IMG]

Hình 1 cây 2-3-4
Các số 2, 3 và 4 trong cụm từ cây 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ó thể có 3 cách sắp xếp sau:
[IMG]file:///C:/Users/user/AppData/Local/Temp/msohtmlclip1/01/clip_image002.gif[/IMG]Một node với một mục dữ liệu thì luôn luôn có 2 con.
[IMG]file:///C:/Users/user/AppData/Local/Temp/msohtmlclip1/01/clip_image002.gif[/IMG]Một node với hai mục dữ liệu thì luôn luôn có 3 con.
[IMG]file:///C:/Users/user/AppData/Local/Temp/msohtmlclip1/01/clip_image002.gif[/IMG]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à k và số mục dữ liệu là d, thì : k = d + 1Trích từ: http://www.kilobooks.com