โปรแกรม C++ เพื่อใช้งาน B+ Tree

ต้นไม้ B+ เป็นลักษณะทั่วไปของแผนผังการค้นหาแบบไบนารีโดยที่โหนดสามารถมีลูกได้มากกว่าสองคน โดยพื้นฐานแล้วจะเป็นโครงสร้างข้อมูลทรีแบบสมดุลในตัวเอง ซึ่งจะรักษาข้อมูลที่จัดเรียงไว้ และอนุญาตให้เข้าถึงตามลำดับ การค้นหา การแทรก และการลบตามเวลาลอการิทึม

สามารถดูได้ว่าเป็น B-tree ซึ่งแต่ละโหนดมีเพียงคีย์เท่านั้นและมีการเพิ่มระดับเพิ่มเติมที่ด้านล่างด้วยใบไม้ที่เชื่อมโยง

อัลกอริทึม

เริ่มต้นฟังก์ชัน insert() เพื่อแทรกโหนดลงในทรี:เริ่มต้น x เป็นรูท ถ้า x เป็นลีฟ และมีพื้นที่สำหรับข้อมูลเพิ่มเติม ให้ใส่ a ถึง x มิฉะนั้น ถ้า x ไม่ใช่ใบไม้ ให้ค้นหาลูกของ x ที่จะข้ามต่อไป หากเด็กไม่อิ่ม ให้เปลี่ยน x ให้ชี้ไปที่เด็ก หากเด็กเต็ม ให้แยกออกแล้วเปลี่ยน x ให้ชี้ไปที่ส่วนใดส่วนหนึ่งของเด็ก หาก a น้อยกว่าคีย์กลางในคีย์ย่อย ให้ตั้งค่า x เป็นส่วนแรกของคีย์ย่อย ส่วนที่สองของเด็กจบ

โค้ดตัวอย่าง

#includeใช้เนมสเปซ std;struct BplusTree { int *d; BplusTree **child_ptr; บูล l; int n;}*r =NULL, *np =NULL, *x =NULL;BplusTree* init()//เพื่อสร้างโหนด { int i; np =ใหม่ BplusTree; np->d =new int[6];//order 6 np->child_ptr =ใหม่ BplusTree *[7]; np->l =จริง; np->n =0; สำหรับ (i =0; i <7; i++) { np->child_ptr[i] =NULL; } กลับ np;} การเคลื่อนที่เป็นโมฆะ (BplusTree * p) // สำรวจต้นไม้ { cout<n; i++) { if (p->l ==false) { traverse(p->child_ptr[i]); } cout <<" " <d[i]; } if (p->l ==false) { traverse(p->child_ptr[i]); } cout<p[j]) { t =p[i]; p[i] =p[j]; p[j] =t; } } }}int split_child (BplusTree *x, int i) { int j, กลาง; BplusTree *np1, *np3, *y; np3 =เริ่มต้น (); np3->l =จริง; ถ้า (i ==-1) { กลาง =x->d[2]; x->d[2] =0; x->n--; np1 =เริ่มต้น (); np1->l =เท็จ; x->l =จริง; สำหรับ (j =3; j <6; j++) { np3->d[j - 3] =x->d[j]; np3->child_ptr[j - 3] =x->child_ptr[j]; np3->n++; x->d[j] =0; x->n--; } สำหรับ (j =0; j <6; j++) { x->child_ptr[j] =NULL; } np1->d[0] =กลาง; np1->child_ptr[np1->n] =x; np1->child_ptr[np1->n + 1] =np3; np1->n++; r =np1; } อื่น ๆ { y =x->child_ptr[i]; กลาง =y->d[2]; y->d[2] =0; y->n--; สำหรับ (j =3; j <6; j++) { np3->d[j - 3] =y->d[j]; np3->n++; y->d[j] =0; y->n--; } x->child_ptr[i + 1] =y; x->child_ptr[i + 1] =np3; } return mid;} โมฆะการแทรก (int a) { int i, t; x =ร; ถ้า (x ==NULL) { r =init(); x =ร; } อื่น { ถ้า (x->l==จริง &&x->n ==6) { t =split_child(x, -1); x =ร; สำหรับ (i =0; i <(x->n); i++) { if ((a>x->d[i]) &&(a d[i + 1])) { i++; หยุดพัก; } else if (a d[0]) { แตก; } อื่น ๆ { ดำเนินการต่อ; } } x =x->child_ptr[i]; } อื่น { ในขณะที่ (x->l ==false) { สำหรับ (i =0; i <(x->n); i++) { if ((a>x->d[i]) &&(a d[i + 1])) { i++; หยุดพัก; } else if (a d[0]) { แตก; } อื่น ๆ { ดำเนินการต่อ; } } if ((x->child_ptr[i])->n ==6) { t =split_child(x, i); x->d[x->n] =t; x->n++; ดำเนินต่อ; } อื่น ๆ { x =x->child_ptr[i]; } } }} x->d[x->n] =a; sort(x->d, x->n); x->n++;}int main() { int i, n, t; cout<<"ใส่จำนวนองค์ประกอบที่จะแทรก\n"; ซิน>>น; for(i =0; i >ที; แทรก (t); } cout<<"การข้ามของต้นไม้ B ที่สร้างขึ้น\n"; traverse(r);}

ผลลัพธ์

ป้อนหมายเลของค์ประกอบที่จะแทรก10ป้อนองค์ประกอบ10ป้อนองค์ประกอบ20ป้อนองค์ประกอบ30ป้อนองค์ประกอบ40ป้อนองค์ประกอบ50ป้อนองค์ประกอบ60ป้อนองค์ประกอบ70ป้อนองค์ประกอบ80ป้อนองค์ประกอบ90ป้อนองค์ประกอบ100ข้ามผ่านต้นไม้ที่สร้างขึ้น B 10 203040 506070 80 90 100