0001 template <typename T> //关键码删除后若节点下溢，则做节点旋转或合并处理
0002 void BTree<T>::solveUnderflow( BTNodePosi<T> v ) {
0003    while ( ( _m + 1 ) / 2 > v->child.size() ) { //除非当前节点并未下溢
0004       BTNodePosi<T> p = v->parent;
0005       if ( !p ) { //已到根节点（两个孩子即可）
0006          if ( !v->key.size() && v->child[0] ) {
0007             //但倘若作为树根的v已不含关键码，却有（唯一的）非空孩子，则
0008             _root = v->child[0]; _root->parent = NULL; //这个节点可被跳过
0009             v->child[0] = NULL; delete v; //并因不再有用而被销毁
0010          } //整树高度降低一层
0011          return;
0012       }
0013       Rank r = 0;
0014       while ( p->child[r] != v ) r++;
0015       //确定v是p的第r个孩子——此时v可能不含关键码，故不能通过关键码查找
0016       //另外，在实现了孩子指针的判等器之后，也可直接调用Vector::find()定位
0017    // 情况1：向左兄弟借关键码
0018       if ( 0 < r ) { //若v不是p的第一个孩子，则
0019          BTNodePosi<T> ls = p->child[r - 1]; //左兄弟必存在
0020          if ( ( _m + 1 ) / 2 < ls->child.size() ) { //若该兄弟足够“胖”，则
0021             v->key.insert( 0, p->key[r - 1] ); // p借出一个关键码给v（作为最小关键码）
0022             p->key[r - 1] = ls->key.remove( ls->key.size() - 1 ); // ls的最大关键码转入p
0023             v->child.insert( 0, ls->child.remove( ls->child.size() - 1 ) );
0024             //同时ls的最右侧孩子过继给v
0025             if ( v->child[0] ) v->child[0]->parent = v; //作为v的最左侧孩子
0026             return; //至此，通过右旋已完成当前层（以及所有层）的下溢处理
0027          }
0028       } //至此，左兄弟要么为空，要么太“瘦”
0029    // 情况2：向右兄弟借关键码
0030       if ( p->child.size() - 1 > r ) { //若v不是p的最后一个孩子，则
0031          BTNodePosi<T> rs = p->child[r + 1]; //右兄弟必存在
0032          if ( ( _m + 1 ) / 2 < rs->child.size() ) { //若该兄弟足够“胖”，则
0033             v->key.insert( v->key.size(),
0034                            p->key[r] ); // p借出一个关键码给v（作为最大关键码）
0035             p->key[r] = rs->key.remove( 0 ); // rs的最小关键码转入p
0036             v->child.insert( v->child.size(), rs->child.remove( 0 ) );
0037             //同时rs的最左侧孩子过继给v
0038             if ( v->child[v->child.size() - 1] ) //作为v的最右侧孩子
0039                v->child[v->child.size() - 1]->parent = v;
0040             return; //至此，通过左旋已完成当前层（以及所有层）的下溢处理
0041          }
0042       } //至此，右兄弟要么为空，要么太“瘦”
0043    // 情况3：左、右兄弟要么为空（但不可能同时），要么都太“瘦”——合并
0044       if ( 0 < r ) { //与左兄弟合并
0045          BTNodePosi<T> ls = p->child[r - 1]; //左兄弟必存在
0046          ls->key.insert( ls->key.size(), p->key.remove( r - 1 ) ); p->child.remove( r );
0047          // p的第r - 1个关键码转入ls，v不再是p的第r个孩子
0048          ls->child.insert( ls->child.size(), v->child.remove( 0 ) );
0049          if ( ls->child[ls->child.size() - 1] ) // v的最左侧孩子过继给ls做最右侧孩子
0050             ls->child[ls->child.size() - 1]->parent = ls;
0051          while ( !v->key.empty() ) { // v剩余的关键码和孩子，依次转入ls
0052             ls->key.insert( ls->key.size(), v->key.remove( 0 ) );
0053             ls->child.insert( ls->child.size(), v->child.remove( 0 ) );
0054             if ( ls->child[ls->child.size() - 1] ) 
0055                ls->child[ls->child.size() - 1]->parent = ls;
0056          }
0057          delete v; //释放v
0058       } else { //与右兄弟合并
0059          BTNodePosi<T> rs = p->child[r + 1]; //右兄弟必存在
0060          rs->key.insert( 0, p->key.remove( r ) ); p->child.remove( r );
0061          // p的第r个关键码转入rs，v不再是p的第r个孩子
0062          rs->child.insert( 0, v->child.remove( v->child.size() - 1 ) );
0063          if ( rs->child[0] ) rs->child[0]->parent = rs; // v的最右侧孩子过继给rs做最左侧孩子
0064          while ( !v->key.empty() ) { // v剩余的关键码和孩子，依次转入rs
0065             rs->key.insert( 0, v->key.remove( v->key.size() - 1 ) );
0066             rs->child.insert( 0, v->child.remove( v->child.size() - 1 ) );
0067             if ( rs->child[0] ) rs->child[0]->parent = rs;
0068          }
0069          delete v; //释放v
0070       }
0071       v = p; //上升一层，如有必要则继续旋转或合并——至多O(logn)层
0072    } //while
0073 }