splay

splay的长度可能会被干到\(O(N)\)（考虑从\(1\)到\(n\)依次插入）,但是只要访问过一次最远的节点，splay就会通过把最远节点旋转到根这个过程来调整树高，直至\(O(\log N)\)级别，均摊来说，只要访问的次数够多，均摊复杂度就是\(O(\log N)\);如果不访问，树高可能短暂存在\(O(N)\)的状态，~~但是不访问复杂度是0 (乐~~

delete

// 1. 有前驱后继
pre = getpre(x);
nxt = getnxt(x);
splay(pre, 0);
splay(nxt, pre);
delete(root->right->left);

// 2. 只用查找
find(x);
left = root->left;
right = root->right;
delete(root);
if(op == 1){ // 右并到左
    findmax(left);
    left->right = right;
}else{ // 左并到右
    findmin(right);
    right->left = left;
}