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

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