关于平衡树基础[违规紫衫]
  • 板块灌水区
  • 楼主xuxinyi
  • 当前回复12
  • 已保存回复12
  • 发布时间2022/12/10 18:21
  • 上次更新2023/10/26 23:53:41
查看原帖
关于平衡树基础[违规紫衫]
373422
xuxinyi楼主2022/12/10 18:21

我正在oiwiki上自学平衡树 然后看到删除部分
有一点看不懂这个代码

int deletemin(int& o) {
  if (!lc[o]) {
    int u = o;
    o = rc[o];
    return u;
  } else {
    int u = deletemin(lc[o]);
    siz[o] -= cnt[u];
    return u;
  }
}

void del(int& o, int v) {
  // 注意 o 有可能会被修改
  siz[o]--;
  if (val[o] == v) {
    if (cnt[o] > 1) {
      cnt[o]--;
      return;
    }
    if (lc[o] && rc[o]) o = deletemin(rc[o]);
    // 这里以找右子树的最小值为例
    else
      o = lc[o] + rc[o];//就是这两行看不懂
    return;
  }
  if (val[o] > v) del(lc[o], v);
  if (val[o] < v) del(rc[o], v);
}

有看算法介绍但是还是不理解(lc[o] && rc[o]) o 是什么意思 然后也不理解为什么要 o = lc[o] + rc[o];

2022/12/10 18:21
加载中...