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