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)|nodenút]] của nó có thể có đến bốn nút con và ba mục dữ liệu.

Trong một nút lá hoặc nút trong có thể có 2-3-4 khóa đại diện cho mục dữ liệu. Các khóa trong mỗi nodenút được sắp xếp theo thứ tự tăng dần. Tất nhiên các nút lá không có con.

* Một nút chứa một khóa luôn luôn có đúng 2 nút con. Nó được gọi là 2-nodenút.

* Một nút chứa hai khóa luôn luôn có đúng 3 nút con. Nó được gọi là 3-nodenút.

* Một nút chứa ba mục khóa luôn luôn có đúng 4 nút con. Nó được gọi là 4-nodenút.

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ố khóa của nó. Nói cách khác, đối với mọi nodenút với số con là l và số khóa là d, thì: l = d + 1.

Một đặc tính quan trọng của cấu trúc [[cây tìm kiếm nhị phân]] 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 nodenút đang xét và tất cả nodenút của cây con bên phải, có khoá lớn hơn hoặc bằng khoá của nodenút đang xét.

*Phép biến đổi này tách một nút thành hai nút, nghĩa là thêm một nút anh em với nó. Như vậy số con của nút cha tăng thêm một, do đó số khóa của nút cha cũng tăng lên một. Khóa tăng thêm này được lấy từ chính nút con sẽ được tách ra. Do đó để có thể tách một nút, nút đó phải có đúng 3 khóa k1 < k2 < k3 (nó là 4-nodenút). Khi tách, chỉ khóa k1 được giữ lại nút ban đầu (nút này trở thành 2-nodenút), k3 được gán cho nút mới tạo thêm (là 3-nodenút), còn k2 được thêm vào nút cha. Như vậy nút ban đầu và nút mới tạo ra là anh em liền kề. Nếu nút cha đã là 4-nodenút thì trước khi thêm k2 vào nó cần tách chính nút cha này.

Phép gộp hai nút anh em liền kề thành một nút. Khi đó số con của nút cha giảm đi một, do đó cả số khóa của nút cha cũng giảm một. Khóa này được đưa cả vào nút mới gộp. Do đó chỉ có thể gộp hai anh em liền kề thành một nút khi cả hai là các 2-nodenút, nghĩa là mỗi nút chỉ có đúng một khóa, đồng thời cha của chúng phải có nhiều hơn một khóa. Sau khi gộp, nút ban đầu trở thành 4-nodenút, còn nút anh em được giải phóng.

Để chèn một khóa vào một cây 2-3-4 , trước hết tìm giá trị đó trong cây, nếu không thấy thì chèn khóa đó vào nút lá gặp tại cuối quá trình tìm kiếm. Nếu nút này có ít hơn 3 khóa thì việc thêm khóa đó vào nút đơn giản là việc sắp xếp nó cùng với các khóa đã có theo thứ tự tăng. Nếu nút là muốn chèn thêm là 4-nodenút thì trước khi chèn ta tách nút đó ra. Điều phức tạp xảy ra khi nút cha của nút định tách cũng là 4-nodenút. Khi đó trước khi tách nút này phải tách nút cha của nó.

Khóa k nằm trong nút lá u và u chỉ có một khóa và tồn tại nút anh em v của u có nhiều hơn một khóa thì bằng phép dịch chuyển dần có thể dịch chuyển một khóa của v đến u khiến u trở thành 3-nodenút và quay về trường hợp 1.

Khóa k nằm trong nút lá u và u chỉ có một khóa và tất cả các nút anh em của u chỉ có một khóa thì bằng phép gộp u với nút anh em kề nó sẽ khiến u trở thành 3-nodenút và quay về trường hợp 1.

Khóa k nằm trong nút trong u: Khi đó tìm khóa tiền nhiệm hoặc khóa kế vị của k (khóa này luôn nằm trong nút lá). Thay k bởi khóa đó, và giải phóng khóa đó tkhỏi nút chứa nó (quay về trường hợp 1). Tuy việc dùng khóa tiền nhiệm hay kế vị đều được, nhưng nên chọn khóa nào trong chúng nằm trong nút có hai khóa trở lên, nếu cả hai đều nằm trong các 2-nodenút thì chọn khóa nào cũng được.

=== Tăng số khóa cho 2-nodenút ===

Nếu hàm trả về 0 thì tất cả các nút anh em đều là 2-nodenút

====Tăng số khóa cho 2-nodenút====