0001 template <typename T> struct LinkParent {
0002    BTNP<T> parent;  LinkParent(BTNP<T> p) : parent(p) {}
0003    void operator()(BTNP<T> x) { if (x) x->parent = parent; }
0004 }; //LinkParent
0005 template <typename T> void BTree<T>::solveOverflow() { //修复上溢
0006    while (_b < _x->way.size()) { //_x上溢：|way|-1 == b == |key|
0007       Rank s = _b - _a+1; //_x将以中位数为界，将后缀转移至
0008       BTNP<T> u = new BTNode<T>(_b, _x->height); //分裂出来的新节点u
0009       u->key.insert(0, _x->key, s, _b);  _x->key.remove(s, _b); //关键码
0010       u->way.insert(0, _x->way, s, _b+1);  _x->way.remove(s, _b+1); //孩子
0011       u->way.traverse(LinkParent<T>(u)); //u的孩子们统一指向u
0012       BTNP<T> p = _x->parent; //_x的父亲p：若为空，则创建之，且
0013       if (!p) _root = p = new BTNode<T>(_b, _x->height + 1, _x); //全树长高一层
0014       _k = p->way.find(_x); //确定_x在p中的秩
0015       p->key.insert(_k, _x->key.remove(s-1)); //轴点上升
0016       p->way.insert(_k+1, u);  u->parent = p; //u与p互联
0017       _x = p; //上升一层，继续修复——至多可能上溯O(logn)层、分裂O(logn)次
0018    } //while
0019 } //solveOverflow