看oiwiki的treap板子时的疑惑
查看原帖
看oiwiki的treap板子时的疑惑
356117
落木之樱meow楼主2024/9/11 21:13
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;
    }
  }

原链接这一段有旋转操作20240911210451

初次接触平衡树,有很多理解不到位的地方,请多指教。

问题是注释这两行,删除数量为 11 的节点,往下面旋转到最下面然后删除。

但是rotate返回的节点不是操作后根节点吗?那样又删除一遍自己是不是没有意义?

2024/9/11 21:13
加载中...