Khác biệt giữa bản sửa đổi của “Cây 2-3-4”

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 nút trong có số con là ''l'' và số khóa là ''d'', thì: ''l'' = ''d''+ 1.

 

 

===Các khóa nằm trong các nút khác nhau===

==Các phép biến đổi không làm thay đổi tính chất của cây 2-3-4==

===Dịch chuyển khóa ===

 

Phép biến đổi này chuyển một khóa từ một 3-nút hoặc 4-nút sang một nút anh em kề nó có ít hơn 3 khóa.

Nếu nút anh em liền kề với nút '''u''' chỉ có môt nút có thể tăng số khóa của '''u''' từ một nút anh em không liền kề có nhiều hơn một khóa bằng 2 hoặc 3 phép dịch chuyển liên tiếp.

 

 

=== Tách một nú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-nút). Khi tách, chỉ khóa k1 được giữ lại nút ban đầu (nút này trở thành 2-nút), k3 được gán cho nút mới tạo thêm (là 3-nú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-nút thì trước khi thêm k2 vào nó cần tách chính nút cha này.

 

=== Gộp hai nút ===

 

 

 

== Chèn một khóa mới vào cây ==

Để 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-nú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-nút. Khi đó trước khi tách nút này phải tách nút cha của nó.

Phép xóa một khóa k khỏi cây 2-3-4 đòi hỏi những phân tích phức tạp hơn. Trước hết tìm nút chứa nó. Các trường hợp sau có thể xảy ra:

===Trường hợp 1===

 

Khóa k nằm trong nút lá u và u có nhiều hơn một khóa: giải phóng khóa k khỏi u .

===Trường hợp 2===

 

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-nút và quay về trường hợp 1.

 

===Trường hợp 3===

 

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-nút và quay về trường hợp 1.

===Trường hợp 4===

 

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-nút thì chọn khóa nào cũng được.