CTDL B-Tree
1. Định nghĩa
Một B-tree bậc N (hay còn gọi là bậc N*2+1) là cây tìm kiếm đa phân cân bằng có các đặc tính sau:
(+) Nút gốc hoặc là lá hoặc có ít nhất hai nút con
(+) Mỗi nút (ngoại trừ nút gốc) chứa tối thiểu N khóa.
(+) Một nút bất kỳ chứa tối đa N*2 khóa.
(+) Một nút bất kỳ khác lá chứa k khóa thì nó có k+1 nút con.
(+) Các đường đi từ gốc tới các lá có cùng độ dài.
Ví dụ:
Hình 1. B-tree bậc 5 có 3 mức
Khai báo và khởi tạo:
-Khai báo:
#define ORDER 5
#define Ndiv2 2 /* =ORDER/2 */
#define TRUE 1
#define FALSE -1
typedef struct tagNODE {
int NumTree; /* so cay con cua nut hien hanh */
int Key[ORDER-1]; /* mang luu tru cac khoa cua nut */
tagNODE* Branch[ORDER]; /* mang luu tru cac con tro chi den cac nut con */
} *NODEPTR; /* con tro nut va cac kieu con tro nut */
NODEPTR Root; /* con tro nut goc */
Hàm INIT
Khởi tạo cây rỗng.
void Init() {
Root=NULL;
}
2. Tìm kiếm trên B-Tree
Hình 2. Tìm kiếm giá trị X
Xét nút trong Hình 2, khoá cần tìm là X. Giả sử nội dung của nút nằm trong bộ nhớ. Với m đủ lớn ta sử dụng phương pháp tìm kiếm nhị phân, nếu m nhỏ ta sử dụng phuơng pháp tìm kiếm tuần tự.
Nếu X không tìm thấy sẽ có 3 trường hợp sau xảy ra:
(+) Ki < X < Ki+1. Tiếp tục tìm kiếm trân cây con Ci
(+) Km < X. Tiếp tục tìm kiếm trên Cm
(+) X < K1. Tiếp tục tìm kiếm trên C0
Quá trình này tiếp tục cho đến khi nút đúng được tìm thấy. Nếu đã đi đến nút lá mà vẫn không tìm thấy khoá, việc tìm kiếm là thất bại.
Hàm NODESEARCH
Trả về vị trí nhỏ nhất của khóa trong nút p bắt đầu lớn hơn hay bằng k. Trường hợp k lớn hơn tất cả các khóa trong nút p thì trả về vị trí p-> NumTree-1
int NodeSearch (NODEPTR p, int k) {
int i = 0;
for (i=0; i< p->NumTree-1 && p->Key[i] < k; i++);
return i;
}
Hàm NodeSearch được dùng để tìm khóa k có trong nút p hay không. Nếu khóa k không có trong nút p thì phép toán này trả về vị trí giúp chúng ta chọn nút con phù hợp của p để tiếp tục tìm khóa k trong nút con này.
Hàm SEARCH:
Tìm khóa k trên B-Tree. Con trỏ p xuất phát từ gốc và đi xuống các nhánh cây con phù hợp để tìm khóa k có trong một nút p hay không.
Nếu có khóa k tại nút p trên cây:
+ Biến found tra về giá trị TRUE
+ Hàm Search( ) trả về con trỏ chỉ nút p có chứa khóa k
+ Biến position trả về vị trí của khóa k có trong nút p này
Nếu không có khóa k trên cây: lúc này p = NULL và q (nút cha của p) chỉ nút lá có thể thêm khóa k vào nút này được.
+ Biến found trả về giá trị FALSE
+ Hàm Search( ) trả về con trỏ q là nút lá có thêm nút k vào
+ Biến position trả về vị trí có thể chèn khóa k vào nút lá q này
NODEPTR Search(int k, int &Position, int &Found){
int i = 0;
NODEPTR p = Root, q = NULL;
while (p !=NULL) {
i = NodeSearch (p, k);
if (i< p->NumTree-1 && k == p->Key[i]) {
Found = TRUE;
Position = i; /* Vi tri tim thay khoa k */
return p; /* Nut co chua khoa k */
}
q = p;
p = p ->Branch[i];
}
/* Khong tim thay, luc nay p = NULL, và q la nut la co the them khoa k vao nut nay, Position là vi tri co the chen khoa k */
Found = FALSE;
Position = i;
return q; /* Tra ve nut la */
}
3. Duyệt cây B-Tree
Hàm SCAN
Duyệt các khóa của B-Tree theo thứ tự từ nhỏ đến lớn bằng phương pháp đệ qui
void Scan(NODEPTR p) {
if (p== NULL)
return;
else {
/* Vong lap duyet nhanh con Branch[i] va khoa Key[i] cua nut p */
for (int i = 0; i < p-> NumTree-1; i++){
Scan(p->Branch[i]);
printf ("%d ", p-> Key[i]);
}
/* Duyet nhanh con cuoi cung cua nut p */
Scan (p-> Branch[p-> NumTree-1]);
}
}
Hàm OUTPUTTREE
In cây dạng thư mục từ nút gốc đến các nút lá (gọi hàm với level=0 từ nút gốc):
void OutputTree(NODEPTR p,int level) {
if (p== NULL){
return;
}
else {
/* In so ky tu tab theo muc cua nut */
for (int i = 0; i < level; i++)
printf ("\t");
/* In cac khoa cua nut */
for (int i = 0; i < p->NumTree-1; i++) {
printf (".%d", p-> Key[i]);
}
printf (".\n");
/* In cac cay con */
for (int i = 0; i < p->NumTree; i++) {
OutputTree(p->Branch[i],level+1);
}
}
}
4. Thêm khóa vào B-Tree
Trước khi đưa ra giải thuật thêm một phần tử mới vào B-Tree, ta xem tình huống cụ thể qua các ví dụ sau :
Ví dụ 1: Thêm x = 22 vào B-Tree ở Hình 3.
- Khóa 22 chưa có trong cây. Nhưng không thể thêm vào nút C vì node C đã đầy.
- Do đó tách nút C thành hai nút : nút mới D được cấp phát và m+1 khóa được chia đều cho 2 node C và D, và khóa ở giữa được chuyển lên nút cha A : Hình 3
Hình 3: Quá trình tách node khi thêm khóa 22
Như vậy, việc thêm một khóa mới vào B-Tree có thể gây ra việc tách nút và việc tách nút có thể lan truyền ngược lên nút cha, trong trường hợp đặc biệt lan truyền đến tận gốc của B-Tree
Ví dụ 2:
Xem quá trình tạo B-Tree từ dãy các khóa sau : 20; 40 10 30 15; 35 7 26 18 22; 5; 4 13 46 27 8 32; 38 24 45 25
+ Hình 4 là tình trạng cây sau khi thêm vào khóa 30 và quá trình thêm khóa 15:
Hình 4: Quá trình tách node khi thêm khóa 15
Khi thêm vào 15 thì nút này bị đầy, do đó trường hợp này tạo thành 2 nút mới : phần tử ở giữa là 20 bị đẩy lên tạo thành một nút mới, các phần tử còn lại chia cho 2 nút : nút cũ chứa 10, 15 và nút mới thứ 2 chứa 30,40
+ Thêm vào các khóa 35, 7,26 và 18 chỉ đơn giản là việc bổ sung các khóa vào các nút có sẵn:
Hình 5: Thêm vào các khóa 35, 7,26 và 18
+ Đến khi thêm khóa 22 cũng có sự đầy nút dẫn đến việc tách nút (như ví dụ 1):
Hình 6: Quá trình tách node khi thêm khóa 22
+ Thêm vào 5 cũng có sự đầy nút (nút đang chứa 4 khóa 7, 10, 15, 18) dẫn đến việc tách nút :
Hình 7: Quá trình tách node khi thêm khóa 5
+ Thêm vào các khóa 42, 13, 46, 27 và 8 chỉ đơn giản là quá trình bổ dung khóa vào các nút có sẵn:
Hình 8: Thêm vào các khóa 42, 13, 46, 27 và 8
+ Khi thêm 32 có sự tách nút :
Hình 9: Quá trình tách nút khi thêm khóa 32
+ Thêm vào 38, 24 và 45 chỉ đơn giản là quá trình bổ dung khóa vào các nút có sẵn.
Hình 10: Thêm vào 38, 24 và 45
+ Thêm 25 vào có sự tách nút và cho thấy sự lan truyền tách nút ngược lên về phía gốc :
- 25 thêm vào nút (22, 24 26, 27) làm nút này bị tách và 25 được đưa lên nút cha (10, 20, 30, 40)
- 25 được đưa lên nút cha (10, 20, 30, 40) làm nút này bị tách thành 2 nút và khoá 25 được đưa lên thành cha (nút gốc mới)
Hình 11: Quá trình tách nút đệ quy khi thêm khóa 25
Hàm INSERTKEY
Thêm một khóa k vào B-Tree:
(+) Nếu B-Tree rỗng thì tạo nút gốc mới với khóa k
(+) Nếu B-Tree không rỗng thì tìm nút lá (phép toán Searcch) và thêm k vào vị trí pos: sử dụng phép toán InsertLeaf
void InsertKey(int k) {
int pos,found;
NODEPTR s;
if (Root == NULL)
Root = MakeRoot(k);
else {
s = Search(k, pos, found);
if (found == TRUE)
printf ("Bi trung khoa, khong them khoa %d vao B-Tree duoc", k);
else
InsertLeaf(s, k, pos);
}
}
Hàm INSERTLEAF
Thêm khóa k vào vị trí position của nút lá s (s và position do phép toán Search( ) trả về)
(1) Nếu nút s chưa đầy thì sử dụng phép toán InsNode để chèn khóa k vào nút s và dừng, ngược lại sang bước 2
(2) Nếu nút s đã đầy và s khác nút gốc thì thực hiện 2.1 và 2.2, ngược lại sang bước 3
(2.1) Tách nút s cùng với khóa k mới và nút con mới thành: nút nửa trái, nút nửa phải và khóa chính giữa.
(2.2) Gán nút s mới là nút cha của nút s, nút con mới là nút nửa phải, khóa k mới là khóa chính giữa, quay lại bước 2.
(3) Nút s chưa đầy sử dụng phép toán InsNode để chèn khóa k mới và nút con mới vào nút s và dừng
(4) Nếu nút s là nút gốc thì thực hiện 4.1 và 4.2
(4.1) Tách nút s cùng với khóa k mới và nút con mới thành: nút nửa trái, nút nửa phải và khóa ở giữa.
(4.2) Tạo nút gốc mới với khóa ở giữa, nhánh con 0 là nút nửa trái, nhánh con 1 là nút nửa phải. Kết thúc.
void InsertLeaf(NODEPTR s, int k, int position) {
NODEPTR nd = s, nd2, f = Father(nd), newnode = NULL;
int pos = position, newkey = k, midkey;
/* Vong lap tach cac node day */
while (f != NULL && nd->NumTree == ORDER) {
Split(nd, newkey, newnode, pos, nd2, midkey);
/* Gan lai cac gia tri sau khi tach node */
nd = f;
newkey = midkey;
newnode = nd2;
pos = NodeSearch (f, midkey);
f = Father (nd);
}
/* Truong hop node nd chua day va khong phai la node goc */
if (nd -> NumTree < ORDER) {
/* Chen newkey và newnode tai vi tri pos cua node nd */
InsNode (nd, newkey, newnode, pos);
return;
}
/* Truong hop nd là node goc bi day, tach node goc va tao node goc moi */
Split (nd, newkey, newnode, pos, nd2, midkey);
/* Tao node goc moi và gan cac node nd và nd2 vào goc */
Root = MakeRoot (midkey);
Root -> Branch[0] = nd;
Root -> Branch[1] = nd2;
}
Hàm SPLIT
Tách node đầy nd, phép toán này được gọi bởi phép toán InsertLeaf
(+) nd là nút đầy bị tách, sau khi tách xong nút nd chỉ còn lại một nửa số khóa bên trái
(+) newkey, newnode và pos là khóa mới, nhánh cây con và vị trí chèn vào nút nd
(+) Nút nd2 là nút nửa phải có được sau lần tách, nút nd2 chiếm một nửa số khóa bên phải
(+) Midkey là khóa ngay chính giữa sẽ được chèn vào nút cha
void Split(NODEPTR nd, int newkey, NODEPTR newnode, int pos, NODEPTR &nd2, int &midkey) {
NODEPTR p;
p = GetNode(); /* Tao nut moi chua nut nua phai */
/* Truong hop chen newkey va newnode vào node nua phai */
if (pos > Ndiv2) {
Copy(nd, Ndiv2+1, ORDER - 2, p);
InsNode (p, newkey, newnode, pos-Ndiv2 -1);
nd->NumTree = Ndiv2+1; /* So nhanh cay con con lai cua nut nua trai */
midkey = nd -> Key[Ndiv2];
nd2 = p;
return;
}
/* Truong hop newkey la midkey */
else
if (pos == Ndiv2) {
Copy(nd, Ndiv2, ORDER-2, p);
nd->NumTree = Ndiv2+1; /* So nhanh cay con con lai cua nut nua trai */
/* Hieu chnh lai nut con dau tien cua nut nua phai */
p -> Branch[0] = newnode;
midkey = newkey;
nd2 = p;
return ;
}
/* Truong hop chen newkey va newnode vao nut nua trai */
else
if (pos < Ndiv2) {
Copy(nd, Ndiv2, ORDER-2, p);
nd->NumTree = Ndiv2; /* So nhanh cay con con lai cua nut nua trai */
midkey = nd -> Key[Ndiv2 - 1];
InsNode(nd, newkey, newnode, pos);
nd2 = p;
return;
}
}
Hàm INSNODE
Chèn khóa newkey vào vị trí pos của nút chưa đầy p,và chèn nhánh cây con newnode vào vị trí bên phải của khóa newkey
void InsNode(NODEPTR p, int newkey, NODEPTR newnode, int pos) {
/* Doi cac nhanh con va cac khóa tu vi tri pos tro ve sau tang mot vi tri */
for (int i = p->NumTree - 1; i >= pos+1; i--) {
p -> Branch[i+1] = p -> Branch[i];
p -> Key[i] = p -> Key[i - 1];
}
/* Gan khoa newkey vao vi tri pos */
p -> Key[pos] = newkey;
/* Gan nhanh newnode la nhanh cay con ben phai cua khoa newkey */
p -> Branch[pos + 1] = newnode;
/* Tang so nhanh cay con cua node p len 1 */
p -> NumTree ++;
}
Hàm COPY
Chép các khóa (và nhánh cây con) từ vị trí first đến vị trí last của nút nd (nút nửa trái) sang nút nd2 (nửa nút phải). Hàm này được gọi bởi hàm Split
void Copy(NODEPTR nd, int first, int last, NODEPTR nd2) {
/* Sao chep cac khoa tu nut nd qua nut nd2 */
for (int i = first; i <= last; i++)
nd2 -> Key[i-first] = nd -> Key[i];
/* Sao chep cac nhanh tu nut nd qua nut nd2 */
for (int i = first; i <= last+1; i++)
nd2 -> Branch[i-first] = nd -> Branch[i];
/* So cay con cua nut nd2 */
nd2->NumTree = last - first +2;
}
Hàm FATHER
Tìm nút cha của nút nd, nếu nd là nút gốc trả về giá trị NULL
NODEPTR Father(NODEPTR nd){
NODEPTR p=Root;
int i;
if (p == nd)
return NULL;
else {
i= NodeSearch(p, nd->Key[0]);
/* Vong lap di xuong nhanh con co chua nut nd */
while((p->Branch[i]!=nd)){
p=p->Branch[i];
i= NodeSearch(p, nd->Key[0]);
}
return p;
}
}
Hàm MAKEROOT
Tạo nút mới với khóa k
NODEPTR MakeRoot(int k) {
NODEPTR p;
p=new tagNODE;
p->Key[0]=k;
p->Branch[0]=NULL;
p->Branch[1]=NULL;
p->NumTree=2;
return p;
}
Hàm GETNODE
Tạo nút rỗng
NODEPTR GetNode(){
NODEPTR p;
p=new tagNODE;
p->NumTree=0;
return p;
}
5. Xóa khóa ra khỏi B-Tree
Hàm DELKEY
Xóa một khóa k khỏi B-Tree:
(+) Sử dụng phép toán Search để tìm vị trí khóa k của một nút trên B-Tree (nếu không tìm thấy thì xóa thất bại)
(+) Nếu khóa k ở nút lá, sử dụng phép toán DelLeaf xóa k ở nút lá
(+) Ngược lại nếu khóa k ở nút khác lá, thay thế k bằng khóa tận cùng bên phải của cây con trái vị trí khóa k của nút (hoặc thay thế k bằng khóa tận cùng bên trái của cây con phải vị trí khóa k của nút), sau đó sử dụng phép toán DelLeaf xóa khóa tận cùng bên phải (ở nút lá) đã thay thế khóa k.
void DelKey(int k){
int pos, found;
NODEPTR p=Search(k, pos, found);
/* Khong tim thay khoa k */
if (found==FALSE){
printf("\nKhong tim thay khoa %d de xoa\n",k);
return;
}
/* Truong hop 1: k thuoc nut la */
if (p->Branch[0]==NULL){
DelLeaf(p, pos); /* Xoa khoa o vi tri pos cua nut la p */
}
/* Truong hop 2: k thuoc nut khac la */
else {
/* Tim va thay the k bang phan tu tan cung phai cua cay con trai vi tri pos*/
NODEPTR q=p->Branch[pos];
while (q->Branch[q->NumTree-1]!=NULL){
q=q->Branch[q->NumTree-1];
}
p->Key[pos]=q->Key[q->NumTree-2];
DelLeaf(q,q->NumTree-2); /* Xoa khoa tan cung ben phai cua nut la q */
}
}
Hàm DELLEAF
Xóa một khóa ở nút lá p tại vị trí pos:
(1) Loại bỏ khóa ở nút p tại vị trí pos
(2) Nếu số lượng cây con của p bị thiếu (nhỏ hơn n/2+1) và p khác nút gốc thì thực hện 2.1, ngược lại dừng
(2.1) Nếu có nút anh em kế cận của p dư khóa thì mượn nút anh em kế cận và dừng, ngược lại sang bước 2.2
(2.2) Hợp nhất p với 1 nút anh em kế cận và 1 khóa ở nút cha của p, gán p là nút cha của p, lặp lại bước 2.
void DelLeaf(NODEPTR p, int pos) {
NODEPTR q= Father(p);
int i;
/* Loai bo khoa o vi tri pos */
DelNode(p, pos);
/* Truong hop so cay con cua p < Ndiv2+1 va p dang xet khac nut goc*/
while ((p->NumTree<Ndiv2+1)&&(p!=Root)) {
/* Truong hop 1: muon khoa cua anh em ke can neu co */
i=NodeSearch (q, p->Key[0]);
/* Truong hop nut p la tan cung trai (xoay phai) */
if((i==0)&&(q->Branch[i+1]->NumTree>Ndiv2+1)){
BorrowBrother(q,i);
return;
}
/* Truong hop nut p la tan cung phai (xoay trai) */
if((i==q->NumTree-1)&&(q->Branch[i-1]->NumTree>Ndiv2+1)){
BorrowBrother(q,i-1);
return;
}
/* Truong hop nut p nam giua */
if((i>0)&&(i<q->NumTree-1)) {
/* Truong hop nut ben phai p thua khoa (xoay trai) */
if(q->Branch[i+1]->NumTree>Ndiv2+1) {
BorrowBrother(q,i);
return;
}
/* Truong hop nut ben trai p thua khoa (xoay phai) */
if(q->Branch[i-1]->NumTree>Ndiv2+1){
BorrowBrother(q,i-1);
return;
}
}
/* Truong hop 2: hop nhat 2 nut anh em ke can va 1 khoa o nut cha, xet tiep nut cha */
if (i==q->NumTree-1){
Combine(q,i-1); /* Hop nhat voi nut anh em ke can ben trai */
}
else {
Combine(q,i); /* Hop nhat voi nut anh em ke can ben phai */
}
p=q;
q=Father(p);
}
}
Hàm DELNODE
Loại bỏ 1 khóa và 1 nhánh con ở vị trí pos.
void DelNode(NODEPTR p, int pos) {
/* Doi cac nhanh con va cac khoa tu vi tri pos+1 tro ve sau giam mot vi tri */
for (int i = pos ; i < p->NumTree - 2; i++) {
p -> Branch[i] = p -> Branch[i+1];
p -> Key[i] = p -> Key[i+1];
}
p -> Branch[p->NumTree-2] = p -> Branch[p->NumTree-1];
p -> NumTree--;
}
Hàm BORROWBROTHER
Mượn khóa anh em kế cận và được gọi bởi hàm DelLeaf. Có 2 trường hợp xảy ra:
(+) Trường hợp nút con trái dư khóa thì mượn khóa con trái của nút p ở vị trí pos (xoay phải)
(+) Trường hợp nút con phải dư khóa thì mượn khóa con phải của nút p ở vị trí pos (xoay trái)
void BorrowBrother(NODEPTR p,int pos){
NODEPTR left=p->Branch[pos];
NODEPTR right=p->Branch[pos+1];
/* Truong hop muon ben trai (xoay phai) */
if (left->NumTree>Ndiv2+1){
/* Doi cac nhanh con va cac khoa tu vi tri pos tro ve sau tang mot vi tri tren nut right*/
for (int i = p->NumTree - 1; i >= 0; i--) {
right -> Branch[i+1] = right -> Branch[i];
right -> Key[i] = right -> Key[i - 1];
}
/* chen khoa cua nut cha vao con ben phai,... cap nhat lai 3 nut */
right->Key[0]=p->Key[pos];
right->Branch[0]=left->Branch[left->NumTree-1];
right->NumTree++;
p->Key[pos]=left->Key[left->NumTree-2];
left->NumTree--;
return;
}
/* Truong hop muon ben phai (xoay trai) */
if (right->NumTree>Ndiv2+1){
/* chen khoa cua nut cha vao con ben trai,... cap nhat lai 3 nut */
left->Key[left->NumTree-1]=p->Key[pos];
left->Branch[left->NumTree]=right->Branch[0];
left->NumTree++;
p->Key[pos]=right->Key[0];
/* xoa khoa vi tri 0 cua nut right */
DelNode(right, 0);
}
}
Hàm COMBINE
Hợp nhất khóa ở vị trí pos và nút con pos+1 (right) vào nút con pos (left), được gọi bởi hàm DelLeaf
void Combine(NODEPTR &p, int pos) {
NODEPTR left=p->Branch[pos];
NODEPTR right=p->Branch[pos+1];
/* Them khoa o vi tri pos nut p, cac khoa va nhanh con cua nut right vao nut left */
left->Key[left->NumTree-1]=p->Key[pos];
left->NumTree++;
for(int i=0;i<right->NumTree-1;i++){
left->Key[left->NumTree-1+i]=right->Key[i];
left->Branch[left->NumTree-1+i]=right->Branch[i];
}
left->NumTree=left->NumTree+right->NumTree-1;
left->Branch[left->NumTree-1]=right->Branch[right->NumTree-1];
/* Xoa 1 khoa nut cha p da hop nhat o vi tri pos */
DelNode(p, pos);
/* Gan lai nhanh con cua p o vi tri pos la left va xoa nut right */
p->Branch[pos]=left;
delete right;
/* Truong hop p=Root va so cay con con it hơn 2: xoa nut goc Root va gan Root moi = Left*/
if((p==Root)&&(p->NumTree<2)){
delete Root;
Root=left;
p = Root;
}
}