0001 template <typename T> void RedBlack<T>::solveDoubleRed() {
0002    for (BNP<T> x = _x; ; ) {
0003       if (!x->parent) //若已（递归）转至树根，则将其转黑，整树黑高度也随之递增
0004          {  x->color = RBT_BLACK; break;  } //否则，x的父亲p必存在
0005       BNP<T> p = x->parent; if (IsBlack(p)) break; //若p为黑，则可终止调整
0006       BNP<T> g = p->parent; //否则x的祖父必存在且为黑
0007       BNP<T> u = Uncle(x); //以下，视x叔父的颜色分别处理
0008       if (IsBlack(u)) { //RR-1：u为黑（含nullptr）
0009          rotate(g)->color = RBT_BLACK; //绕g旋转之后，新根
0010          g->color = RBT_RED; break; //与原根g互换颜色，即完成修复
0011       } else { //RR-2：u为红
0012          p->color = u->color = RBT_BLACK; //p、u由红转黑
0013          g->color = RBT_RED; g->height++; //在B-树中g是上交的关键码，故转红
0014          x = g; //继续上溯
0015       } //else
0016    } //for
0017 } //solveDoubleRed