-
编程语言
站-
热门城市 全国站>
-
其他省市
-
-
400-636-0069
小标
2018-07-20
来源 ：
阅读 2231
评论 0
摘要：本文主要向大家介绍了C++语言模板实现B+树，通过具体的内容向大家展示，希望对大家学习C++语言有所帮助。
本文主要向大家介绍了C++语言模板实现B+树，通过具体的内容向大家展示，希望对大家学习C++语言有所帮助。
B+ 树是一种树数据结构，是一个n叉排序树，每个节点通常有多个孩子，一棵B+树包含根节点、内部节点和叶子节点。根节点可能是一个叶子节点，也可能是一个包含两个或两个以上孩子节点的节点。
B+ 树通常用于数据库和操作系统的文件系统中。NTFS, ReiserFS, NSS, XFS, JFS, ReFS 和BFS等文件系统都在使用B+树作为元数据索引。B+ 树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。B+ 树元素自底向上插入
B+树的定义:B+树是应文件系统所需而出的一种B-树的变型树。一棵m阶的B+树和m阶的B-树的差异在于：
1.有n棵子树的结点中含有n个关键字，每个关键字不保存数据，只用来索引，所有数据都保存在叶子节点。
2.所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
3.所有的非终端结点可以看成是索引部分，结点中仅含其子树（根结点）中的最大（或最小）关键字。
通常在B+树上有两个头指针，一个指向根结点，一个指向关键字最小的叶子结点。
下面我们使用模板简单实现B+树：
BTreeNode.h
[cpp] view plain copy print?
1. template<typename Type> class BTree;
2.
3. template<typename Type> class BTreeNode{
4. public:
5. friend BTree<Type>;
6. BTreeNode(): m_nMaxSize(0), m_ptr(NULL), m_pparent(NULL){}
7. BTreeNode(int size): m_nsize(0), m_nMaxSize(size), m_pparent(NULL){
8. m_pkey = new Type[size+1];
9. m_ptr = new BTreeNode<Type> *[size+1];
10. for (int i=0; i<=size; i++){
11. m_ptr[i] = NULL;
12. m_pkey[i] = this->m_Infinity;
13. }
14. }
15. void Destroy(BTreeNode<Type> *root);
16. ~BTreeNode(){
17. if (m_nMaxSize){
18. delete[] m_pkey;
19. for (int i=0; i<=m_nMaxSize; i++){
20. m_ptr[i] = NULL;
21. }
22. }
23. }
24. bool IsFull(){
25. return m_nsize == m_nMaxSize;
26. }
27. Type GetKey(int i){
28. if (this){
29. return this->m_pkey[i];
30. }
31. return -1;
32. }
33.
34. private:
35. int m_nsize;
36. int m_nMaxSize; //the Max Size of key
37. Type *m_pkey;
38. BTreeNode<Type> *m_pparent;
39. BTreeNode<Type> **m_ptr;
40. static const Type m_Infinity = 10000;
41. };
42.
43. template<typename Type> struct Triple{
44. BTreeNode<Type> *m_pfind;
45. int m_nfind;
46. bool m_ntag;
47. };
48.
49. template<typename Type> void BTreeNode<Type>::Destroy(BTreeNode<Type> *root){
50. if (NULL == root){
51. return;
52. }
53. for (int i=0; i<root->m_nsize; i++){
54. Destroy(root->m_ptr[i]);
55. }
56. delete root;
57. }
BTree.h
[cpp] view plain copy print?
1. #include "BTreeNode.h"
2.
3. template<typename Type> class BTree{
4. public:
5. BTree(int size): m_nMaxSize(size), m_proot(NULL){}
6. ~BTree();
7. Triple<Type> Search(const Type item);
8. int Size();
9. int Size(BTreeNode<Type> *root);
10. bool Insert(const Type item); //insert item
11. bool Remove(const Type item); //delete item
12. void Print(); //print the BTree
13. BTreeNode<Type> *GetParent(const Type item);
14.
15. private:
16. //insert the pright and item to pinsert in the nth place;
17. void InsertKey(BTreeNode<Type> *pinsert, int n, const Type item, BTreeNode<Type> *pright);
18.
19. void PreMove(BTreeNode<Type> *root, int n); //move ahead
20.
21. //merge the child tree
22. void Merge(BTreeNode<Type> *pleft, BTreeNode<Type> *pparent, BTreeNode<Type> *pright, int n);
23.
24. //adjust with the parent and the left child tree
25. void LeftAdjust(BTreeNode<Type> *pright, BTreeNode<Type> *pparent, int min, int n);
26.
27. //adjust with the parent and the left child tree
28. void RightAdjust(BTreeNode<Type> *pleft, BTreeNode<Type> *pparent, int min, int n);
29.
30. void Print(BTreeNode<Type> *start, int n = 0);
31.
32. private:
33. BTreeNode<Type> *m_proot;
34. const int m_nMaxSize;
35. };
36.
37.
38. template<typename Type> BTree<Type>::~BTree(){
39. m_proot->Destroy(m_proot);
40. }
41. template<typename Type> Triple<Type> BTree<Type>::Search(const Type item){
42. Triple<Type> result;
43. BTreeNode<Type> *pmove = m_proot, *parent = NULL;
44. int i = 0;
45. while (pmove){
46. i = -1;
47. while (item > pmove->m_pkey[++i]); //find the suit position
48. if (pmove->m_pkey[i] == item){
49. result.m_pfind = pmove;
50. result.m_nfind = i;
51. result.m_ntag = 1;
52. return result;
53. }
54. parent = pmove;
55. pmove = pmove->m_ptr[i]; //find in the child tree
56. }
57. result.m_pfind = parent;
58. result.m_nfind = i;
59. result.m_ntag = 0;
60. return result;
61. }
62.
63. template<typename Type> void BTree<Type>::InsertKey(BTreeNode<Type> *pinsert, int n, const Type item, BTreeNode<Type> *pright){
64. pinsert->m_nsize++;
65. for (int i=pinsert->m_nsize; i>n; i--){
66. pinsert->m_pkey[i] = pinsert->m_pkey[i-1];
67. pinsert->m_ptr[i+1] = pinsert->m_ptr[i];
68. }
69. pinsert->m_pkey[n] = item;
70. pinsert->m_ptr[n+1] = pright;
71.
72. if (pinsert->m_ptr[n+1]){ //change the right child tree's parent
73. pinsert->m_ptr[n+1]->m_pparent = pinsert;
74. for (int i=0; i<=pinsert->m_ptr[n+1]->m_nsize; i++){
75. if (pinsert->m_ptr[n+1]->m_ptr[i]){
76. pinsert->m_ptr[n+1]->m_ptr[i]->m_pparent = pinsert->m_ptr[n+1];
77. }
78. }
79. }
80.
81. }
82. template<typename Type> bool BTree<Type>::Insert(const Type item){
83. if (NULL == m_proot){ //insert the first node
84. m_proot = new BTreeNode<Type>(m_nMaxSize);
85. m_proot->m_nsize = 1;
86. m_proot->m_pkey[1] = m_proot->m_pkey[0];
87. m_proot->m_pkey[0] = item;
88. m_proot->m_ptr[0] = m_proot->m_ptr[1] =NULL;
89. return 1;
90. }
91. Triple<Type> find = this->Search(item); //search the position
92. if (find.m_ntag){
93. cerr << "The item is exist!" << endl;
94. return 0;
95. }
96. BTreeNode<Type> *pinsert = find.m_pfind, *newnode;
97. BTreeNode<Type> *pright = NULL, *pparent;
98. Type key = item;
99. int n = find.m_nfind;
100.
101. while (1){
102. if (pinsert->m_nsize < pinsert->m_nMaxSize-1){ //There is some space
103. InsertKey(pinsert, n, key, pright);
104. return 1;
105. }
106.
107. int m = (pinsert->m_nsize + 1) / 2; //get the middle item
108. InsertKey(pinsert, n, key, pright); //insert first, then break up
109. newnode = new BTreeNode<Type>(this->m_nMaxSize);//create the newnode for break up
110.
111. //break up
112. for (int i=m+1; i<=pinsert->m_nsize; i++){
113. newnode->m_pkey[i-m-1] = pinsert->m_pkey[i];
114. newnode->m_ptr[i-m-1] = pinsert->m_ptr[i];
115. pinsert->m_pkey[i] = pinsert->m_Infinity;
116. pinsert->m_ptr[i] = NULL;
117. }
118. newnode->m_nsize = pinsert->m_nsize - m - 1;
119. pinsert->m_nsize = m;
120.
121. for (int i=0; i<=newnode->m_nsize; i++){ //change the parent
122. if (newnode->m_ptr[i]){
123. newnode->m_ptr[i]->m_pparent = newnode;
124. for (int j=0; j<=newnode->m_ptr[i]->m_nsize; j++){
125. if (newnode->m_ptr[i]->m_ptr[j]){
126. newnode->m_ptr[i]->m_ptr[j]->m_pparent = newnode->m_ptr[i];
127. }
128. }
129. }
130. }
131. for (int i=0; i<=pinsert->m_nsize; i++){ //change the parent
132. if (pinsert->m_ptr[i]){
133. pinsert->m_ptr[i]->m_pparent = pinsert;
134. for (int j=0; j<=pinsert->m_nsize; j++){
135. if (pinsert->m_ptr[i]->m_ptr[j]){
136. pinsert->m_ptr[i]->m_ptr[j]->m_pparent = pinsert->m_ptr[i];
137. }
138. }
139. }
140. }
141. //break up over
142.
143. key = pinsert->m_pkey[m];
144. pright = newnode;
145. if (pinsert->m_pparent){ //insert the key to the parent
146. pparent = pinsert->m_pparent;
147. n = -1;
148. pparent->m_pkey[pparent->m_nsize] = pparent->m_Infinity;
149. while (key > pparent->m_pkey[++n]);
150. newnode->m_pparent = pinsert->m_pparent;
151. pinsert = pparent;
152. }
153. else { //create new root
154. m_proot = new BTreeNode<Type>(this->m_nMaxSize);
155. m_proot->m_nsize = 1;
156. m_proot->m_pkey[1] = m_proot->m_pkey[0];
157. m_proot->m_pkey[0] = key;
158. m_proot->m_ptr[0] = pinsert;
159. m_proot->m_ptr[1] = pright;
160. newnode->m_pparent = pinsert->m_pparent = m_proot;
161. return 1;
162. }
163. }
164. }
165.
166. template<typename Type> void BTree<Type>::PreMove(BTreeNode<Type> *root, int n){
167. root->m_pkey[root->m_nsize] = root->m_Infinity;
168. for (int i=n; i<root->m_nsize; i++){
169. root->m_pkey[i] = root->m_pkey[i+1];
170. root->m_ptr[i+1] = root->m_ptr[i+2];
171. }
172.
173. root->m_nsize--;
174. }
175.
176. template<typename Type> void BTree<Type>::Merge(BTreeNode<Type> *pleft, BTreeNode<Type> *pparent, BTreeNode<Type> *pright, int n){
177. pleft->m_pkey[pleft->m_nsize] = pparent->m_pkey[n];
178. BTreeNode<Type> *ptemp;
179.
180. for (int i=0; i<=pright->m_nsize; i++){ //merge the two child tree and the parent
181. pleft->m_pkey[pleft->m_nsize+i+1] = pright->m_pkey[i];
182. pleft->m_ptr[pleft->m_nsize+i+1] = pright->m_ptr[i];
183. ptemp = pleft->m_ptr[pleft->m_nsize+i+1];
184. if (ptemp){ //change thd right child tree's parent
185. ptemp->m_pparent = pleft;
186. for (int j=0; j<=ptemp->m_nsize; j++){
187. if (ptemp->m_ptr[j]){
188. ptemp->m_ptr[j]->m_pparent = ptemp;
189. }
190. }
191. }
192. }
193.
194. pleft->m_nsize = pleft->m_nsize + pright->m_nsize + 1;
195. delete pright;
196. PreMove(pparent, n);
197. // this->Print();
198. }
199.
200. template<typename Type> void BTree<Type>::LeftAdjust(BTreeNode<Type> *pright, BTreeNode<Type> *pparent, int min, int n){
201. BTreeNode<Type> *pleft = pparent->m_ptr[n-1], *ptemp;
202. if (pleft->m_nsize > min-1){
203. for (int i=pright->m_nsize+1; i>0; i--){
204. pright->m_pkey[i] = pright->m_pkey[i-1];
205. pright->m_ptr[i] = pright->m_ptr[i-1];
206. }
207. pright->m_pkey[0] = pparent->m_pkey[n-1];
208.
209. pright->m_ptr[0] = pleft->m_ptr[pleft->m_nsize];
210. ptemp = pright->m_ptr[0];
211. if (ptemp){ //change the tree's parent which is moved
212. ptemp->m_pparent = pright;
213. for (int i=0; i<ptemp->m_nsize; i++){
214. if (ptemp->m_ptr[i]){
215. ptemp->m_ptr[i]->m_pparent = ptemp;
216. }
217. }
218. }
219. pparent->m_pkey[n-1] = pleft->m_pkey[pleft->m_nsize-1];
220. pleft->m_pkey[pleft->m_nsize] = pleft->m_Infinity;
221. pleft->m_nsize--;
222. pright->m_nsize++;
223. }
224. else {
225. Merge(pleft, pparent, pright, n-1);
226. }
227. // this->Print();
228. }
229.
230. template<typename Type> void BTree<Type>::RightAdjust(BTreeNode<Type> *pleft, BTreeNode<Type> *pparent, int min, int n){
231. BTreeNode<Type> *pright = pparent->m_ptr[1], *ptemp;
232. if (pright && pright->m_nsize > min-1){
233. pleft->m_pkey[pleft->m_nsize] = pparent->m_pkey[0];
234. pparent->m_pkey[0] = pright->m_pkey[0];
235. pleft->m_ptr[pleft->m_nsize+1] = pright->m_ptr[0];
236. ptemp = pleft->m_ptr[pleft->m_nsize+1];
237. if (ptemp){ //change the tree's parent which is moved
238. ptemp->m_pparent = pleft;
239. for (int i=0; i<ptemp->m_nsize; i++){
240. if (ptemp->m_ptr[i]){
241. ptemp->m_ptr[i]->m_pparent = ptemp;
242. }
243. }
244. }
245. pright->m_ptr[0] = pright->m_ptr[1];
246. pleft->m_nsize++;
247. PreMove(pright,0);
248. }
249. else {
250. Merge(pleft, pparent, pright, 0);
251. }
252. }
253.
254.
255. template<typename Type> bool BTree<Type>::Remove(const Type item){
256. Triple<Type> result = this->Search(item);
257. if (!result.m_ntag){
258. return 0;
259. }
260. BTreeNode<Type> *pdel, *pparent, *pmin;
261. int n = result.m_nfind;
262. pdel = result.m_pfind;
263.
264. if (pdel->m_ptr[n+1] != NULL){ //change into delete leafnode
265. pmin = pdel->m_ptr[n+1];
266. pparent = pdel;
267. while (pmin != NULL){
268. pparent = pmin;
269. pmin = pmin->m_ptr[0];
270. }
271. pdel->m_pkey[n] = pparent->m_pkey[0];
272. pdel = pparent;
273. n = 0;
274. }
275.
276. PreMove(pdel, n); //delete the node
277.
278. int min = (this->m_nMaxSize + 1) / 2;
279. while (pdel->m_nsize < min-1){ //if it is not a BTree, then adjust
280. n = 0;
281. pparent = pdel->m_pparent;
282. if (NULL == pparent)
283. {
284. return 1;
285. }
286. while (n<= pparent->m_nsize && pparent->m_ptr[n]!=pdel){
287. n++;
288. }
289. if (!n){
290. RightAdjust(pdel, pparent, min, n); //adjust with the parent and the right child tree
291. }
292. else {
293. LeftAdjust(pdel, pparent, min, n); //adjust with the parent and the left child tree
294. }
295. pdel = pparent;
296. if (pdel == m_proot){
297. break;
298. }
299. }
300. if (!m_proot->m_nsize){ //the root is merged
301. pdel = m_proot->m_ptr[0];
302. delete m_proot;
303. m_proot = pdel;
304. m_proot->m_pparent = NULL;
305. for (int i=0; i<m_proot->m_nsize; i++){
306. if (m_proot->m_ptr[i]){
307. m_proot->m_ptr[i]->m_pparent = m_proot;
308. }
309. }
310. }
311. return 1;
312. }
313.
314. template<typename Type> void BTree<Type>::Print(BTreeNode<Type> *start, int n){
315. if (NULL == start){
316. return;
317. }
318. if (start->m_ptr[0]){
319. Print(start->m_ptr[0], n+1); //print the first child tree
320. }
321. else {
322. for (int j=0; j<n; j++){
323. cout << " ";
324. }
325. cout << "NULL" << endl;
326. }
327.
328. for (int i=0; i<start->m_nsize; i++){ //print the orther child tree
329. for (int j=0; j<n; j++){
330. cout << " ";
331. }
332. cout << start->m_pkey[i] << "--->" <<endl;
333. if (start->m_ptr[i+1]){
334. Print(start->m_ptr[i+1], n+1);
335. }
336. else {
337. for (int j=0; j<n; j++){
338. cout << " ";
339. }
340. cout << "NULL" << endl;
341. }
342. }
343. }
344.
345. template<typename Type> void BTree<Type>::Print(){
346. Print(m_proot);
347. }
348.
349. template<typename Type> int BTree<Type>::Size(BTreeNode<Type> *root){
350. if (NULL == root){
351. return 0;
352. }
353. int size=root->m_nsize;
354. for (int i=0; i<=root->m_nsize; i++){
355. if (root->m_ptr[i]){
356. size += this->Size(root->m_ptr[i]);
357. }
358. }
359. return size;
360. }
361.
362. template<typename Type> int BTree<Type>::Size(){
363. return this->Size(this->m_proot);
364. }
365.
366. template<typename Type> BTreeNode<Type>* BTree<Type>::GetParent(const Type item){
367. Triple<Type> result = this->Search(item);
368. return result.m_pfind->m_pparent;
369. }
Main.cpp
[cpp] view plain copy print?
1. #include <iostream>
2. #include <cstdlib>
3.
4. using namespace std;
5.
6. #include "BTree.h"
7.
8. int main(){
9. BTree<int> btree(3);
10. int init[]={1,3,5,7,4,2,8,0,6,9,29,13,25,11,32,55,34,22,76,45
11. ,14,26,33,88,87,92,44,54,23,12,21,99,19,27,57,18,72,124,158,234
12. ,187,218,382,122,111,222,333,872,123};
13. for (int i=0; i<49; i++){
14. btree.Insert(init[i]);
15.
16. }
17.
18. btree.Print();
19. cout << endl << endl << endl;
20.
21. Triple<int> result = btree.Search(13);
22. cout << result.m_pfind->GetKey(result.m_nfind) << endl;
23. cout << endl << endl << endl;
24.
25. for (int i=0; i<49; i++){
26. btree.Remove(init[i]);
27.
28. btree.Print();
29. cout << endl << endl << endl;
30.
31. }
32.
33. return 0;
34. }
本文由职坐标整理并发布，了解更多内容，请关注职坐标编程语言C/C+频道！
喜欢 | 2
不喜欢 | 0
您输入的评论内容中包含违禁敏感词
我知道了
请输入正确的手机号码
请输入正确的验证码
您今天的短信下发次数太多了，明天再试试吧！
我们会在第一时间安排职业规划师联系您！
您也可以联系我们的职业规划师咨询：
版权所有 职坐标-一站式IT培训就业服务领导者 沪ICP备13042190号-4
上海海同信息科技有限公司 Copyright ©2015 www.zhizuobiao.com，All Rights Reserved.
沪公网安备 31011502005948号
索取资料
答疑解惑
技术交流
职业测评
面试技巧
高薪秘笈
