关于 FHQ-Treap 合并顺序与分裂顺序的关系
  • 板块学术版
  • 楼主endswitch
  • 当前回复9
  • 已保存回复9
  • 发布时间2025/1/12 20:41
  • 上次更新2025/1/13 10:14:23
查看原帖
关于 FHQ-Treap 合并顺序与分裂顺序的关系
773915
endswitch楼主2025/1/12 20:41

rt。屡次遇到了。以删除操作为例:

inline void deleted(int p) {
  int x = 0, y = 0, z = 0;
  
  split(root, p, x, y);
  split(x, p - 1, x, z);
  
  z = merge(ls[z], rs[z]);
  root = merge(z, merge(x, y));
  
  return ;
}

这段代码是错误的,而:

inline void deleted(int p) {
  int x = 0, y = 0, z = 0;
  
  split(root, p, x, y);
  split(x, p - 1, x, z);
  
  z = merge(ls[z], rs[z]);
  root = merge(merge(x, z), y);
  
  return ;
}

这一段代码是正确的。

所以合并顺序与分裂顺序如何安排才能使在操作的前提下不改变原先平衡树的形态?如果有严谨证明更好。

谢谢。

2025/1/12 20:41
加载中...