真c++创建B树（非c with class）
??首先要感謝清華大學(xué)鄧公的教材（數(shù)據(jù)結(jié)構(gòu)c++語(yǔ)言版第三版）和視頻
??鄧公的視頻網(wǎng)址如下：https://next.xuetangx.com/course/THU08091002048/1515966
??由于鄧公實(shí)現(xiàn)b樹(shù)是用自定義的vector實(shí)現(xiàn)，網(wǎng)上大部分也都是用數(shù)組實(shí)現(xiàn)。我嘗試了一下用stl的vector實(shí)現(xiàn)。也能實(shí)現(xiàn)b樹(shù)的功能。
??在此，為了方便，用了一些教材中的插圖（侵刪）。
如果要看懂此代碼，你需要擁有的基礎(chǔ)為：
- 對(duì)c++模板有基本了解
- 對(duì)c++stl中的vector有一定了解
- 熟悉stl迭代器，逆向迭代器的用法，在本代碼的查找，插入和刪除操作中，用了大量的迭代器操作，如果你不熟悉，可能會(huì)有點(diǎn)繞。
- 對(duì)c++11的新特性，如auto ，lambdas，基于范圍的for循環(huán)等有所了解
??本代碼在vs2019版能運(yùn)行，其他平臺(tái)未測(cè)試，但應(yīng)該能支持c++11的編譯器都能運(yùn)行。如果你沒(méi)接觸過(guò)b樹(shù)，要理解本代碼，你至少需要一個(gè)小時(shí)甚至以上，b樹(shù)真的十分復(fù)雜。
此B樹(shù)只適合存放不相同元素，如果想放相同的元素，請(qǐng)自行改進(jìn)。
文章目錄
- 一.B樹(shù)的定義~
- 1.多路搜索樹(shù)~
- 2.多路平衡搜索樹(shù)~
- 3.B樹(shù)的性質(zhì)~
- 二.B樹(shù)節(jié)點(diǎn)類~
- BTNode.h~
- 三.B樹(shù)類~
- （一）定義變量和接口~
- 1.需要的變量
- 2.需要的接口
- 3.必備的輔助函數(shù)
- 4.BTree.h~
- （二）B樹(shù)查找~
- 1.代碼~
- 2.效率分析~
- （三）B樹(shù)插入~
- 1.簡(jiǎn)單插入圖示~
- 2.代碼~
- （四）上溢與分裂~
- 1.只上溢一次，不會(huì)造成父親上溢~
- 2.上溢之后，父親也會(huì)上溢~
- 3.上溢到根節(jié)點(diǎn)~
- 4.show you my code~
- 5.復(fù)雜度分析~
- （五）刪除~
- 1.節(jié)點(diǎn)為葉節(jié)點(diǎn)刪除圖示~
- 2.節(jié)點(diǎn)不為葉節(jié)點(diǎn)刪除圖示~
- 3.代碼~
- （六）下溢與合并~
- 1.V的左兄弟L存在，左兄弟至少包含?m/2?個(gè)關(guān)鍵碼（動(dòng)圖gif）~
- 2.V的右兄弟R存在，右兄弟至少包含?m/2?個(gè)關(guān)鍵碼（動(dòng)圖gif）~
- 3.左兄弟為空，并且右兄弟沒(méi)有足夠孩子（動(dòng)圖gif）~
- 4.右兄弟為空，并且左兄弟沒(méi)有足夠孩子（動(dòng)圖gif）~
- 5.經(jīng)過(guò)（3）（4）后，父親發(fā)生下溢~
- 6.show you my code~
- 7.復(fù)雜度分析~
- （七）前序遍歷測(cè)試~
- 四.結(jié)果測(cè)試~
- 1.插入測(cè)試~
- 2.刪除測(cè)試~
- 五.結(jié)語(yǔ)~
一.B樹(shù)的定義~
1.多路搜索樹(shù)~
比如以二叉搜索樹(shù)（BST）的兩層為間隔，將各節(jié)點(diǎn)與其左右孩子合并成一個(gè)大節(jié)點(diǎn)，就能得到一個(gè)四路搜索樹(shù)。
當(dāng)以三層為間隔時(shí)，可以得到八路搜索樹(shù)。因此可以推廣到2^k路搜索樹(shù)
接下來(lái)的代碼，能創(chuàng)建任意路搜索樹(shù)，如果創(chuàng)建的為4路搜索樹(shù)，我們不妨稱之為（2,4）樹(shù)。
2.多路平衡搜索樹(shù)~
若樹(shù)中所有葉節(jié)點(diǎn)的深度均相等，就可以稱之為多路平衡搜索樹(shù)。
深度即從根節(jié)點(diǎn)到這個(gè)節(jié)點(diǎn)的長(zhǎng)度。
如下圖所示
3.B樹(shù)的性質(zhì)~
舉例說(shuō)明：
即在一顆4階的B樹(shù)中，其孩子個(gè)數(shù)至少為2，最多為4.關(guān)鍵碼個(gè)數(shù)至少為1，最多為3.
即在一顆3階的B樹(shù)中，其孩子個(gè)數(shù)至少為2，最多為3.關(guān)鍵碼個(gè)數(shù)至少為1，最多為2.
二.B樹(shù)節(jié)點(diǎn)類~
從B樹(shù)的結(jié)構(gòu)和性質(zhì)來(lái)看，在B樹(shù)節(jié)點(diǎn)中，至少需要一個(gè)存放關(guān)鍵碼的容器和一個(gè)存放孩子節(jié)點(diǎn)的容器。
所以我們把同一節(jié)點(diǎn)的所有孩子組織為一個(gè)vector，各相鄰孩子之間的關(guān)鍵碼也組織為一個(gè)vector。當(dāng)然，按照B-樹(shù)的定義，孩子vector的實(shí)際長(zhǎng)度總是比關(guān)鍵碼vector多一。
為了方便插入和刪除，同樣也需要一個(gè)parent指針，來(lái)指向父節(jié)點(diǎn)。
同樣，為了規(guī)范，將節(jié)點(diǎn)定義包含在一個(gè)命名空間my_btree里面。
由于沒(méi)有在堆區(qū)構(gòu)造，所以不需要寫析構(gòu)函數(shù)來(lái)delete
BTNode.h~
#pragma once #include <vector> using std::vector;namespace my_btree {/*B-樹(shù)節(jié)點(diǎn)模板類*/template<typename T = int>class BTNode {public:using BTNodePtr = BTNode<T>*;public:BTNodePtr _parent;//父節(jié)點(diǎn)vector<T> _key;//關(guān)鍵碼vectorvector<BTNodePtr> _child;//孩子vector，其長(zhǎng)度總比key多一private:int _order;//B樹(shù)的order，方便擴(kuò)容//可不要這個(gè)，讓vector自動(dòng)擴(kuò)容public://用于創(chuàng)建根節(jié)點(diǎn)，初始時(shí)有0個(gè)關(guān)鍵碼和一個(gè)空孩子指針BTNode(int order=3) :_order(order),_parent(nullptr), _key(0){_key.reserve(order);//并且給key和child的vector預(yù)留容量//用空間換時(shí)間。_child.reserve(order + 1);_child.push_back(nullptr);}};//class BTNode}//namespace my_btree三.B樹(shù)類~
（一）定義變量和接口~
1.需要的變量
int _size;//存放的關(guān)鍵碼總數(shù)int _order;//B-樹(shù)的階次，比如3階b樹(shù)，可以在構(gòu)造的時(shí)候進(jìn)行修改。BTNodePtr _root;//根節(jié)點(diǎn)BTNodePtr _hot;//BTree::search()最后訪問(wèn)的非空（除非樹(shù)空）的節(jié)點(diǎn)位置如果看過(guò)鄧?yán)蠋煹恼n的同學(xué)，應(yīng)該能明白_hot節(jié)點(diǎn)的作用。在這里我簡(jiǎn)單解釋一下_hot的作用。即其對(duì)應(yīng)查找之后，訪問(wèn)的最后一個(gè)非空節(jié)點(diǎn)位置。有了_hot，節(jié)點(diǎn)的插入和刪除操作就能變得更加簡(jiǎn)單。
2.需要的接口
構(gòu)造函數(shù) 析構(gòu)函數(shù) 查找 插入 刪除 遍歷（前序遍歷，方便看結(jié)果） 其他接口如 獲取階次，返回規(guī)模，判空，返回根節(jié)點(diǎn)等。3.必備的輔助函數(shù)
因插入而造成節(jié)點(diǎn)上溢所需的解決上溢函數(shù) 因刪除而造成節(jié)點(diǎn)下溢所需的解決下溢函數(shù)4.BTree.h~
為了方便起見(jiàn)，以下均以3階b樹(shù)為基準(zhǔn) #pragma once #include "BTNode.h" #include <algorithm> using std::cout; using std::endl;namespace my_btree{template<typename T=int>class BTree {public:using BTNodePtr = BTNode<T>*;protected:int _size;//存放的關(guān)鍵碼總數(shù)int _order;//B-樹(shù)的階次，比如3階b樹(shù)，可以在構(gòu)造的時(shí)候進(jìn)行修改。BTNodePtr _root;//根節(jié)點(diǎn)BTNodePtr _hot;//BTree::search()最后訪問(wèn)的非空（除非樹(shù)空）的節(jié)點(diǎn)位置protected:void solveOverFlow(BTNode<T>*);//處理因插入而上溢之后的分裂處理void solveUnderFlow(BTNode<T>*);//處理因刪除而下溢之后的合并處理public:BTree(int order=3):_order(order),_size(0),_root(new BTNode<T>(_order)),_hot(nullptr){}~BTree() {if (_root){delete _root;_root = nullptr;}}public:constexpr int order()const {//獲取階次return _order;}constexpr int size()const {return _size;}inline BTNodePtr root()const{//返回樹(shù)根return _root;} constexpr bool empty()const {return !_root;}public:BTNode<T>* search(const T& data);//查找bool insert(const T& data);//插入bool remove(const T& data);//刪除public:void show_BTree(BTNode<T>* BT)const;};//class BTree }//namespace my_btree（二）B樹(shù)查找~
1.代碼~
??從根節(jié)點(diǎn)開(kāi)始，通過(guò)關(guān)鍵碼的比較不斷深入至下一層，直到某一關(guān)鍵碼命中（查找成功），或者到達(dá)某一外部節(jié)點(diǎn)（查找失敗）。
??此時(shí)各節(jié)點(diǎn)內(nèi)通常都包含多個(gè)關(guān)鍵碼，故有可能需要經(jīng)過(guò)多次比較，才能確定應(yīng)該轉(zhuǎn)向下一層的哪個(gè)節(jié)點(diǎn)并繼續(xù)查找。
??如果查找失敗，返回不大于data（圖中的key）的最大節(jié)點(diǎn)（由于節(jié)點(diǎn)數(shù)最多也不過(guò)幾百個(gè)，故用順序查找還是二分查找，都可以，這里用的是順序查找）。從而轉(zhuǎn)至下一層，直到找到或者到達(dá)葉子節(jié)點(diǎn)。
??由于c++標(biāo)準(zhǔn)庫(kù)并沒(méi)有提供find_last的算法給vector使用。因此返回不大于data的最大節(jié)點(diǎn)，我用的是逆向迭代器結(jié)合find_if算法，并結(jié)合lambdas表達(dá)式作為仿函數(shù)來(lái)實(shí)現(xiàn)。
??并且由于標(biāo)準(zhǔn)庫(kù)中的算法，需要傳的是迭代器，返回的也是迭代器，因此，如果你對(duì)迭代器不是很懂，那么就建議你看看鄧公原版的代碼，那個(gè)稍微容量理解點(diǎn)。
template<typename T>BTNode<T>* BTree<T>::search(const T& data){BTNode<T>* v = _root;//從根節(jié)點(diǎn)出發(fā)_hot = nullptr;//首先將_hot置空while (v) {//返回第一個(gè)不大于data的迭代器auto key_Iter = std::find_if(v->_key.rbegin(), v->_key.rend(),[data](T key_value){return key_value <= data;});if ((key_Iter != v->_key.rend()) && data == *key_Iter)//若找到，則返回return v;_hot = v;//否則就將當(dāng)前節(jié)點(diǎn)設(shè)為_(kāi)hot,并且去對(duì)應(yīng)的孩子節(jié)點(diǎn)找//由于孩子的個(gè)數(shù)始終比關(guān)鍵碼個(gè)數(shù)多一，所以不會(huì)越界v = v->_child.at(std::distance(key_Iter,v->_key.rend()));}return nullptr;//失敗，抵達(dá)外部節(jié)點(diǎn)}2.效率分析~
??vector的查找十分迅速，因此其耗時(shí)幾乎可以忽略不計(jì)。
??b樹(shù)的查找的耗時(shí)主要在于去其孩子節(jié)點(diǎn)找相應(yīng)的值。并且在查找的過(guò)程中，在每一高度上，至多訪問(wèn)一個(gè)節(jié)點(diǎn)。因此，b樹(shù)查找的復(fù)雜度即為b樹(shù)的高度。
??在這里，證明略，查閱資料可得b樹(shù)的平均高度為O(logmN)。
??故b樹(shù)查找的平均復(fù)雜度為O(logmN)。
（三）B樹(shù)插入~
1.簡(jiǎn)單插入圖示~
在上圖中插入節(jié)點(diǎn)232.代碼~
template<typename T> bool BTree<T>::insert(const T& data) {//搜尋了一遍之后，_hot節(jié)點(diǎn)所在的位置的關(guān)鍵碼vector即為要插入的數(shù)值應(yīng)該屬于的vector。BTNode<T>* v = search(data);if (v)//確認(rèn)目標(biāo)不存在return false;//找到要插入的位置auto key_r_Iter = std::find_if(_hot->_key.rbegin(), _hot->_key.rend(), [data](T key_value) {return key_value <= data;});int distance = std::distance(key_r_Iter, _hot->_key.rend())+1; //提前算好距離并且必須要加1//由于insert只接受正向迭代器,所以要轉(zhuǎn)成正向的,就是要插入到后一個(gè)位置_hot->_key.insert(key_r_Iter.base(), data); auto child_Iter = _hot->_child.begin();child_Iter += distance;//找到要插入的孩子節(jié)點(diǎn)的迭代器位置_hot->_child.insert(child_Iter, nullptr);//在對(duì)應(yīng)孩子節(jié)點(diǎn)vector中，插入一個(gè)空指針_size++;//當(dāng)此時(shí)_hot節(jié)點(diǎn)的孩子的個(gè)數(shù)大于原來(lái)的設(shè)定的B樹(shù)的階次時(shí)if(_order < static_cast<int>(_hot->_child.size()))solveOverFlow(_hot);//需做分裂，處理上溢return true; }（四）上溢與分裂~
??由b樹(shù)的定義可知，剛發(fā)生上溢的節(jié)點(diǎn)，應(yīng)恰好含有m個(gè)關(guān)鍵碼。不妨取s=m/2的下界。則它們依次為：
{ k0, ..., ks-1; ks; ks+1, ..., km-1 } ??可見(jiàn)，以ks為界，可將該節(jié)點(diǎn)分前、后兩個(gè)子節(jié)點(diǎn)，且二者大致等長(zhǎng)。??于是，可令關(guān)鍵碼ks上升一層，歸入其父節(jié)點(diǎn)（若存在）中的適當(dāng)位置，并分別以這兩個(gè)子節(jié)點(diǎn)作為其左、右孩子。這一過(guò)程，稱作節(jié)點(diǎn)的分裂（split）。
以下分三種情況進(jìn)行考慮
1.只上溢一次，不會(huì)造成父親上溢~
在上圖中插入節(jié)點(diǎn)29
可以觀察到，由于19 23 29有了三個(gè)key，超過(guò)了3階b樹(shù)的限制，3階b樹(shù)單個(gè)節(jié)點(diǎn)的關(guān)鍵碼數(shù)最多為2
因此此時(shí)要發(fā)生上溢。
??我們之前設(shè)置的s的作用就體現(xiàn)出來(lái)了，由于m=3，所以s=1，因此，以下標(biāo)為1的關(guān)鍵碼為界限進(jìn)行分裂，在19 23 29中，23的下標(biāo)為1，所以23提升到父節(jié)點(diǎn)中，而19 和29 就成為其左右兩個(gè)孩子。
??父親節(jié)點(diǎn)36插入23之后，符合3階b樹(shù)的標(biāo)準(zhǔn)，所以上溢終止，調(diào)整結(jié)束。
2.上溢之后，父親也會(huì)上溢~
在上圖中插入節(jié)點(diǎn)45
??同理，插入了45之后，41 45 51三個(gè)節(jié)點(diǎn)由于有3個(gè)關(guān)鍵碼，因此也會(huì)發(fā)生上溢，經(jīng)過(guò)上溢方式1的調(diào)整?？傻?br />
這時(shí)候，不難觀察到其父親23 36 45此時(shí)也有了3個(gè)關(guān)鍵碼，因此也會(huì)發(fā)生上溢，因此，可得。
這樣就調(diào)整完畢。
3.上溢到根節(jié)點(diǎn)~
倘若此時(shí)我們插入87 此時(shí)會(huì)發(fā)生持續(xù)上溢 直到根節(jié)點(diǎn) 此時(shí)，還是跟之前一樣，將key為1的關(guān)鍵碼往上提，即把53往上提 至此就完成了上溢調(diào)整。 這也是b樹(shù)長(zhǎng)高的唯一可能。4.show you my code~
注釋寫的很詳細(xì)了，可以自己對(duì)照?qǐng)D加深理解。 template<typename T> void BTree<T>::solveOverFlow(BTNode<T>* v) {while (_order < static_cast<int>(v->_child.size())) {int s = _order / 2;//軸點(diǎn)(如果能到這一步，說(shuō)明發(fā)生了上溢，此時(shí)，必然有key的size等于_order)int move_Number = _order - s - 1;//分裂后需要移動(dòng)的關(guān)鍵碼的個(gè)數(shù)//創(chuàng)建一個(gè)新節(jié)點(diǎn)，并且由于構(gòu)造函數(shù)，這個(gè)節(jié)點(diǎn)必然有一個(gè)空孩子//堆區(qū)的數(shù)據(jù)，由vector來(lái)刪除BTNode<T>* newNode = new BTNode<T>(_order);//將v的右側(cè)的child的vector的數(shù)值轉(zhuǎn)移到新的節(jié)點(diǎn)的孩子vector中//首先，因?yàn)檫@個(gè)新節(jié)點(diǎn)創(chuàng)建后，一定有一個(gè)空孩子，所以要將這個(gè)空孩子的值賦值成對(duì)應(yīng)的值//而且v->_child的vector必然有兩個(gè)元素以上（可能均為nullptr）newNode->_child.at(0) = *(v->_child.end() - move_Number - 1);//再在后面進(jìn)行插入,此時(shí)是在begin()的下一個(gè)位置進(jìn)行插入newNode->_child.insert(++newNode->_child.begin(), v->_child.end() - move_Number, v->_child.end());//刪除v中對(duì)應(yīng)child的vector的一部分v->_child.erase(v->_child.end() - move_Number - 1, v->_child.end());//將v的右側(cè)的關(guān)鍵碼vector的數(shù)值轉(zhuǎn)移到新的節(jié)點(diǎn)的關(guān)鍵碼vector中newNode->_key.insert(newNode->_key.begin(), v->_key.end() - move_Number, v->_key.end());//刪除v中對(duì)應(yīng)key的vector的一部分v->_key.erase(v->_key.end() - move_Number, v->_key.end());//如果新節(jié)點(diǎn)的第一個(gè)孩子不為空，如果一個(gè)孩子為空，則后面孩子必然為空if (newNode->_child.at(0)) {for (auto& child : newNode->_child) {//則令它們的父節(jié)點(diǎn)統(tǒng)一child->_parent = newNode;//即指向父節(jié)點(diǎn)}}BTNode<T>* p = v->_parent;//v節(jié)點(diǎn)的當(dāng)前父親if (p == nullptr) {//如果父親為空//則說(shuō)明此時(shí)根節(jié)點(diǎn)溢出，則需創(chuàng)建一個(gè)新的節(jié)點(diǎn)作為根節(jié)點(diǎn)_root = p = new BTNode<T>(_order);p->_child.at(0) = v;//就將這個(gè)根節(jié)點(diǎn)的孩子設(shè)為vv->_parent = p;//并更新v的父親}//找到v在父節(jié)點(diǎn)對(duì)應(yīng)的孩子的秩auto p_r_Iter = std::find_if(p->_key.rbegin(), p->_key.rend(), [=](T key_value) {return key_value <= v->_key.at(0);});int distance = std::distance(p_r_Iter, p->_key.rend()) + 1;//提前算好距離并且必須要加1auto key_Iter = p_r_Iter.base();p->_key.insert(key_Iter, v->_key.at(s));//在對(duì)應(yīng)位置插入軸點(diǎn)關(guān)鍵碼v->_key.pop_back();//并且s，必然是v的key此時(shí)的最后一個(gè)，在v中刪除這個(gè)關(guān)鍵碼auto child_Iter = p->_child.begin();child_Iter += distance;p->_child.insert(child_Iter, newNode);//將這個(gè)新節(jié)點(diǎn)作為p的孩子newNode->_parent = p;//并且更新新節(jié)點(diǎn)的父親v = p;//將v設(shè)成v的父親，進(jìn)入迭代循環(huán)} }5.復(fù)雜度分析~
??若將B-樹(shù)的階次m視作為常數(shù)，則關(guān)鍵碼的移動(dòng)和復(fù)制操作所需的時(shí)間都可以忽略。至于solveOverflow()算法，其每一次循環(huán)均只需常數(shù)時(shí)間，迭代層數(shù)不超過(guò)B-樹(shù)高度。由此可知，對(duì)于存有N個(gè)關(guān)鍵碼的m階B-樹(shù)，每次插入操作都可在O(logmN)時(shí)間內(nèi)完成。
??實(shí)際上，因插入操作而導(dǎo)致O(logmN)次分裂的情況極為罕見(jiàn)，單次插入操作平均引發(fā)的分裂次數(shù)，遠(yuǎn)遠(yuǎn)低于這一估計(jì)，故時(shí)間通常主要消耗于對(duì)目標(biāo)關(guān)鍵碼的查找。
（五）刪除~
1.節(jié)點(diǎn)為葉節(jié)點(diǎn)刪除圖示~
在上圖中刪除節(jié)點(diǎn)412.節(jié)點(diǎn)不為葉節(jié)點(diǎn)刪除圖示~
在上圖中刪除節(jié)點(diǎn)53，首先將53與其直接后繼64進(jìn)行交換數(shù)值 然后當(dāng)做葉節(jié)點(diǎn)刪除53既可3.代碼~
template<typename T> bool BTree<T>::remove(const T& data) {BTNode<T>* v = search(data);if (v == nullptr)//如果沒(méi)找到，就返回return false;//在v中確定data的逆向迭代器的位置//必然存在，不可能找不到auto key_r_Iter = std::find_if(v->_key.rbegin(), v->_key.rend(), [data](T key_value) {return key_value <= data;});//同search算法，不需要加1//distance必然不可能為0int distance = std::distance(key_r_Iter, v->_key.rend());if (v->_child.at(0)) {//如果v有孩子，就去找其直接后繼BTNode<T>* u = v->_child.at(distance);//找到對(duì)應(yīng)孩子節(jié)點(diǎn)的位置while (u->_child.at(0))//向左一直找,直到u沒(méi)有孩子為止，說(shuō)明u此時(shí)為葉節(jié)點(diǎn)u = u->_child.at(0);//此時(shí)的u即為原來(lái)v的直接后繼，因此同BST，此時(shí)將v此時(shí)的值設(shè)為u的值既可v->_key.at(distance - 1) = u->_key.at(0);v = u;//讓v去接替u的值，然后刪掉其中的key和child。distance = 0;}if (distance == 0) {v->_key.erase(v->_key.begin());v->_child.erase(++(v->_child.begin()));//刪第二個(gè)，也可以刪第一個(gè)}else {auto key_Iter = key_r_Iter.base();v->_key.erase(--key_Iter);//此時(shí)刪除必須要退一格進(jìn)行刪除auto child_Iter = v->_child.begin();child_Iter += distance;v->_child.erase(child_Iter);}_size--;//規(guī)模更新solveUnderFlow(v);//如果必要，需做旋轉(zhuǎn)或合并return true; }（六）下溢與合并~
??通過(guò)B樹(shù)的性質(zhì)，不難發(fā)現(xiàn)，在m階B-樹(shù)中，剛發(fā)生下溢的節(jié)點(diǎn)V必恰好包含?m/2?(取上界）- 2個(gè)關(guān)鍵碼和?m/2?- 1個(gè)孩子。以下將根據(jù)其左、右兄弟所含關(guān)鍵碼的數(shù)目，分五種情況做相應(yīng)的處理。
??還是以3階b樹(shù)來(lái)考慮，此時(shí)m=3，即m/2的上界為2.
1.V的左兄弟L存在，左兄弟至少包含?m/2?個(gè)關(guān)鍵碼（動(dòng)圖gif）~
??即左兄弟至少有2個(gè)關(guān)鍵碼。而v刪除后此時(shí)只有0個(gè)關(guān)鍵碼，此時(shí)，就將父節(jié)點(diǎn)的對(duì)應(yīng)關(guān)鍵碼給v，并從v的左兄弟中借最右邊的那個(gè)關(guān)鍵碼給父親。同時(shí)也要對(duì)孩子進(jìn)行一些刪除和變換。
如刪除下圖中關(guān)鍵碼32.V的右兄弟R存在，右兄弟至少包含?m/2?個(gè)關(guān)鍵碼（動(dòng)圖gif）~
??即右兄弟至少有2個(gè)關(guān)鍵碼。而v刪除后此時(shí)只有0個(gè)關(guān)鍵碼，此時(shí)，就將父節(jié)點(diǎn)的對(duì)應(yīng)關(guān)鍵碼給v，并從v的右兄弟中借最左邊的那個(gè)關(guān)鍵碼給父親。同時(shí)也要對(duì)孩子進(jìn)行一些刪除和變換。
如刪除下圖中關(guān)鍵碼13.左兄弟為空，并且右兄弟沒(méi)有足夠孩子（動(dòng)圖gif）~
??顯然，由于一個(gè)節(jié)點(diǎn)至少有兩個(gè)孩子，其父親至少有兩個(gè)孩子，因此，這個(gè)節(jié)點(diǎn)v至少存在一個(gè)兄弟，并且這個(gè)兄弟一定恰好包含?m/2?- 1個(gè)關(guān)鍵碼，必然不可能為空。
??對(duì)于3階b樹(shù)而言，其兄弟有且僅有1個(gè)關(guān)鍵碼。不足以借它，所以可以向其父親，借一個(gè)關(guān)鍵碼，將兩個(gè)節(jié)點(diǎn)合并成一個(gè)節(jié)點(diǎn)。同時(shí)對(duì)孩子進(jìn)行調(diào)整。
如刪除下圖中關(guān)鍵碼1并且，借了一個(gè)關(guān)鍵碼之后，這個(gè)新節(jié)點(diǎn)，必然不可能越界。
4.右兄弟為空，并且左兄弟沒(méi)有足夠孩子（動(dòng)圖gif）~
同（3）分析
如刪除下圖中關(guān)鍵碼55.經(jīng)過(guò)（3）（4）后，父親發(fā)生下溢~
??但是從父親借一個(gè)關(guān)鍵碼，可能造成父親的下溢，因此，只需對(duì)父親再進(jìn)行一次下溢的操作，即可修復(fù)父親的下溢，當(dāng)然，可能會(huì)引發(fā)連鎖下溢，但最壞也不過(guò)下溢到根節(jié)點(diǎn)。
如刪除下圖中關(guān)鍵碼1??如果下溢到根節(jié)點(diǎn)，并且原來(lái)的根節(jié)點(diǎn)只有一個(gè)關(guān)鍵碼，借了之后就沒(méi)有了。那么此時(shí)就不妨刪除這個(gè)根節(jié)點(diǎn)，以其孩子作為根節(jié)點(diǎn)，從而取代之。此時(shí)，b樹(shù)的高度也必然下降一層。
這也是b樹(shù)變矮的唯一可能。6.show you my code~
注釋寫的很詳細(xì)了，可以自己對(duì)照?qǐng)D加深理解。 template<typename T> void BTree<T>::solveUnderFlow(BTNode<T>* v) {if ((_order + 1) / 2 <= static_cast<int>(v->_child.size()))//遞歸基，當(dāng)前節(jié)點(diǎn)未下溢return;BTNode<T>* p = v->_parent;//當(dāng)前節(jié)點(diǎn)的父親if (p == nullptr) {//遞歸基，如果父親為空節(jié)點(diǎn)，即說(shuō)明此時(shí)到達(dá)了根節(jié)點(diǎn)。if (!v->_key.size() && v->_child.at(0)) {//如果v此時(shí)的key為空，但卻有唯一的非空孩子_root = v->_child.at(0);//就將v的孩子作為根節(jié)點(diǎn)_root->_parent = nullptr;v->_child.at(0) = nullptr;//將v的這個(gè)孩子置為空delete v;//釋放vv = nullptr;}//整樹(shù)的高度降低一層return;//無(wú)論v此時(shí)是否為空，均達(dá)到遞歸基，若v不為空，則v就是根節(jié)點(diǎn)。}size_t rank = 0;while (p->_child.at(rank) != v)//找到v在其父親中所屬的孩子的位置rank++;/*1.向左兄弟借關(guān)鍵碼*/if (0 < rank) {//如果v不是p的第一個(gè)孩子BTNode<T>* ls = p->_child.at(rank - 1);//則左兄弟必然存在if ((_order + 1) / 2 < static_cast<int>(ls->_child.size())) {//如果左兄弟有充足的孩子v->_key.insert(v->_key.begin(), p->_key.at(rank - 1));//將父親插入v的最左邊//將左兄弟的最右邊的key設(shè)為父親的這個(gè)key的值p->_key.at(rank - 1) = ls->_key.at(ls->_key.size() - 1);ls->_key.pop_back();//刪除左兄弟的最右邊的key//將左兄弟的最右邊的孩子作為v的第一個(gè)孩子v->_child.insert(v->_child.begin(),ls->_child.back());ls->_child.pop_back();//刪除左兄弟的最右邊的child//如果左兄弟的右孩子不為空，即v此時(shí)的左孩子不為空，就重設(shè)左孩子的父親。if (v->_child.front())v->_child.front()->_parent = v;return;//至此，就完成了當(dāng)前層的下溢處理。同時(shí)，由于父親的key沒(méi)有減少，所以也完成了所有層的下溢處理。}}//如果執(zhí)行到此，說(shuō)明左兄弟沒(méi)有充足的孩子，或者根本沒(méi)進(jìn)入if語(yǔ)句內(nèi)，即rank=0，v沒(méi)有左兄弟/*2.向右兄弟借關(guān)鍵碼*/if (p->_child.size() - 1 > rank) {//如果v并非最后一個(gè)孩子，并且其左兄弟沒(méi)有充足的孩子時(shí)BTNode<T>* rs = p->_child.at(rank + 1);//則右兄弟必然存在if ((_order + 1) / 2 < static_cast<int>(rs->_child.size())) {//如果右兄弟有充足的孩子v->_key.push_back(p->_key.at(rank));//將父親插入v的最右邊p->_key.at(rank) = rs->_key.front();//將右兄弟的最左邊的key設(shè)為父親的這個(gè)key的值rs->_key.erase(rs->_key.begin());//刪除右兄弟的最左邊的keyv->_child.push_back(rs->_child.front());//將右兄弟的最左邊的孩子作為v的最后一個(gè)孩子rs->_child.erase(rs->_child.begin());//刪除右兄弟的最左邊的child//如果右兄弟的左孩子不為空，即v此時(shí)的右孩子不為空，就重設(shè)右孩子的父親。if (v->_child.back())v->_child.back()->_parent = v;return;//至此，就完成了當(dāng)前層的下溢處理。同時(shí)，由于父親的key沒(méi)有減少，所以也完成了所有層的下溢處理。}}//如果執(zhí)行到此，說(shuō)明右兄弟沒(méi)有充足的孩子，或者根本沒(méi)進(jìn)入if語(yǔ)句中，即v沒(méi)有右兄弟/*3.此時(shí)，要么左兄弟為空，并且右兄弟沒(méi)有足夠孩子；或者右兄弟為空，并且左兄弟沒(méi)有足夠孩子*//*左右兄弟不可能均為空*/if (0 < rank) {//與左兄弟和父親合并BTNode<T>* ls = p->_child.at(rank - 1);//左兄弟必然存在，一定不為空，但沒(méi)有足夠孩子ls->_key.push_back(p->_key.at(rank - 1));//在左兄弟的最右邊插入父親的keyp->_key.erase(p->_key.begin() + rank - 1);//并刪除父親對(duì)應(yīng)的節(jié)點(diǎn)//同時(shí)刪除父親這個(gè)節(jié)點(diǎn)的孩子，此時(shí)v不再是p的這個(gè)孩子p->_child.erase(p->_child.begin() + rank);ls->_child.push_back(v->_child.front());//將v的左孩子作為其左兄弟的最右孩子v->_child.erase(v->_child.begin());if (ls->_child.back())//并且重新設(shè)定父子關(guān)系ls->_child.back()->_parent = ls;//將v此時(shí)所有的key都插到其左兄弟的尾部ls->_key.insert(ls->_key.end(), v->_key.begin(), v->_key.end());v->_key.clear();//刪除v的key的所有節(jié)點(diǎn)for (auto v_c_Iter : v->_child) {ls->_child.push_back(v_c_Iter);//將v此時(shí)所有的child都插到其左兄弟的尾部if (ls->_child.back())//如果不為空,就重新設(shè)定父子關(guān)系ls->_child.back()->_parent = ls;}v->_child.clear();//刪除v的child的所有節(jié)點(diǎn)delete(v);//釋放vv = nullptr;}else {//與右兄弟和父親合并BTNode<T>* rs = p->_child.at(rank +1);//右兄弟必然存在，一定不為空，但沒(méi)有足夠孩子rs->_key.insert(rs->_key.begin(), p->_key.at(rank));//在右兄弟的最左邊插入父親的keyp->_key.erase(p->_key.begin() + rank);//并刪除父親對(duì)應(yīng)的節(jié)點(diǎn)//同時(shí)刪除父親這個(gè)節(jié)點(diǎn)的孩子，此時(shí)v不再是p的這個(gè)孩子p->_child.erase(p->_child.begin() + rank);rs->_child.insert(rs->_child.begin(), v->_child.back());//將v的右孩子作為右兄弟的最左孩子v->_child.pop_back();if (rs->_child.front())//并且重新設(shè)定父子關(guān)系rs->_child.front()->_parent = rs;//將v此時(shí)所有的key都插到其右兄弟的頭rs->_key.insert(rs->_key.begin(), v->_key.begin(), v->_key.end());v->_key.clear();//刪除v的key的所有節(jié)點(diǎn)//將v此時(shí)所有的child都插到其右兄弟的頭部rs->_child.insert(rs->_child.begin(), v->_child.begin(), v->_child.end());for (auto& rs_child : rs->_child) {if (rs_child) {//如果不為空,就重新設(shè)定父子關(guān)系//直到遍歷到?jīng)]有加v的child之前的原來(lái)的rs的child為止。if (rs_child->_parent == rs)break;rs_child->_parent = rs;}}v->_child.clear();//刪除v的child的所有節(jié)點(diǎn)delete v;//釋放vv = nullptr;}solveUnderFlow(p);//上升一層，如果有必要，繼續(xù)分裂，至多遞歸至logn層 }7.復(fù)雜度分析~
??與插入操作同理，在存有N個(gè)關(guān)鍵碼的m階B-樹(shù)中的每次關(guān)鍵碼刪除操作，都可以O(shè)(logmN)時(shí)間內(nèi)完成。
??另外同樣地，因某一關(guān)鍵碼的刪除而導(dǎo)致O(logmN)次合并操作的情況也極為罕見(jiàn)，單次刪除操作過(guò)程中平均只需做常數(shù)次節(jié)點(diǎn)的合并。
??故刪除的復(fù)雜度為O(logmN)。
（七）前序遍歷測(cè)試~
調(diào)用show_BTree函數(shù)。傳一個(gè)root()作為參數(shù)既可。
template<typename T> void BTree<T>::show_BTree(BTNode<T>* BT)const {//用的時(shí)候，傳一個(gè)root()if (BT == nullptr) {cout << "BTree 不存在" << endl;return;}bool has_child = false;cout << "[";for (auto it = BT->_key.begin(); it != BT->_key.end(); ++it) {if (it != BT->_key.begin())cout << " ";cout << *it;}cout << "]";for (size_t i = 0; i <= BT->_key.size(); ++i) {if (BT->_child.at(i) != nullptr) {if (i == 0) {cout << "<";}else {cout << ",";}show_BTree(BT->_child.at(i));has_child = true;}}if (has_child)cout << ">"; }四.結(jié)果測(cè)試~
1.插入測(cè)試~
#include<iostream> #include "BTree.h"using namespace std; using namespace my_btree;int main() {BTree b(3);for (int i = 0; i <7; i++) {b.insert(i);}b.show_BTree(b.root());return 0; }輸出結(jié)果為
[3]<[1]<[0],[2]>,[5]<[4],[6]>>
更具體點(diǎn)為
2.刪除測(cè)試~
#include<iostream> #include "BTree.h"using namespace std; using namespace my_btree;int main() {BTree b(3);for (int i = 0; i <7; i++) {b.insert(i);}b.show_BTree(b.root());cout << endl;for (int i = 0; i < 7; i++) {b.remove(i);b.show_BTree(b.root());cout << endl;}return 0; }輸出結(jié)果為
[3]<[1]<[0],[2]>,[5]<[4],[6]>> [3 5]<[1 2],[4],[6]> [3 5]<[2],[4],[6]> [5]<[3 4],[6]> [5]<[4],[6]> [5 6] [6] []五.結(jié)語(yǔ)~
??理解b樹(shù)，特別是(2,4)樹(shù)，是理解紅黑樹(shù)的基礎(chǔ)，紅黑樹(shù)的代碼見(jiàn)紅黑樹(shù)
??碼字不易，此篇高達(dá)1w5千字，有任何疑問(wèn)可以在下方留言；代碼有任何紕漏之處，希望廣大讀者可以進(jìn)行指正。
??如果你覺(jué)得對(duì)你有所幫助，可以點(diǎn)個(gè)贊。
總結(jié)
以上是生活随笔為你收集整理的真c++创建B树（非c with class）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： 社工要掌握哪些计算机基本操作,【作为一名
- 下一篇： 程序依赖图（Program Depend