多路平衡樹—BTree（B樹）

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

■B樹的主要性質：

              （1）根節點至少有兩個孩子。

              （2）每個非根節點為[[M/2], M]個孩子，這里[M/2]表示向上取整。

              （3）每個非根節點都有[[M/2], M-1]個關鍵字，并且以升序排列。

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

■下面是一個簡單的3階B樹：

     如果想給B樹中，插入一個關鍵字，并且關鍵字的數目超過，且就需要對樹進行調整。那就需要尋找關鍵字的中位數，那怎樣快速的尋找關鍵字呢？

     ▲思路一：

            將所有的關鍵字進行排序，然后將中位數尋找出來。

      ▲思路二：

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

■下面是插入關鍵字示例：

■下面是具體的實現代碼：

#pragma once
//實現B樹（實際就是多叉樹）

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

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

template <class K, class V>    //需要返回兩個參數，使用結構體
struct Pair
{
     K _first;
     V _second;
     
     Pair(const K& key = K(), const V& value = V())     //缺省參數，會調用默認構造函數
          :_first(key)
          , _second(value)
     { }
};

template <class K, int M = 3>
class BTree
{
     typedef BTreeNode<K, M> Node;
public:
     BTree()          //無參構造
          :_root(NULL)
     {}
     
     Pair<Node*, int>  Find(const K& key)      //查找
     {
          Node* parent = NULL;
          Node* cur = _root;
          while (cur)
          {
               int index = 0;
               while (index < cur->_size)     //在一個節點中找相同的關鍵字
               {
                    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)     //插入節點
     {
          //沒有節點
          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;
          }
          
          //在節點cur中插入key和sub
          Node* str = cur._first;
          K InsertKey = key;
          Node* sub = NULL;
          while (1)
          {
               _InsertKey(str, InsertKey, sub);    
               if (str->_size < M)    //插入后，節點中的數據個數沒有超過規定的
               {
                    return true;
               }
               //插入數據后，節點的數據個數大于規定的數據個數，需要將節點進行分裂
               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)    //將后面的數據向后移一位
          {
               cur->_keys[index + 1] = cur->_keys[index];
               cur->_subs[index + 2] = cur->_subs[index + 1];
               --index;
          }
          cur->_keys[index + 1] = key;    //插入數據及其子節點
          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();
}