Chưa có thời gian viết, ở đây có cái khung. Anh chị em nào rỗi thì cứ cái khung này mà phệt, vì đang có việc bận nên bà con thông cảm. Mấy anh chị em trẻ cố gắng tự viết cho nó nhớ, chứ để mấy ông già viết thì cũng kỳ ghê cơ.

Code:

cây B-tree
 
 
/************************************************************************/ 
#define m 3          //Bậc của cây là 3 chẳng hạn
/************************************************************************/ 
 
//Cấu trúc của một Node trong B-Tree
typedef struct NODE
{ 
  int key[m - 1];
  int nKey;      //Số khóa
  NODE *pWay[m];    //Con trỏ đến các nhánh
  NODE *pFather;    //Con trỏ đến nút cha (nếu cần)
  NODE *pLeft;    //Con trỏ đến nút anh em bên trái (nếu cần)
NODE *pRight;    //Con trỏ đến nút anh em bên phải (nếu cần)
}Node;
 
Node *tree;      //B-tree
 
/************************************************************************/ 
/* Hàm khởi tạo cây                            */ 
/************************************************************************/ 
void InitTree()
{
  //Khởi tạo null cho tree
}
 
/************************************************************************/ 
/* Thêm môt khóa mới vào cây                        */ 
/************************************************************************/ 
void InsertElement(int key)
{
  //Thao tác thêm phần tử (Insert): thêm 1 khóa v vào cây
  //  [1] Duyệt cây để tìm kiếm vị trí của v cho đến khi gặp nút lá
//  [2] Nếu nút lá có chứa khóa v thì không thêm, kết thúc hàm Insert
//  ( Gọi nút lá là nút hiện tại)
  //  [3] Thêm khóa v vào nút hiện tại
  //  [4] Nếu nút hiện tại đầy
//    [4.1] Tách nút hiện tại ra làm đôi
//    [4.2] Nếu tồn tại nút cha, chuyển phần tử giữa lên nút cha
//    [4.3] Nếu không (trường hợp ở gốc), tạo một nút cha chưa phần tử đó 
//    [4.4] Cập nhật lại con cho nút cha
//    [4.5] Gọi nút cha là nút hiện tại
//    [4.6] Quay lại [4]
//  [5] Nếu không, kết thúc hàm Insert.
} 
/************************************************************************/ 
/* Tìm kiếm Node chứa khóa                        */ 
/************************************************************************/ 
Node* SearchNode(int key)
{
  //Duyệt cây cho đến khi gặp khóa
  //Trả về con trỏ node chứa khóa
}
 
 
/************************************************************************/ 
/* Xóa một khóa khỏi cây                          */ 
/************************************************************************/ 
void DeleteElement(int key)
{
  // Thao tác xóa phần tử (Delete): xóa 1 khóa v khỏi cây
  //  [1] Duyệt cây, cho đến khi gặp khóa chứa v. Gọi p là khóa chứa v
  //  [2] Nếu không thấy, kết thúc việc xóa.
  //  [3] Nếu v nằm giữa 2 cây con rỗng (v không có cây con) thì xóa phần tử v
  //  [4] Nếu v có cây con, thay thế v bằng: 
  //    - phần tử lớn nhất trong cây con trái của v; đồng thời p trỏ đến node này
  //    - hoặc phần tử bé nhất trong cây con phải của v; đồng thời p trỏ đến node này
//  [5] Nếu p có ít hơn [(m-1)/2] khóa:
//  [5.1] Nếu nút anh em kế cận (trái hoặc phải) có dư khóa, thì “mượn” 1 khóa. Thao tác “mượn” là thao tác xoay trái (nếu mượn bên trái), xoay phải (nếu mượn bên phải). Đi đến bước [6]
//  [5.2] Nếu không, tiến hành “sát nhập” với nút anh em kế cận, cùng với khóa tương ứng ở nút cha
  //    [5.3] p trỏ đến nút cha. Quay lại [5]
  //  [6] Kết thúc
}
 
/************************************************************************/ 
/* Xuất ra file                              */ 
/************************************************************************/ 
void Output(char *filename)
{
  //Duyệt cây theo chiều rộng (BFS - Bread First Search)
  //Ghi lên file theo đặc tả
}
 
/************************************************************************/ 
/* Ngoài ra có thể viết thêm một số hàm như…..                          */ 
/************************************************************************/ 
 
/************************************************************************/ 
/* Xoay trái                        */ 
/************************************************************************/ 
void RotateLeft(Node *p)
{
//….
}
 
/************************************************************************/ 
/* Xoay phải                                      */ 
/************************************************************************/ 
void RotateRight(Node *p)
{
//…. }
 
//…
 
void main()
{
  //Khởi tạo cây
  //Xây dựng cây từ file input
  //Thực hiện quá trình nhập khoá (insert)
  //    quá trình xuất  khoá (delete)
  //In ra file
}
 

[You must be registered and logged in to see this link.]

Quá đẹp!!

Ban QT:
[You must be registered and logged in to see this image.]

Không biết nên viết tiếp thế nào, vì một số người trong chúng ta, Khách viếng thăm có thể không chuyên lắm về C++ (đương nhiên là Khách viếng thăm có thể chuyên về ngôn ngữ khác). Tôi luôn có một mong muốn để mọi người trong lớp càng hiểu rõ hơn càng tốt. Thôi thì mình tiên phong gõ một ít ra đây vậy, nếu có gì thiếu thì Khách viếng thăm hãy bổ sung, hoặc làm rõ hơn nhé. Đừng thụ động để người khác gõ, mình copy thì những gì vào đầu sẽ nhanh vuột mất, thiên hạ vẫn nói vậy.

Đầu tiên, chúng ta cần có một định nghĩa chuẩn theo thầy đã.

Cấu trúc và tham số ban đầu của nút hiện tại sẽ như thế này:
define ORDER 3 //Bậc của nút sẽ là 3. Đương nhiên, nếu thay số 3 = 5 thì...

const int B = 2 * ORDER; // Số nhánh tối đa tại một nút, vậy trường hợp này sẽ là 6
// Ta viết int là chỉ hằng số nguyên, việc dùng công thức để khi chỉnh bậc ở chỗ,
//thì các hằng như B sẽ tự cập nhật giá trị mới, không phải mất công đi chỉnh từng chỗ một

const int MAXKEYS = B - 1//Số key tối đa của 1 nút, đương nhiên nút hiện tại cũng vậy

Typedef int KEY;//Khai báo một kiểu dữ liệu số nguyên KEY;

struct tree_node{
//Cấu trúc của nút để tiện truy cập các thành phần và kết nối của nó

int NumKeys;//Số khoá hiện tại của nút đang xét, tính là số nguyên

bool leaf;//Cờ hiệu của nút để xác định, nút đang xét có phải là lá không; nếu là lá, giá trị TRUE

KEY key[MAXKEYS];//khoá key chỉ có thể nhận được từ 0,1.. MAXKEYS - 1

tree_node * branch [B];//Con trỏ chỉ nhánh tiếp theo có số hiệu từ 1 đến B

          tree_node(){

          //Nào hãy tự giải thích nhé

          NumKeys = 0;

          leaf = false;

          FOR (int i = 0; i < B; i++) {

                              branch [i] = NULL;

                    }

          }

Bi giờ viết ra đây để Khách viếng thăm trả lời giúp tôi nhé:

Nếu nút chứa khoá cần xoá là delete_node, khoá cần xoá là khoá thứ i trong delete_node thì:

delete_node → Key[i] là gì?

delete_node → branch[i] là gì?

Trời, dễ như ăn bún vậy.

Nếu nút trái của nút hiện tại đang xét là left_node thì:

left_node → branch[left_node → numKeys - 1] và left_node → numKeys[numKeys - 1] cái nào viết đúng và nó là cái gì nhỉ?

left_node → numKeys [left_node → numKeys] là gì nhỉ?

left_node → branch[left_node → numKeys - 1] → NumKeys là cái gì?

Nếu Khách viếng thăm trả lời hết mới bàn tiếp nhé, nếu không ai trả lời, nghĩa là tất cả chúng ta đều đã biết hết cả và... close topic để dành thời gian bàn việc khác.

Hic em cũng cố gắng làm nhưng mà làm vất vả quá. Lâu nay chỉ là thợ code chứ có bao giờ để ý đến cái này đâu.
Thôi thì cũng xác định lấy tập thể làm đầu và tiêu chí là "CHIA SẺ DÙ ĐÚNG HAY SAI". Sai thì mọi người góp ý.

Em viết 1 chương trình B-TRee đúng theo kiểu của slide.

Hiện tại em mới làm được có chức năng thêm mới cây và duyệt cây.

Hiển thị cây em không biết ý tưởng nào hay. Ai có ý tưởng hay có thể trao đổi em sẽ viết.

Xóa cây em chưa rõ thuật toán lắm nên chưa viết.
Bác Cường vào trình bày thuật toán trên giấy em hiểu được thì em sẽ viết thành chương trình được.

Chương trình em kiểm tra đúng với >30 số. Nhiều hơn thì chưa biết ( viết hơi gấp nên cũng không dám chắc)

Ai có nhu cầu cần cài đặt hoặc source code cụ thể liên hệ với em ta thảo luận.

Code:


/*
   Dựng cây theo hướng dẫn của thầy hùng
   Các phương thức viết
   B-TREE-SEARCH
   B-TREE-CREATE
   B-TREE-INSERT
   B-TREE-DELETE
*/
/*
   Đính kèm thư viện
*/
#include <iostream>
using namespace std;
//Định nghĩa các biến constant
#define ORDER 3 //Bậc của cây
const int B=2*ORDER;//So nhanh cua cay
const int MAXKEYS=B-1;// So khoa toi da tren 1 nut

typedef int KEY;
struct Tree_Node
{
   int NumKeys;//So khoa hien thoi
   bool Leaf; //La la hay khong
   KEY Key[MAXKEYS];//0,1,2...,B-1
   Tree_Node * Branch [B];//Con trỏ chỉ nhánh tiếp theo có số hiệu từ 0 đến B-1
   Tree_Node()//Ham khoi tao
   {
          //Nào hãy tự giải thích nhé
          NumKeys = 0;
          Leaf = true;
          FOR (int i = 0; i < B; i++)
            Branch [i] = NULL;
    }
};
// Ham trim kiem tren cay
bool B_TREE_SEARCH(Tree_Node *Root,KEY K, Tree_Node *NodeFound,int *Index)
{
   //Bien duyet ( lay tu 0)
   int i=0;
   WHILE(i<Root->NumKeys && K>Root->NumKeys)
      i++;
   // Neu tim thay khoa
   if(i<Root->NumKeys&&K==Root->Key[i])
   {
      NodeFound=Root;
      *Index=i;
      return true;
   }
   // Neu khong tim thay khoa
   // Neu la khoa
   if(Root->Leaf)
      return false;
   // Neu khong la khoa tim de qui
   return(Root->Branch[i],K,NodeFound,Index);
}
//Ham chia tach cay
//Tach nut y thanh 2 nut va chinh x de x co them mot nut con
void B_TREE_SPLIT_CHILD(Tree_Node *x,int Index,Tree_Node *y)
{
   // Tao nut de tach nut y
   Tree_Node *z=new Tree_Node();
   z->Leaf=y->Leaf;
   z->NumKeys=ORDER-1;
   //Dieu chinh z
   // Lay cac khoa cua nua ben phai nut y de gan cho z
   FOR(int i=0;i<ORDER-1;i++)
      z->Key[i]=y->Key[ORDER+i];
   // Neu y khong la la gan cac con tro z
   if(!y->Leaf)
      FOR(int i=0;i<ORDER;i++)
         z->Branch[i]=y->Branch[ORDER+i];
   // Xong dieu chinh z
   // Dieu chinh y
   y->NumKeys=ORDER-1;
   // Dieu chinh x
   // Dieu chinh cac nhanh dich ben phai so voi Index
   FOR(int i=x->NumKeys;i>Index+1;i--)
   {
      x->Branch[i]=x->Branch[i-1];
   }
   x->Branch[Index+1]=z;
   x->Branch[Index]=y;
   // Dieu chinh khoa
   FOR(int i=x->NumKeys;i>Index;i--)
   {
      x->Key[i]=x->Key[i-1];
   }
   // Gan y cho con index cua x
   x->Key[Index]=y->Key[ORDER-1];
   // Tang khoa cua x
   x->NumKeys++;
}
// Chen du lieu vao cay co goc khong day
void B_TREE_INSERT_NONFULL(Tree_Node *&Root,KEY K)
{
   int iNumkeys=Root->NumKeys-1;
   if(Root->Leaf)
   {
      // La nut la thi them vao
      WHILE(iNumkeys>0&&K<Root->Key[iNumkeys])// Day dan sang ben phai de chen khoa K vao
      {
         Root->Key[iNumkeys+1]=Root->Key[iNumkeys];
         iNumkeys--;
      }
      // Ket thuc vong lap iNumkeys chinh la cho chen k
      Root->Key[iNumkeys+1]=K;
      Root->NumKeys++;
      return;
   }
   ELSE // Neu khong la nut la chung ta se tim vi tri de di xuong duoi
   {
      WHILE(iNumkeys>0&&K<Root->Key[iNumkeys])// Tim vi tri de di xuong
         iNumkeys--;
   }
   iNumkeys++;
   // Neu con la nut day thi thuc hien chia tach
   if(Root->Branch[iNumkeys]->NumKeys==   MAXKEYS   )
   {
      B_TREE_SPLIT_CHILD  (Root,iNumkeys,Root->Branch[iNumkeys]);
      // Sau khi chia tach thi chung ta se xem la di xuong huong nao de chen
      if(   K>Root->Key[iNumkeys])
         iNumkeys++;
   }
   B_TREE_INSERT_NONFULL(Root->Branch[iNumkeys],K);
}
// Ham insert mot nut vao cay
void B_TREE_INSERT(Tree_Node *&Root,KEY K)
{
   if(Root->NumKeys==0)
   {
      Root->NumKeys=1;
      Root->Key[0]=K;
      return;
   }
   Tree_Node *r=Root;
   // Neu nut goc day
   if(r->NumKeys==MAXKEYS)// Tach goc
   {
      // Gan mot nut moi
      Tree_Node *s=new Tree_Node();
      Root=s;
      s->Leaf=false;
      s->NumKeys=0;
      s->Branch[0]=r;
      // Cay moi cua chung ta da co goc khong day
      // Chung ta chia tach nut
      B_TREE_SPLIT_CHILD(s,0,r);
      B_TREE_INSERT_NONFULL(s,K);
   }
   ELSE
      B_TREE_INSERT_NONFULL(r,K);
}
// Hien thi cay
void B_TREE_SHOW(Tree_Node *Root)
{
   FOR (int i=0; i<Root->NumKeys; i++)
      cout<<Root->Key[i]<<" ";
    cout<<endl;
}
void main()
{
   int choice,item;
   Tree_Node *Root;
   Root=new Tree_Node();
   cout << "CHUONG TRINH BTREE THAY HUNG DAY\n"   ;
        cout << "==========================================="  << "\n\n\n";
   cout << "1:Nhap gia tri vao cay\n";
   cout << "2:Hien thi cay\n";
   cout << "10:Thoat\n";
   
   WHILE(1)
        {
      /*
      cout << "Nhap vao lua chon cua ban:";
        cin >> choice;
      switch(choice)
        {
         case 1: cout << "Nhap gia tri :";
               cin >> item;
               B_TREE_INSERT(Root,item);
               break;
         case 2:   B_TREE_SHOW(Root);     break;
         case 3: break;
         default:break;
      }*/
      cout << "Nhap gia tri : ";
               cin >> item;
               B_TREE_INSERT(Root,item);
      cout <<   "\n";
   }
}




Bác Admin hỏi thì em xin trả lời (theo ý hiểu của em), ở đây mạn phép em cũng trả lời tựa giải thuật nhé (ngôn ngữ C++ em cũng không làm nhiều, có gì ko đúng bác chỉnh sửa cho em).

1. delete_node → Key[i] là gì?
Đây là thao tác ta phải thực hiện xóa khóa Key[i] (tương ứng với chỉ mục i+1 trong nút delete_node).
Để thực hiện được thao tác này, chúng ta phải xét các trường hợp sau:
i) nút delete_node là nút lá
{
KEY K=left_node → Key[numKeys-1];
left_node → numKeys = left_node → numKeys -1;
return K;
}
ii) nút delete_node là một nút trong
Trong trường hợp này, bạn cũng phải quan tâm tới 2 trường hợp:
- nút delete_node có số khóa tối thiểu: delete_node → numKeys = ORDER - 1;
{
...
}
- nút delete_node có số khóa lớn hơn số khóa tối thiểu: delete_node → numKeys > ORDER -
{
...
}

2. delete_node → branch[i] là gì?
Đây là thao tác ta đi xuống nhánh con [i] từ nút delete_node


3. Nếu nút trái của nút hiện tại đang xét là left_node thì:

a>left_node → branch[left_node → numKeys - 1] và left_node → numKeys[numKeys - 1] cái nào viết đúng và nó là cái gì nhỉ?

Ta phải viết: left_node → branch[left_node → numKeys - 1]
Tức là ta xuống nhánh con có chỉ số (left_node → numKeys - 1) từ nút left_node.

b> left_node → numKeys [left_node → numKeys] là gì nhỉ?
Câu hỏi này không rõ?


c>left_node → branch[left_node → numKeys - 1] → NumKeys là cái gì?
Cho biết số khóa hiện thời của nhánh con [left_node → numKeys - 1] của nút left_node.


Em mạo muội trả lời như zậy, sai sót chỗ nào các pác sửa dùm cho nhé! Tôi luôn cầu thị trong học tập.

Cuong01111 đã viết:1. delete_node → Key[i] là gì?
Đây là thao tác ta phải thực hiện xóa khóa Key[i] (tương ứng với chỉ mục i+1 trong nút delete_node).

Theo em hình như bác nhầm từ đầu thì phải. Em nghĩ nếu delete_node là một nút, thì:
delete_node → Key phải là phần truy cập đến khoá của nút đó (tức là nút delete_node)
Vậy delete_node → Key[i] chính là truy cập đến khoá [i] nằm trong nút delete_node

Cuong01111 đã viết:

2. delete_node → branch[i] là gì?
Đây là thao tác ta đi xuống nhánh con [i] từ nút delete_node

Em nghĩ đây không phải là thao tác, mà là truy cập đến nút con thứ i của delete_node

Cuong01111 đã viết:
3. Nếu nút trái của nút hiện tại đang xét là left_node thì:

a>left_node → branch[left_node → numKeys - 1] và left_node → numKeys[numKeys - 1] cái nào viết đúng và nó là cái gì nhỉ?

Ta phải viết: left_node → branch[left_node → numKeys - 1]
Tức là ta xuống nhánh con có chỉ số (left_node → numKeys - 1) từ nút left_node.

Theo em không phải đi xuống mà là chỉ rõ nút con thứ (left_node → numKeys - 1) của nút left_node, vì (left_node → numKeys - 1) chính là khoá cuối cùng trong tổng số khoá của left_node, vậy đó chính là nút phải cùng trong số con của left_node
Hay nói chính xác là Admin muốn bảo left_node → branch[left_node → numKeys - 1] là nút phải cùng trong số các con của nút left_node.

Admin đã viết:
b> left_node → numKeys [left_node → numKeys] là gì nhỉ?

Cuong01111 đã viết:
Câu hỏi này không rõ?

left_node → numKeys chính là số lượng Key của nút left_node, nên có thể coi câu hỏi của Admin nghĩa là left_node → numKeys[số = số lượng Key] chính là khoá cuối cùng trong nút left_node

Cuong01111 đã viết:
c>left_node → branch[left_node → numKeys - 1] → NumKeys là cái gì?
Cho biết số khóa hiện thời của nhánh con [left_node → numKeys - 1] của nút left_node.

Do left_node → branch[left_node → numKeys - 1] là nút con phải cùng của left_node, nên left_node → branch[left_node → numKeys - 1] → NumKeys là số lượng khoá của nút con phải cùng của nút left_node.

Em xin phép được sửa lại đôi chút, mong các cao nhân chỉ giáo cho.

Em không được học ở lớp CNTT1, nên không có tên trong danh sách của các anh chị ạ.