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 ;
}
这一段代码是正确的。
所以合并顺序与分裂顺序如何安排才能使在操作的前提下不改变原先平衡树的形态?如果有严谨证明更好。
谢谢。