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 18:
==Tổ chức==
===Các khóa trong một nút===
[[Hình:2-3-4Tree.png|phải]]▼
Các mục dữ liệu trong mỗi node được sắp xếp theo thứ tự tăng dần từ trái sang phải (''sắp xếp từ thấp đến cao'').
▲[[Hình:2-3-4Tree.png|phải]]
Một đặc tính quan trọng của bất kỳ cấu trúc cây 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 node đang xét và tất cả node của cây con bên phải, có khoá lớn hơn hoặc bằng khoá của node đang xét. Trong cây 2-3-4 thì nguyên tắc cũng giống như trên, nhưng thêm một số điểm sau:▼
===Các khóa nằm trong các nút khác nhau===
▲Một đặc tính quan trọng của
Trong cây 2-3-4 thì một cấu trúc tương tự như trên, thể hiện trong các tính chất sau:
Trong
Lưu ý rằng: cây 2-3-4 là cây cân bằng. Nó vẫn giữ được sự cân bằng khi
===Khóa tiền nhiệm và khóa kế vị===
Cũng như trong cây tìm kiếm nhị phân, trong cây 2-3-4 khóa tiền nhiệm của một khóa k là khóa lớn nhất trong các khóa nhỏ hơn k, khóa kế vị là khóa nhỏ nhất trong các khóa lớn hơn k.
Theo cấu trúc của cây 2-3-4, để tìm khóa tiền nhiệm và khóa kế vị của khóa k trước hết tìm nút u chứa khóa k.
Nếu u là nút trong, giả sử k là khóa thứ m của u, khi đó khóa là khóa cuối cùng của nút cực phải trong cây thứ m của nút u, còn khóa kế vị là khóa đầu tiên trong nút cực trái của cây con thứ m+1 của nút u.
Nếu khóa k nằm trong nút lá u, việc tìm khóa tiền nhiệm và kế vị có khó khăn hơn, tuy nhiên, trong các ứng dụng của cây 2-3-4 không cần đến trường hợp này.
==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.
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.
Trong trường hợp nút cần tách là nút gốc, vì nút gốc không có cha nên ngoài việc tách ra còn phải thêm một nút mới làm cha của nút ban đầu và nút mới tách ra.
=== Gộp hai nút ===
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-node, 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.
==Tìm một khóa trên cây 2-3-4==
▲* Tất cả các nút con của cây con thứ 1 của nút cha thì có các khoá nhỏ hơn khoá thứ nhất của nút cha.
Để tìm một khóa k trên cây 2-3-4, trước hết ta tìm nó trong dãy khóa của nút gốc. Tại mỗi nút, nếu tìm thấy một khóa của nút bằng k thì trả về true và dừng quá trình tìm kiếm. Nếu không tìm thấy và nút đó là lá thì trả về false , còn nếu nút đó là nút trong và k nằm giữa khóa thứ m và m+1 thì tiếp tục tìm kiếm trong con thứ k của nút đó.
▲* Tất cả các nút con của cây con thứ 2 của nút cha thì có các khoá lớn hơn khoá thứ nhất và nhỏ hơn khóa thứ hai của nút cha (nếu nút cha khóa tứ hai).
▲* Tất cả các nút con của cây con thứ 3 (nếu có) của nút cha thì có các khoá lớn hơn khoá thứ hai và nhỏ hơn khóa thứ ba của nút cha (nếu nút cha khóa tứ ba).
▲* Tất cả các nút con của cây con thứ 4 (nếu có) của nút cha thì có các giá trị khoá lớn hơn khoá thứ ba của nút cha.
== Chèn một khóa mới vào cây ==
▲Trong tất cả cây 2-3-4, các lá đều nằm trên cùng một mức. Các nút ở mức trên thường không đầy đủ, nghĩa là chúng có thể chứa chỉ 1 hoặc 2 mục dữ liệu thay vì 3 mục.
Để 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-node 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-node. Khi đó trước khi tách nút này phải tách nút cha của nó.
==Xóa một khóa khỏi cây 2-3-4==
▲Lưu ý rằng: cây 2-3-4 là cây cân bằng. Nó vẫn giữ được sự cân bằng khi thêm vào các phần tử có thứ tự (''tăng dần hoặc giảm dần'').
Nếu phép chèn một khóa vào một nút phải giải quyết trường hợp tràn với nút đầy đẫn tới thao tác tách, nghĩa là thêm một nút, thì phép xóa phải giải quyết trường hợp cạn đối với 2-nút, khi đó việc giải phóng khóa đó dẫn tới một nút rỗng, nghĩa là phải giải phóng nút này.
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-node 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-node 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-node thì chọn khóa nào cũng được.
== Phép chèn ==
| |||