0001 template <typename T> BNP<T> Splay<T>::splay(BNP<T> v) { //将节点v伸展至根
0002    for (BNP<T> p, g; (p = v->parent) && (g = p->parent); ) { //自下而上，做双层伸展
0003       if (BNP<T> gg = v->parent = g->parent) //伸展之后
0004          g == gg->lc ? gg->attachLc(v) : gg->attachRc(v); //v应以原曾祖父为父
0005       switch (((p == g->rc) << 1) | (v == p->rc)) { //视p、v之拐向，分四种情况做伸展
0006          case 0b00 : g->attachLc(p->rc);  p->attachLc(v->rc);
0007                      p->attachRc(g);  v->attachRc(p);  break; //LL
0008          case 0b01 : p->attachRc(v->lc);  g->attachLc(v->rc);
0009                      v->attachRc(g);  v->attachLc(p);  break; //LR
0010          case 0b10 : p->attachLc(v->rc);  g->attachRc(v->lc);
0011                      v->attachLc(g);  v->attachRc(p);  break; //RL
0012          default :   g->attachRc(p->lc);  p->attachRc(v->lc);
0013                      p->attachLc(g);  v->attachLc(p);  break; //0b11 ~ RR
0014       } //switch
0015       g->updateHeight(); p->updateHeight();
0016    } //for: 双层伸展
0017    if (BNP<T> p = v->parent) { //最后一步，可能还要做一次单层伸展
0018       if (v == p->lc) { p->attachLc(v->rc); v->attachRc(p); } //L情况
0019       else              { p->attachRc(v->lc); v->attachLc(p); } //R情况
0020       p->updateHeight(); v->parent = nullptr;
0021    } //if: 单层伸展
0022    (_root = v)->updateHeight(); return v; //v终成树根
0023 } //splay