Splay 规定:每访问一个节点后都要强制将其旋转到根节点。
这里面就分了三类情况来讨论:
1、如果x的父亲是根节点,直接将x左旋或右旋
2、如果x的父亲不是根节点,且x和父亲的儿子类型相同(也就是说,它们都是左子节点或都是右子节点),首先将其父亲左旋或右旋,然后将x右旋或左旋
3、如果x的父亲不是根节点,且x和父亲的儿子类型不同,将x左旋再右旋、或者右旋再左旋.
splay操作就是从被访问的节点x开始,递归地做上面的操作,直到x是根节点。并且,Splay之后,整棵树还是二叉搜索树。
插入操作是一个比较复杂的过程,具体步骤如下(假设插入的值为x ):
删除操作也是一个比较复杂的操作,具体步骤如下:
首先将x旋转到根的位置。
应用二叉搜索树的查找即可,只是最后要对找到的这个点进行Splay操作。
设k为剩余排名,初始时,k=x
在找到之后,要对那个节点进行Splay操作。