bool del(int &k, int x) { // 删除节点
if (!k) return false;
if (val[k] == x) {
if (w[k] > 1) {
w[k]--;
size_[k]--;
return true;
}
if (l[k] == 0 || r[k] == 0) {
k = l[k] + r[k];
return true;
} else if (rnd[l[k]] < rnd[r[k]]) {
rrotate(k);
return del(k, x); // Why not del(r[k], x)?
} else {
lrotate(k);
return del(k, x);// Why not del(l[k], x)?
}
} else if (val[k] < x) {
bool succ = del(r[k], x);
if (succ) size_[k]--;
return succ;
} else {
bool succ = del(l[k], x);
if (succ) size_[k]--;
return succ;
}
}
原链接这一段有旋转操作
初次接触平衡树,有很多理解不到位的地方,请多指教。
问题是注释这两行,删除数量为 1 的节点,往下面旋转到最下面然后删除。
但是rotate返回的节点不是操作后根节点吗?那样又删除一遍自己是不是没有意义?