伸展树

概念：伸展树是一种自调整二叉搜索树。每次访问后通过旋转将目标结点伸展到根，使近期访问的结点更靠近根，操作具有均摊对数复杂度。

关键步骤

维护左右儿子与父亲；旋转时先连接祖父、再换父子关系。伸展中，目标和父亲同为左/右儿子做双旋（zig-zig），方向不同则做 zig-zag。

void rotate(int x){
    int y=fa[x], z=fa[y], k=(ch[y][1]==x);
    if(z) ch[z][ch[z][1]==y]=x;
    fa[x]=z; ch[y][k]=ch[x][k^1];
    if(ch[x][k^1]) fa[ch[x][k^1]]=y;
    ch[x][k^1]=y; fa[y]=x;
}

复杂度

单次操作最坏可为 O(n)，但插入、删除、查找、分裂和合并的均摊复杂度均为 O(log n)，空间 O(n)。实现须谨慎维护根和父指针。