伸展树是二叉查找树的一种改进，与二叉查找树一样，伸展树也具有有序性。即伸展树中的每一个节点 x 都满足：该节点左子树中的每一个元素都小于 x， 而其右子树中的每一个元素都大于 x。与普通二叉查找树不同的是，伸展树可以自我调整，这就要依靠伸展操作 Splay(x,S)。
利用 Splay 操作，我们可以在伸展树 S 上进行如下运算：
- Find(x,S)：判断元素 x 是否在伸展树 S 表示的有序集中。 首先，与在二叉查找树中的查找操作一样，在伸展树中查找元素 x。如果 x 在树中，则再执行 Splay(x,S)调整伸展树。
- Insert(x,S)：将元素 x 插入伸展树 S 表示的有序集中。 首先，也与处理普通的二叉查找树一样，将 x 插入到伸展树 S 中的相应位置 上，再执行 Splay(x,S)。
- Delete(x,S)：将元素 x 从伸展树 S 所表示的有序集中删除。 首先，用在二叉查找树中查找元素的方法找到 x 的位置。如果 x 没有孩子或 只有一个孩子，那么直接将 x 删去，并通过 Splay 操作，将 x 节点的父节点调整 到伸展树的根节点处。否则，则向下查找 x 的后继 y，用 y 替代 x 的位置，最后 执行 Splay(y,S)，将 y 调整为伸展树的根。
- Join(S1,S2)：将两个伸展树 S1 与 S2 合并成为一个伸展树。其中 S1 的所
有元素都小于 S2 的所有元素。
首先，我们找到伸展树 S1 中最大的一个元素 x，再通过 Splay(x,S1)将 x 调
整到伸展树 S1 的根。然后再将 S2 作为 x 节点的右子树。这样，就得到了新的
伸展树 S。如图所示
- Split(x,S)：以 x 为界，将伸展树 S 分离为两棵伸展树 S1 和 S2，其中 S1
中所有元素都小于 x，S2 中的所有元素都大于 x。
首先执行 Find(x,S)，将元素 x 调整为伸展树的根节点，则 x 的左子树就是
S1，而右子树为 S2。如图所示
