歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

B-樹 C++模板類封裝(有圖有真相)

定義:

一棵m階B-樹是擁有以下性質的多路查找樹:

1、非葉子結點的根結點至少擁有兩棵子樹;

2、每一個非根且非葉子的結點含有k-1個關鍵字以及k個子樹,其中⌈m/2⌉≤k≤m;

3、每一個葉子結點都具有k-1個關鍵字,其中⌈m/2⌉≤k≤m;

4、key[i]和key[i+1]之間的孩子節點的值介於key[i]、key[i+1]之間

5、所有的葉子結點都在同一層。

ps: ⌈m/2⌉是向上取整

建立B-樹的節點:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 template<class K,int M=3> struct BTreeNode {     K _key[M];  //關鍵字 (有效關鍵字個數為M-1)     BTreeNode<K, M>* _sub[M + 1]; //鏈接子樹的指針數組     size_t _size;      //節點中關鍵字的個數     BTreeNode<K, M>* _parent; //指向父節點的指針       BTreeNode()         :_size(0)         , _parent(NULL)     {         for (size_t i = 0; i < M + 1; i++)         {             _sub[i] = NULL;         }     } };

插入數據key:

 M階B樹--M=3:

用例 {53, 75, 139, 49, 145, 36, 101};

 

根據上面這些圖,依次插入這些數據時的變化一目了然。現在就來看代碼:

在插入一個數據前,我們首先要找到你要插入的位置,這裡實現一個find函數尋找插入點,輔助插入數據key;

但是這裡find函數的返回值該如何處理?bool或int都不行,這兩個都不能滿足我們的要求。BTreeNode類型也不太合適,找到key就返回該節點無可厚非;但是如果你查找的時候已經遍歷到NULL了,說明沒有找到數據key,這時候難道返回NULL嗎?顯然不合適,要插入的位置不能是NULL,這時候應該返回的是當前NULL的父親結點,也就是我要插入數據的位置了。

那麼找到就返回該節點以及該數據所在的關鍵字數組的下標,未找到就返回-1及父節點,這裡我們可以將將它們封裝起來,如下:

1 2 3 4 5 6 7 8 9 10 11 template<class K,class V> struct Pair {     K _first;     V _second;           Pair(const K &k = K(), const V& v = V())         :_first(k)         , _second(v)     {} };

返回值類型確定好的,其它的就好辦了:

查找函數思想:

遍歷關鍵字數組_key[],如果key比它小就 ++i 並繼續往後遍歷
1.如果key=_key[i]則停止遍歷,返回該結構體節點
2.如果key比它大則停止遍歷,此時的子樹_sub[i]指向的關鍵字數組的所有數據都是介於_key[i-1]和_key[i]之間的數據,我們要找的key或許就在其中
3.如果跳出循環則未找到該數據cur=NULL,返回cur的父節點;這時候若是插入key,就插入到parent指向的關鍵字數組中

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19     //遞歸查找key Pair<BTreeNode<K, M>*, int> Find(const K& key) {     BTreeNode<K, M>* parent=NULL;     BTreeNode<K, M>* cur=_root;           while (cur!=NULL)     {         size_t i = 0;         while (i < cur->_size&&cur->_key[i] < key)             ++i;         if (cur->_key[i] == key)             return Pair<BTreeNode<K, M>*, int>(cur, i);         // key<_key[i] 則走向與key[i]下標相同的子樹         parent = cur;         cur = cur->_sub[i];     }     return Pair<BTreeNode<K, M>*, int>(parent, -1); }

找到位置後,就可以插入該數據key了

分情況:

1.B-樹為NULL

2.B-樹中已經存在key

3.B-樹中不存在key,先把key以插入排序的方式插入到關鍵字數組中,判斷該關鍵字數組是否已滿,滿了就要進行分裂。注意,這裡的分裂有時可能不止一次!

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 //插入數據     bool Insert(K& key)     {         // 1.B-樹為空         if (NULL == _root)         {             _root = new BTreeNode<K, M>;             _root->_key[0] = key;             ++_root->_size;             return true;         }           Pair<BTreeNode<K, M>*, int> ret = Find(key);         // 2.該數據已經存在         if (ret._second != -1)              return false;           // 3.插入數據到關鍵字數組         BTreeNode<K, M>* cur = ret._first;         BTreeNode<K, M>* sub = NULL;         while (1)         {             int i = 0;             for ( i = cur->_size - 1; i >= 0; )             { // 把大數往後挪,對應子樹也要進行挪動                 if (cur->_key[i] > key)                 {                     cur->_key[i + 1] = cur->_key[i];                     cur->_sub[i + 2] = cur->_sub[i + 1];                     i--;                 }                 else                 {                     break;                 }             }             cur->_key[i + 1] = key;             cur->_sub[i + 2] = sub;             if (sub!=NULL)                 cur->_sub[i+2]->_parent = cur;             cur->_size++;               //關鍵字數組未滿,插入成功             if (cur->_size < M)                 return true;               //關鍵字數組已滿,需要進行分裂             int mid = M / 2;             BTreeNode<K, M>* tmp = new BTreeNode<K, M>;             int index = 0;             size_t k;               for ( k = mid + 1; k < cur->_size; k++)             {                 tmp->_key[index] = cur->_key[k];                 if (cur->_sub[k] != NULL)                 {                     tmp->_sub[index] = cur->_sub[k];                     cur->_sub[k] = NULL;                     tmp->_sub[index]->_parent = tmp;                 }                 tmp->_size++;                 cur->_size--;                 index++;             }             if (cur->_sub[k] != NULL)             {                 tmp->_sub[index] = cur->_sub[k];                 cur->_sub[k] = NULL;                 tmp->_sub[index]->_parent = tmp;             }             //父節點為空時的鏈接             if (cur->_parent == NULL)             {                 _root = new BTreeNode<K, M>;                 _root->_key[0] = cur->_key[mid];                 cur->_size--;                 _root->_sub[0] = cur;                 _root->_sub[1] = tmp;                 _root->_size++;                                   //鏈接                 tmp->_parent = _root;                 cur->_parent = _root;                 return true;             }             //父節點不為空時的鏈接             key = cur->_key[mid];             cur->_size--;             cur = cur->_parent;             sub = tmp;         }     }

代碼到Linux公社資源站下載:

------------------------------------------分割線------------------------------------------

免費下載地址在 http://linux.linuxidc.com/

用戶名與密碼都是www.linuxidc.com

具體下載目錄在 /2016年資料/7月/18日/B-樹 C++模板類封裝(有圖有真相)/

下載方法見 http://www.linuxidc.com/Linux/2013-07/87684.htm

------------------------------------------分割線------------------------------------------

Copyright © Linux教程網 All Rights Reserved