社区讨论

关于 FHQ-Treap 合并顺序与分裂顺序的关系

eendswitch
学术版参与者 8已保存回复 9

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
9 条
当前快照
1 份
快照标识符
@m5tlvp2d
此快照首次捕获于
2025/01/12 20:43
去年
此快照最后确认于
2025/01/13 10:14
去年
查看原帖
rt。屡次遇到了。以删除操作为例：
CPP
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 ;
}
这段代码是错误的，而：
CPP
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 ;
}
这一段代码是正确的。
所以合并顺序与分裂顺序如何安排才能使在操作的前提下不改变原先平衡树的形态？如果有严谨证明更好。
谢谢。

回复

共 9 条回复，欢迎继续交流。

正在加载回复...