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 98:
 
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.
 
==Giả mã==
Trong phần này ta sử dụng một số ký hiệu sau:
#Nếu u là một nút thì u.keys chỉ số khóa chứa trong u, khi đó số con của nó là u.keys+1, giá trị của các khóa được chứa trong mảng u.key[1..3];
#Các nút con của nút u được trỏ đến bởi mảng con trỏ u.child[1..4];
#Cha của nút u được trỏ bởi biến con trỏ u.parent, nếu u là nút gốc thì u.parent = Null, nếu u là con thứ m của nút cha thì m được lưu trữ bởi biến u.order
#Biến u.leaf = true / false tùy theo u là lá hay nút trong.
===Phép dịch chuyển===
'''Procedure Trans_keys(u,bleft)'''
{chuyển một khóa từ nút v là anh (nếu bleft = true) / em (nếu bleft=false) cho u nếu v có nhiều hơn một khóa và u có ít hơn ba khóa }
1.if (u.keys>2) then return false;
2.if (bleft and then u.order=1) or (!bleft and then u.order=u.parent.keys+1) then return false;
3.m= u.order;
4.if bleft then v:=u.parent.child(m-1)
5.else v:=u.parent.child(m+1);
6. if v.keys <2 then return false;
7. u.keys:=u.keys+1
8. if bleft then begin { Chuyển từ nút kề bên trái sang }
9. for i:=2 to u.keys+1 do u.key(i):=u.key(i-1);
10. u.key(1)=u.parent.key(m);
11. u.parent.key(m):=v.key(v.keys);
12. end;
13. else begin { Chuyển từ nút kề bên phải sang }
14. u.key(u.keys)=u.parent.key(m+1);
15. u.parent.key(m+1):=v.key(1);
16. for i:=1 to u.keys do v.key(i)=v.key(i+1);
17. end;
18. v.keys:=v.keys-1;
19.return true;
=== Phép tách nút ===
'''Procedure SplitNode(u);'''
1.if u.keys<3 then return fase;
2.if u.parent = Null then begin { tách nút gốc }
3. NewNode(v1);v1.key(1):=u.key(1); v1.keys:=1; v1.parent:=u;
4. NewNode(v2);v2.key(1):=u.key(3); v2.keys:=1; v2.parent:=u;
5. u.child(1).parent:=v1;u.child(2).parent:=v1; v1.child(1)=u.child(1); v1.child(2)=u.child(2);
6. u.child(3).parent:=v2;u.child(4).parent:=v2; v2.child(1)=u.child(3); v2.child(1)=u.child(1);
7. u.key(1)=u.key(2); u.keys:=1; end;
8.else begin { tách nút không là gốc }
9. if u.parent.keys>2 then SplitNode(u.parent) ; { gọi đệ quy }
10. m:= u.order;
11. u.parent.keys:=u.parent.keys+1;
12. for i:=u.parent.keys-1 downto m do u.parent.key(i+1)=u.parent.key(i);
13. for i:=u.parent.keys downto m+1 do u.parent.child(i+1):= u.parent.child(i);
14. u.parent.key(1)=u.key(2);
15. NewNode(v); v.keys:=1; v.key(1):= u.key(3); v.parent=u.parent; u.parent.child(2):=v;
16. v.child(1):=u.Child(3); v.child(2):=u.Child(4);
17. u.keys:= 1;
18.end;
 
=== Gộp nút===
'''Procedure Fusion(u) ; '''
1.if u.keys>1 then return false;
2. if u.parent = Null then return false;
3. m:=u.order;
4. if m = 1 then v:= u.parent.child(2) else v:= u.parent.child(m-1) ;
5. if v.keys>1 then return false ;
6. u.keys:=3;
7. if u.parent= Null then return false;
8. if u.parent.keys=1 then TwoNodeAddKey(u.parent);
9. if m:=1 then begin
10. u.key(2)=u.parent.key(1); u.key(3):= v.key(1);
11. u.child(3):=v.child(1); u.child(4):=v.child(2); v.Child(3).parent:=u; v.Child(4).parent:=u ;
12. for i:=1 to u.parent.keys-1 do u.key(i):= u.key(i+1);
13. for i:=2 to u.parent.keys do u.parent.child(i):=u.parent.child(i+1)
14. end;
15. else begin
16. u.key(3):= u.key(1); u.key(1):=v.key(1); u.key(2):= u.parent.key(m-1);
17. u.child(3):=uChild(1);u.Child(4):=u.Child(2);
18. u.child(1):=v.child(1); u.child(2):=v.child(2); v.child(1).parent:=u; v.child(2).parent:=u;
19. for i:=m to u.parent.keys-1 do u.key(i):= u.key(i+1);
20. for i:=m to u.parent.keys do u.parent.child(i):=u.parent.child(i+1);
21. u.parent.child(m-1):=u;
22. end;
23.u.parent.keys:=u.parent.keys-1;
24.dispos(v);
 
=== Tăng số khóa cho 2-node ===
Khi xóa một khóa trong hai nút, trước hết phải dùng phép chuyển khóa hoặc phép dồn nút để tăng số khóa của nút này. Nếu tìm được một khóa anh em có nhiều hơn một khóa có thể dùng phép dịch chuyển, nếu không có có thể dùng một phép gộp nút.
====Tìm nút anh em có nhiều hơn một khóa====
'''Procedure FindSubling(u);'''
1.if u.parent= Null then return 0;
2.m:=u.order;
3.k:=m+1
4.while (k≤ u.parent.keys+1) and (u.parent.child(k).keys<2) do k:=k+1;
5.if k ≤ u.parent.keys+1 then return k;
6.else while (k≥1) and (u.parent.child(k).keys<2) do k:=k-1;
7.if k = 0 then return 0 else return k;
 
====Tăng số khóa cho 2-node====
'''Procedure TwoNodeAddKey(u);'''
1.If u.keys>1 then return false ;
2.if u.parent=null then fusion(u);
3.else begin
4. k= FindSubling(u);
5. if k=0 then
6. fusion(u);
7. else
8. if k< u.order then
9. for i:= k+1 to u.order do TransKey(u.parent.Child(i),true);
10. else
11. for i:= k-1 downto u.order do TransKey(u.parent.Child(i),false);
12.end;
=== Tìm kiếm một khóa trong cây ===
====Tìm một khóa trong một nút====
Giả sử u có n khóa. Đặt thêm các phần tử khóa hai đầu u.key(0) =  ∞ và u.key(n+1)= +∞. Khi tìm khóa k trong nút u có thể hoặc k = u.key(j) với 1 ≤ j ≤ n hoặc k thuộc một trong u.keys+1 khoảng (u.key(j),u.key(j+1)) , j=0,..,n. Trong trường hợp thứ nhất hàm trả về chỉ số khóa tìm thấy j, trong trường hợp sau hàm trả về chỉ số của cận sau trong khoảng nó tìm thấy với dấu âm.
'''Procedure NodeSearchKey(u, k);'''
1.for j:=1 to u.keys do if k=u.key(j) return j;
2.j:=1;
3.while k > u.key(j) and j ≤ n do j:= j+1;
4.return j+1;
====Tìm một khóa trong cây====
'''Procedure TreeSearchKey(k; var v);'''
1.v:= Root.
2.k:=NodeSeachKey(v,k);
3.while k<0 and !u.leaf do begin
4. v:= v.child(abs(k));
5. k:=NodeSeachKey(v,k); end;
6.if k>0 return true else return false;
====Tìm khóa tiền vị và khóa kế vị của một khóa====
Nút chứa khóa tiền vị của khóa thứ m trong nút u
 
'''Procedure Predecessor(u,m);'''
1.v:= u.Child(m);
2.while !v.leaf do v:=v.child(v.keys+1);
3.return v; { khóa cuối của v là khóa cần tìm}.
 
Nút chứa khóa thế vị của khóa thứ m trong nút u
 
'''Procedure Successor(u,m)'''
1.v=u.child(m+1);
2.while !v.leaf do v:=v.child(1);
3.return v; { khóa thứ nhất của v là khóa cần tìm}.
 
=== Chèn một khóa vào cây 2-3-4===
Để chèn khóa k vào cây 2-3-4 ta sử dụng thủ tục đệ quy sau với nút gốc.
 
'''Procedure NodeInsert(u,k);'''
1.if u= Null then begin
2. NewNode(v);
3. v.Keys=1; v.key(1):= k;
4. root:= v;
5. v.parent := Null;
6. end;
7.else begin
8. m=NodeSearchKey(u, k)
9. if u.leaf then
10. if u.keys<3 then begin
11. if m>0 then return 0
12. else begin
13. m=-m; u.keys:=u.keys+1;
14. for j:=u.keys downto m+1 do u.key(j):= u.key(j-1);
15. u.key(m):= k;
16. end;
17. end;
18. else begin { u có 3 khóa }
19. m:=NodeSearchKey(u,k);
20. SplitNode(u);
21. v:= u.parent.child(u.order+1);
22. case of m
23. 1 : u.keys:=2; u.key(2):= u.key(1); u.key(1):=k;
24. 2: u.keys:=2; u.key(2):= k;
25. 3: v.keys:=2; v.key(2):= v.key(1); v.key(1):=k;
26. 4: v.keys:=2; v.key(2):= k;
27. end;
28.else begin { u không là lá }
29. if m>0 then return false
30. else NodeInsert(u.child(m),k)
31. end;
32.end;
 
=== Xóa khóa khỏi cây 2-3-4===
====Xóa một khóa trong nút lá===
'''Procedure LeafDelete(u, k);'''
1.if !u.leaf then return false;
2.m:=NodeSearchKey(u,k)
3.if m<0 then return false;
4.for i:= m to u.keys-1 do u.key(i):=u.key(i+1)
5.u.keys:= u.keys-1;
====Xóa một khóa trong cây gốc ở đỉnh u ===
'''Procedure NodeDelete(u, k);'''
1.m=NodeSearch(u,k);
2.if m>0 then begin { tìm thấy k trong nút u }
3. if u.lesft then begin {nếu u là lá}
4. if (u.keys=1) and u=root then begin
5. dispos(u); return true ; end
6. else begin
7. if u.keys=1 then fusion(u);
8. leafdelete(u,k);
9. end;
10. end {nếu u là lá}
11. else begin {tìm thấy k trong nút u là nút trong }
12. v:= predecessor(u,m);
13. if v.keys=1 then v:=successor(u,m) ;
14. if v.keys=1 then fusion(u);
15. leafdelete(v,k);
16. end; {tìm thấy k trong nút u là nút trong }
17. end { tìm thấy k trong nút u }
18. else begin { m< 0 không tìm thấy k trong nút u }
19. m:=-m ;
20. v:= u.child(m);
21. if v # Null then NodeDelete(v, k)
22. else return false ; { không có khóa k trong cây gốc u }
23. end;
24.end; { m< 0 không tìm thấy k trong nút u }