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
Dòng 42:
==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 ===
[[Hình:234Trans.png|phải]]
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.
Giả sử A là con thứ k của nút cha và A có 2 khóa là a1 , B là nút thứ k+1 của nút cha và B có 3 khóa b1 < b2< b3 . Khóa thứ k của nút cha là ck. Khi đó ta có a1< ck < b1 < b2 <b3 .
Phép dịch chuyển sẽ chuyển khóa ck từ nút cha xuống cuối nút A và chuyển khóa đầu tiên b1 của nút B lên thay cho ck. Như vậy trong phép dịch chuyển này số khóa của nút cha không thay đổ, số khóa của nút A tăng thêm một và số khóa của nút B giảm một. Để số khóa của A và B nằm trong phạm vi từ 1 đến 3, điều kiện để thực hiện phép chuyển khóa là số khóa của nút A nhỏ hơn 3 và số khóa của nút B lớn hơn 1.
=== 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-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.
| |||