0001 template <typename T> void RedBlack<T>::solveDoubleBlack() {
0002    while (_p) {
0003       BNP<T> s = (_r == _p->lc) ? _p->rc : _p->lc; //_r（或为nullptr）的兄弟s（必非nullptr）
0004       if (IsBlack(s)) //兄弟s为黑
0005          if (IsRed(s->lc) || IsRed(s->rc)) { //黑s有红孩子：BB-1
0006             BNP<T> b = rotate(_p); //沿_p、s、t旋转后，新根继承原根的
0007             b->color = _p->color; b->height = _p->height + 1; //颜色和黑高度
0008             b->lc->color = b->rc->color = RBT_BLACK; //左子、右子（均必非nullptr）染黑
0009             break; //一蹴而就
0010          } else { //黑s无红孩子
0011             s->color = RBT_RED;  _p->height--; //s转红，_p坍塌一层
0012             if (IsRed(_p)) { _p->color = RBT_BLACK; break; } //BB-2R：_p转黑，黑高度不变
0013             else { _r = _p;  _p = _r->parent; } //BB-2B：黑_p的黑高度下降，继续上溯
0014          } //else
0015       else { //兄弟s为红：BB-3
0016          s->color = RBT_BLACK;  _p->color = RBT_RED; //s转黑，_p转红
0017          rotate(_p); //绕_p旋转之后，继续上溯（只可能转入BB-1或BB-2R）
0018       } //else
0019    } //while
0020 } //solveDoubleBlack