多路平衡樹(shù)—BTree（B樹(shù)）

      B樹(shù)屬于多叉樹(shù)，也稱多路平衡樹(shù)。有些地方也將B樹(shù)稱為'B-樹(shù)',這里‘-’不表示減號(hào)。

■B樹(shù)的主要性質(zhì)：

              （1）根節(jié)點(diǎn)至少有兩個(gè)孩子。

              （2）每個(gè)非根節(jié)點(diǎn)為[[M/2], M]個(gè)孩子，這里[M/2]表示向上取整。

              （3）每個(gè)非根節(jié)點(diǎn)都有[[M/2], M-1]個(gè)關(guān)鍵字，并且以升序排列。

              （4）K[i]和k[i+1]之間的孩子節(jié)點(diǎn)的值介于k[i]與k[i+1]之間。（5）所有葉子節(jié)點(diǎn)都在同一層。

■下面是一個(gè)簡(jiǎn)單的3階B樹(shù)：

     如果想給B樹(shù)中，插入一個(gè)關(guān)鍵字，并且關(guān)鍵字的數(shù)目超過(guò)，且就需要對(duì)樹(shù)進(jìn)行調(diào)整。那就需要尋找關(guān)鍵字的中位數(shù)，那怎樣快速的尋找關(guān)鍵字呢？

     ▲思路一：

            將所有的關(guān)鍵字進(jìn)行排序，然后將中位數(shù)尋找出來(lái)。

      ▲思路二：

              利用快速排序的思想，選一個(gè)key值，如果左邊個(gè)數(shù)等于右邊個(gè)數(shù)，則中位數(shù)找到，如果沒(méi)有，就在個(gè)數(shù)多的一邊找出中間位置的關(guān)鍵字作為key值，直到key的左 = 右，則找到關(guān)鍵字，這樣的效率更高。

■下面是插入關(guān)鍵字示例：

■下面是具體的實(shí)現(xiàn)代碼：

#pragma once
//實(shí)現(xiàn)B樹(shù)（實(shí)際就是多叉樹(shù)）

/*
性質(zhì)：（1）根節(jié)點(diǎn)至少要2個(gè)節(jié)點(diǎn)
      （2）每個(gè)非根節(jié)點(diǎn)為[(M/2), M]個(gè)孩子
   （3）滿足左孩子值小于根節(jié)點(diǎn)，右孩子值大于根節(jié)點(diǎn)
   （4）并且每個(gè)非根節(jié)點(diǎn)有[(M/2)-1, M-1]個(gè)關(guān)鍵字，并且以升序排列
   （5）key[i]和key[i+1]之間的孩子節(jié)點(diǎn)值介于key[i]和key[i+1]之間
   （6）所有節(jié)點(diǎn)都在同一層
*/

//實(shí)現(xiàn)k形式的結(jié)構(gòu)
//如果要實(shí)現(xiàn)K，V結(jié)構(gòu)，就需要?jiǎng)?chuàng)建一個(gè)結(jié)構(gòu)體，包括K，V
template <class K, int M = 3>   //實(shí)現(xiàn)M為缺省的，值最好取計(jì)數(shù)，能夠更加方便的求取中位數(shù)
struct BTreeNode
{
     K _keys[M];      //關(guān)鍵字的至多個(gè)數(shù)，多預(yù)留一個(gè)位置是可以更加方便的求取中位數(shù)
     BTreeNode<K, M>* _subs[M + 1];      //孩子節(jié)點(diǎn)的最大數(shù)目
     BTreeNode<K, M>* _parent;    //指向父親節(jié)點(diǎn)
     size_t _size;     //數(shù)組中存在的有效關(guān)鍵字的個(gè)數(shù)
     
     BTreeNode()           //構(gòu)造B樹(shù)節(jié)點(diǎn)
          :_parent(NULL)
          , _size(0)
     {
          for (int i = 0; i <= M; ++i)
          {
               _subs[i] = NULL;
          }
     }
};

template <class K, class V>    //需要返回兩個(gè)參數(shù)，使用結(jié)構(gòu)體
struct Pair
{
     K _first;
     V _second;
     
     Pair(const K& key = K(), const V& value = V())     //缺省參數(shù)，會(huì)調(diào)用默認(rèn)構(gòu)造函數(shù)
          :_first(key)
          , _second(value)
     { }
};

template <class K, int M = 3>
class BTree
{
     typedef BTreeNode<K, M> Node;
public:
     BTree()          //無(wú)參構(gòu)造
          :_root(NULL)
     {}
     
     Pair<Node*, int>  Find(const K& key)      //查找
     {
          Node* parent = NULL;
          Node* cur = _root;
          while (cur)
          {
               int index = 0;
               while (index < cur->_size)     //在一個(gè)節(jié)點(diǎn)中找相同的關(guān)鍵字
               {
                    if (key == cur->_keys[index])
                    {
                         return Pair<Node*, int>(cur, index);
                    }
                    else if (key < cur->_keys[index])
                    {
                         break;
                    }
                    else
                    {
                         index++;
                    }
               }
               parent = cur;
               cur = cur->_subs[index];
          }
          return Pair<Node*, int>(parent, -1);
     }
     
     bool Insert(const K& key)     //插入節(jié)點(diǎn)
     {
          //沒(méi)有節(jié)點(diǎn)
          if (_root == NULL)
          {
               _root = new Node;
               _root->_keys[0] = key;
               _root->_size++;
               return true;
          }
          
          //判斷返回值
          Pair<Node*, int> cur = Find(key);
          if (cur._second != -1)
          {
               return false;
          }
          
          //在節(jié)點(diǎn)cur中插入key和sub
          Node* str = cur._first;
          K InsertKey = key;
          Node* sub = NULL;
          while (1)
          {
               _InsertKey(str, InsertKey, sub);    
               if (str->_size < M)    //插入后，節(jié)點(diǎn)中的數(shù)據(jù)個(gè)數(shù)沒(méi)有超過(guò)規(guī)定的
               {
                    return true;
               }
               //插入數(shù)據(jù)后，節(jié)點(diǎn)的數(shù)據(jù)個(gè)數(shù)大于規(guī)定的數(shù)據(jù)個(gè)數(shù)，需要將節(jié)點(diǎn)進(jìn)行分裂
               int mid = (str->_size - 1) / 2;
               int index = 0;
               Node* tmp = new Node;
               
               //先拷貝key
               for (int i = mid + 1; i < str->_size; i++)
               {
                    tmp->_keys[index++] = str->_keys[i];
                    tmp->_size++;
               }
               
               //后拷貝sub
               for (int i = mid + 1; i < str->_size; i++)
               {
                    tmp->_subs[index + 1] = str->_subs[i];
                    if (str->_subs[i])
                    {
                         str->_subs[i]->_parent = tmp;
                    }
               }
               str->_size = (str->_size - 1) / 2;    //更改str的大小
               if (str->_parent == NULL)
               {
                    _root = new Node;
                    _root->_keys[0] = tmp->_keys[mid];
                    _root->_subs[0] = str;
                    _root->_subs[1] = tmp;
                    _root->_size = 1;
                    str->_parent = _root;
                    tmp->_parent = _root;
               }
               else
               {
                    InsertKey = str->_keys[mid];
                    sub = tmp;
                    str = str->_parent;
               }
          }
          return true;
     }
     
     void _InsertKey(Node* cur, const K& key, Node* sub)     //插入key值
     {
          int index = cur->_size - 1;
          while (index >= 0 && cur->_keys[index] > key)    //將后面的數(shù)據(jù)向后移一位
          {
               cur->_keys[index + 1] = cur->_keys[index];
               cur->_subs[index + 2] = cur->_subs[index + 1];
               --index;
          }
          cur->_keys[index + 1] = key;    //插入數(shù)據(jù)及其子節(jié)點(diǎn)
          cur->_subs[index + 2] = sub;
          if (sub)
               sub->_parent = cur;
          cur->_size++;
     }
     
     void InOrder()
     {
          _InOrder(_root);
     }
     
     void _InOrder(Node* root)
     {
          if (root == NULL)
          {
               return;
          }
          for (int i = 0; i < root->_size; i++)
          {
               cout << root->_keys[i] << " ";
               _InOrder(root->_subs[i]);
          }
     }
 
protected:
     Node* _root;
};

void Test()
{
     int a[] = { 53, 75, 139, 49, 145, 36, 101 };
     BTree<int, 1023> t;
     for (size_t i = 0; i < sizeof(a) / sizeof(a[0]); ++i)
     {
          t.Insert(a[i]);
     }
     t.InOrder();
}