Chương trình C ++ để thực hiện sắp xếp bằng B-Tree

Ở đây chúng ta sẽ xem cách lấy chuỗi đã sắp xếp bằng cách sử dụng B-Tree. Cây B là cây n-ary. Để có được các chuỗi đã được sắp xếp, chúng ta có thể tạo một cây B, sau đó thêm các số vào đó. Ở đây cây B có thể chứa tối đa 5 nút. Nếu số lượng nút tăng lên, hãy tách nút và tạo thành cấp độ mới. Vì các nút đang chứa ít phần tử như 5 (nhiều nhất), chúng tôi đang sử dụng kỹ thuật sắp xếp Bong bóng để sắp xếp chúng. vì số lượng phần tử rất thấp nên nó sẽ không ảnh hưởng quá nhiều đến hiệu suất của nó.

Sau khi duyệt qua cây, chúng ta sẽ nhận được tất cả các giá trị của các nút khác nhau. Các yếu tố này sẽ được sắp xếp theo thứ tự không giảm dần.

Thuật toán

traverse (p)

Đầu vào:Nút cây p
Đầu ra:Trình tự duyệt của cây

 Bắt đầu cho tôi trong phạm vi từ 0 đến n-1, thực hiện nếu p không phải là nút lá, sau đó duyệt (con của p ở vị trí i) kết thúc nếu in dữ liệu ở vị trí tôi thực hiện nếu p không phải là nút lá, sau đó đi ngang (con của p ở vị trí i) kết thúc ifEnd 

sort (a, n)

Đầu vào Lấy mảng a, sẽ được sắp xếp, số phần tử trong mảng đó, là n

Đầu ra:Mảng đã sắp xếp

 Bắt đầu cho tôi trong phạm vi 0 đến n-1, thực hiện cho j trong phạm vi 0 đến n-1, thực hiện nếu a [i]> a [j], sau đó hoán đổi a [i] và [j] kết thúc nếu thực hiện xongEnd 

split_node (x, i):

Đầu vào:Nút x được tách, tôi sẽ là (-1) cho nút lá, nếu không thì một số giá trị dương

Đầu ra:Phần tử giữa của Node sau khi tách

 Begin Tạo một nút np3 và đánh dấu nó là nút lá nếu i là -1, sau đó là mid:=Dữ liệu từ vị trí 2 của x Đặt dữ liệu ở vị trí 2 của x thành 0 Giảm số dữ liệu trong x đi 1 tạo một nút mới gọi là np1 và đánh dấu nó là nút không phải là nút. Đánh dấu x là nút lá Chèn tất cả các nút của x từ vị trí 3 đến 5 vào np3 Đồng thời chèn tất cả tham chiếu con của x từ vị trí 3 đến 5 vào np3 Xóa các phần tử đã chèn khỏi nút x chèn giữa vào vị trí đầu tiên của np1, đặt x là con bên trái và np3 là con bên phải của np1 tăng số phần tử của np1 và đặt nó là gốc. else y:=cây con ở vị trí i mid:=dữ liệu từ vị trí 2 của y Đặt dữ liệu ở vị trí 2 của y thành 0 Giảm số dữ liệu trong y đi 1 Chèn tất cả các nút của y từ vị trí 3 đến 5 vào np3 tăng số phần tử lên np3 và xóa các phần tử đã chèn từ y thêm phần tử con ở vị trí i và thêm np3 ở vị trí i + 1 kết thúc ifEnd 

insert (a):

Đầu vào:Một phần tử a, sẽ được chèn vào.

Đầu ra:B-Tree cập nhật

 Begin x:=root nếu x là null, sau đó tạo một nút gốc và lấy root thành x else nếu x là nút lá và có 5 phần tử, sau đó temp_node:=split_child (x, -1) x:=root i:=tìm đúng vị trí để chèn x:=con của x ở vị trí khác trong khi x không phải là nút lá, hãy làm i:=tìm đúng vị trí để chèn if con của x ở vị trí i, có 5 phần tử, sau đó temp_node :=split_child (x, i) thêm dữ liệu temp_node ở vị trí x-> n của x else x:=con của x ở vị trí tôi kết thúc nếu kết thúc nếu kết thúc nếu thêm a vào x ở vị trí x-> n sắp xếp các phần tử của xEnd 

Mã mẫu

 #include  using namespace std; struct BTreeNode {// tạo cấu trúc nút của dữ liệu B-tree int *; BTreeNode ** child_ptr; lá bool; int n;} * root =NULL, * np =NULL, * x =NULL; BTreeNode * getNode () {int i; np =new BTreeNode; np-> data =new int [5]; // thiết lập 5 vòng dữ liệu và 6 trường liên kết np-> child_ptr =new BTreeNode * [6]; np-> leaf =true; // ban đầu nút là một lá np-> n =0; for (i =0; i <6; i ++) {np-> con_ptr [i] =NULL; // khởi tạo tất cả con trỏ thành null} return np;} void traverse (BTreeNode * p) {cout < n; i ++) {// duyệt đệ quy toàn bộ cây b if (p-> leaf ==false) {traverse (p-> child_ptr [i]); } cout <<"" < data [i]; } if (p-> leaf ==false) {traverse (p-> child_ptr [i]); } cout < p [j]) {swap (p [i], p [j]); }}}} int split_child (BTreeNode * x, int i) {// chia nút thành ba nút, một gốc và hai nút con int mid; BTreeNode * np1, * np3, * y; np3 =getNode (); // tạo một nút lá mới có tên np3 np3-> leaf =true; if (i ==-1) {mid =x-> data [2]; // lấy phần tử ở giữa x-> data [2] =0; x-> n--; np1 =getNode (); np1-> leaf =false; x-> lá =true; for (int j =3; j <5; j ++) {np3-> data [j - 3] =x-> data [j]; np3-> con_ptr [j - 3] =x-> con_ptr [j]; np3-> n ++; x-> dữ liệu [j] =0; x-> n--; } for (int j =0; j <6; j ++) {x-> con_ptr [j] =NULL; } np1-> data [0] =mid; np1-> con_ptr [np1-> n] =x; np1-> con_ptr [np1-> n + 1] =np3; np1-> n ++; root =np1; } else {y =x-> con_ptr [i]; mid =y-> data [2]; y-> dữ liệu [2] =0; y-> n--; for (int j =3; j <5; j ++) {np3-> data [j - 3] =y-> data [j]; np3-> n ++; y-> dữ liệu [j] =0; y-> n--; } x-> con_ptr [i] =y; x-> con_ptr [i + 1] =np3; } return mid;} void insert (int a) {// chèn vào BTree int i, tmp_node; x =gốc; if (x ==NULL) {root =getNode (); x =gốc; } else {if (x-> leaf ==true &&x-> n ==5) {// khi nút là nút lá và có 5 dữ liệu tmp_node =split_child (x, -1); // tạo một cấp độ mới bằng cách tách nút x =root; for (i =0; i <(x-> n); i ++) {if ((a> x-> data [i]) &&(a  data [i + 1])) {i ++; phá vỡ; } else if (a  data [0]) {break; } else {tiếp tục; }} x =x-> con_ptr [i]; } else {while (x-> leaf ==false) {for (i =0; i <(x-> n); i ++) {if ((a> x-> data [i]) &&(a  dữ liệu [i + 1])) {i ++; phá vỡ; } else if (a  data [0]) {break; } else {tiếp tục; }} if ((x-> child_ptr [i]) -> n ==5) {tmp_node =split_child (x, i); x-> data [x-> n] =tmp_node; x-> n ++; tiếp tục; } else {x =x-> con_ptr [i]; }}}} x-> data [x-> n] =a; sort (x-> dữ liệu, x-> n); x-> n ++;} int main () {int i, n, t; cout <<"nhập số phần tử sẽ được chèn \ n"; cin>> n; for (i =0; i > t; chèn (t); } cout <<"ngang qua cây đã xây dựng \ n"; traverse (gốc);} 

Đầu ra