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
Không có tóm lược sửa đổi |
|||
Dòng 1:
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)|node]] của nó có thể có đến bốn nút con và ba mục dữ liệu.
[[Hình:2-3-4 tree example.png|phải]]▼
Cây 2-3-4 là [[cây cân bằng (lý thuyết đồ thị)|cây cân bằng]] giống như [[cây đỏ-đen]], tuy nhiên ít hiệu quả hơn nhưng ngược lại dễ lập trình hơn.
Các số 2, 3, 4 trong cụm từ 2-3-4 có ý nghĩa là khả năng có
Với mọi [[Cây (cấu trúc dữ liệu)|nút lá]] thì không có nút con, nhưng có thể chứa 1, 2 hoặc 3 mục dữ liệu, không có [[Cây (cấu trúc dữ liệu)|nút rỗng]]. Một cây 2-3-4 có thể có đến bốn [[Cây (cấu trúc dữ liệu)|cây con]], nên được gọi là ''cây nhiều nhánh bậc 4''.▼
Trong cây 2-3-4 mỗi nút có ít nhất là hai liên kết, trừ [[Cây (cấu trúc dữ liệu)|nút lá]] (''nút không có nút con'').▼
==Tổ chức==▼
===Các khóa trong một nút===▼
Đối với các nút không phải là lá, có 3 cách sắp xếp như sau:
* Một nút với một mục dữ liệu thì luôn luôn có 2 nút con.
[[Hình:2-3-4 tree 2-node.png]]
Hàng 13 ⟶ 20:
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ố mục dự liệu của nó. Nói cách khác, đối với mọi node với số con là l và số mục dữ liệu là d, thì: l = d + 1.
▲Với mọi [[Cây (cấu trúc dữ liệu)|nút lá]] thì không có nút con, nhưng có thể chứa 1, 2 hoặc 3 mục dữ liệu, không có [[Cây (cấu trúc dữ liệu)|nút rỗng]]. Một cây 2-3-4 có thể có đến bốn [[Cây (cấu trúc dữ liệu)|cây con]], nên được gọi là ''cây nhiều nhánh bậc 4''.
▲Trong cây 2-3-4 mỗi nút có ít nhất là hai liên kết, trừ [[Cây (cấu trúc dữ liệu)|nút lá]] (''nút không có nút con'').
▲==Tổ chức==
▲===Các khóa trong một nút===
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]]
Hàng 33 ⟶ 34:
Trong cây 2-3-4, tất cả 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.
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 ta chèn các phần tử theo thứ tự ''tăng dần hoặc giảm dần''.
===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 tiền nhiệm 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.
Hàng 43 ⟶ 44:
===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 .
Hàng 49 ⟶ 51:
=== Tách một nút ===
[[Hình:234Split1.png|trái]]
[[Hình:234Split2.png|
[[Hình:234Split3.png|trái]]
Hàng 57 ⟶ 59:
=== Gộp hai nút ===
[[Hình:234Fusion.png|
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. Sau khi gộp, nút ban đầu trở thành 4-node, còn nút anh em được giải phóng.
Hàng 64 ⟶ 68:
== Chèn một khóa mới vào cây ==
[[Hình:234Inseart.png|trái]]
Để 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ó.
Hàng 73 ⟶ 79:
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===
[[Hình:234delete1.png|Trái]]
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===
[[Hình:234Delete2.png|Trái]]
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===
[[Hình:234Delete3.png|Trái]]
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===
[[Hình:234Delete4.png|Trái]]
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.
| |||