Cây 2-3-4

Trong khoa học máy tính, **cây 2-3-4** là cây nhiều nhánh mà mỗi nút của nó có thể có đến bốn nút con và ba mục dữ liệu. 
Cây 2-3-4 là 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ó 2-3 hoặc 4 liên kết đến các nút con có thể có được trong một nút cho trước. 

Với mọi 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ó nút rỗng. Một cây 2-3-4 có thể có đến bốn 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ừ nút lá (*nút không có nút con*).

## Tổ chức
### Các khóa trong một nút
Trong một nút lá hoặc nút trong có thể có 2-3-4 khóa đại diện cho mục dữ liệu. Các khóa trong mỗi nút được sắp xếp theo thứ tự tăng dần. Tất nhiên các nút lá không có con.  

Còn với các nút không phải là lá, trong từng trường hợp có số nút con như sau:
* Một nút chứa một khóa luôn luôn có đúng 2 nút con. Nó được gọi là 2-nút.
* Một nút chứa hai khóa luôn luôn có đúng 3 nút con. Nó được gọi là 3-nút.
* Một nút chứa ba mục khóa luôn luôn có đúng 4 nút con. Nó được gọi là 4-nút.

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ố khóa của nó. Nói cách khác, đối với mọi nút trong có số con là *l* và số khóa là *d*, thì: *l* = *d*+ 1.

### Các khóa nằm trong các nút khác nhau
Một đặc tính quan trọng của cấu trúc cây tìm kiếm nhị phân 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 nút đang xét và tất cả nút của cây con bên phải, có khoá lớn hơn hoặc bằng khoá của nút đang xét. 

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:
# Tất cả các nút con của cây con thứ 1 của nút cha có các khoá nhỏ hơn khoá thứ nhất của nút cha.
# Tất cả các nút con của cây con thứ 2 của nút cha 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 có khóa thứ hai).
# Tất cả các nút con của cây con thứ 3 (nếu có) của nút cha 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 có khóa thứ ba).
# Tất cả các nút con của cây con thứ 4 (nếu có) của nút cha có các khoá lớn hơn khoá thứ ba của nút cha.

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 khóa thay vì 3 khóa.

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 ngay ca 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.

Trong hình trên đây, khóa tiền nhiệm của khóa 24 là khóa 22, còn khóa kế vị của khóa 24 là khóa 26.

## 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ó 1 khóa là a1  , B là nút thứ k+1 của nút cha và B có 3 khóa b1 23 . Khóa thứ k của nút cha là ck. Khi đó ta có a1k  1 2 3 .
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.

Nếu nút anh em liền kề với nút **u** chỉ có một nút có thể tăng số khóa của **u** từ một nút anh em không liền kề có nhiều hơn một khóa bằng 2 hoặc 3 phép dịch chuyển liên tiếp.

### 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 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 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-nút
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).keys1 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.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 k0 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.keys0 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 m0 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 }

Nguồn:
* Ford, William and William Topp. Data Structures with C++ Using STL, Second Edition. Upper Saddle River, New Jersey: Prentice Hall, 2002. ISBN: 0-13-085850-1.  Pages 683-290 of section 12.6: 2-3-4 Trees
* More info on 2-3-4 Tree

## Xem thêm
* Cây tìm kiếm nhị phân
* Cây AVL
* Cây đỏ đen