0001 template <typename T> void BTree<T>::solveUnderflow() { //修复下溢
0002    while (_a > _x->way.size()) { //_x下溢：|way| = a-1 = |key|+1
0003       BTNP<T> p = _x->parent;
0004       if (!p) { //情况#0：已到树根
0005          if ((_x->key.size() < 1) && (0 < _N)) //若树根已空（树还没空），则
0006             { _root = _x->way[0];  _root->parent = nullptr;  delete _x; } //整树降低一层
0007          break; //随即收工
0008       } //情况#0
0009       _k = p->way.find(_x); //确定_x在p中的秩
0010       BTNP<T> ls  =  (0 < _k) ? p->way[_k-1] : nullptr; //左兄弟
0011       if (ls && (_a < ls->way.size())) { //情况#1L：_x有个足够“胖”的左兄弟
0012          _x->key.insert(0, p->key[_k-1]); //p的轴点关键码转入_x（作为最小关键码）
0013          p->key[_k-1] = ls->key.remove(); //ls的最大关键码转入p
0014          _x->way.insert(0, ls->way.remove()); //ls的最大孩子过继给_x
0015          if (_x->way[0]) _x->way[0]->parent = _x; //作为_x的最小孩子
0016          break; //随即收工
0017       } //情况#1L
0018       BTNP<T> rs = (_k < p->key.size()) ? p->way[_k+1] : nullptr; //右兄弟
0019       if (rs && (_a < rs->way.size())) { //情况#1R：_x有个足够“胖”的右兄弟
0020          _x->key.insert(p->key[_k]); //p的轴点关键码转入_x（作为最大关键码）
0021          p->key[_k] = rs->key.remove(0); //rs的最小关键码转入p
0022          _x->way.insert(rs->way.remove(0)); //rs的最小侧孩子过继给_x
0023          if (_x->way[_a-1]) _x->way[_a-1]->parent = _x; //作为_x的最大孩子
0024          break; //随即收工
0025       } //情况#1R
0026       //情况#2：若左、右兄弟（至少存在一个）均不够“胖”
0027       if (rs) { ls = _x;  _k++; } //则_x与兄弟（右兄弟优先）合并
0028       else rs = _x; //无论选择哪个兄弟，按ls、rs命名之后，以下都是将rs归入ls
0029       ls->key.insert(p->key.remove(_k-1));  p->way.remove(_k); //p吐还轴点
0030       rs->way.traverse(LinkParent<T>(ls)); //rs的孩子们统一指向ls
0031       ls->way.insert(rs->way);  ls->key.insert(rs->key); //过继子树及关键码
0032       delete rs;  _x = p; //rs功成身退；_x上溯一层——至多可能上溯O(logn)层、合并O(logn)次
0033    } //while
0034 } //solveUnderflow