Can you summarize the following document?
        
  伸展树的自我平衡使其拥有良好的性能,因为频繁访问的节点会被移动到更靠近根节点,进而获得更快的访问速度。

  伸展树最显著的缺点是它有可能会变成一条链。例如,在以非递减顺序访问全部n个之后就会出现这种情况。此时树的高度对应于最坏情况的时间效率,操作的实际时间效率可能很低。然而均摊的最坏情况是对数级的——formula_1。  即使以“只读”方式(例如通过查找操作)访问伸展树,其结构也可能会发生变化。这使得伸展树在多线程环境下会变得很复杂。具体而言,如果允许多个线程同时执行查找操作,则需要额外的维护和操作。这也使得它们不适合在纯粹的函数式编程中普遍使用,尽管用于实现优先级队列的方式不多。

  

  当一个节点"x"被访问过后,伸展操作会将"x"移动到根节点。为了进行伸展操作,我们会进行一系列的旋转,每次旋转会使"x"离根节点更近。通过每次访问节点后的伸展操作,最近访问的节点都会离根节点更近,且伸展树也会大致平衡,这样我们就可以得到期望均摊时间复杂度的下界——均摊formula_1。  每次旋转操作由三个因素决定:  在每次旋转操作后,设置"g"的儿子为"x"是很重要的。如果"g"为空,那么"x"显然就是根节点了。  共有三种旋转操作,每种都有左旋(Zig)和右旋(Zag)两种情况。为了简单起见,对每种旋转操作只展示一种情况。这些旋转操作是:  Zig:当"p"为根节点时进行。Zig通常只在伸展操作的最后一步进行。  Zig-zig和Zag-zag:当"p"不为根节点且"x"和"p"都为左儿子或都为右儿子时进行。下图为"x"和"p"都为左儿子时的情况(即Zig-zig),需先将"p"右旋到"g"的位置,再将"x"右旋到"p"的位置。  Zig-zag和Zag-zig:当"p"不为根节点且"x"为左儿子而"p"为右儿子时进行,反之亦然。下图为前述情况(即Zig-zag),需先将"x"左旋到"p"到的位置,再将"x"右旋到"g"的位置。

  给出两棵树S和T,且S的所有元素都比T的元素要小。下面的步骤可以把它们连接成一棵树:

  给出一棵树和一个元素"x",返回两棵树:一棵中所有的元素均小于等于x,另一棵中所有的元素大于"x"。下面的步骤可以完成这个操作:

  插入操作是一个比较复杂的过程,具体步骤如下: 我们假定要插入的值为k。  如果当前树为空,则直接插入根。  如果当前节点的权值等于k则增加当前节点的大小并更新节点和父亲的信息,将当前节点进行splay操作。  否则按照二叉查找树的性质向下找,找到空节点就插入即可,当然在最后还要进行一次splay操作。

  如同一般的查找树的查找方式。

  以下是伸展树的C++实现(用指针实现)

  m次伸展操作的均摊时间效率 formula_4  实际时间效率 formula_5
伸展树(英语:Splay Tree)是一种能够自我平衡的二叉查找树,它能在均摊formula_1的时间内完成基于伸展(Splay)操作的插入、查找、修改和删除操作。它是由丹尼尔·斯立特(英语:Daniel Sleator)和罗伯特·塔扬在1985年发明的。