伸展树性质

伸展树（splay tree），它保证从空树开始连续M次对树的操作最多花费O(MlogN)时间。虽然这种保证并不排除任意单次操作花费O(N)时间的可能，但是保证了不存在坏的操作序列。

伸展树基于这样的事实：对于二叉查找树来说，每次操作最坏情形时间O(N)并不坏，只要它相对不常发生就行。二叉查找树的问题在于，一系列连续操作都是最坏情形仍然是有可能发生的，尽管很罕见。而伸展树就是为了解决二叉查找树的这个问题。

解决思路：如果任意特定操作可以有最坏时间界O(N)，而我们仍然要求一个O(logN)的摊还时间界，那么很清楚，只要一个节点被访问，它必须被移动。否则，一旦发现一个深层的节点，我们就有可能不断对它进行访问。如果这个节点不改变位置，而每次访问又花费O(N)，那么M次访问将花费O(M·N)的时间。

解决方法：伸展树的基本想法是，当一个节点被访问后，它就要经过一系列旋转操作被推到根上。注意，如果一个节点很深，那么在其路径上就存在许多相对较深的节点，通过上述操作重新构造后，可以减少对所有这些节点的进一步访问所花费的时间。这种方法不仅在理论上被证明具有好的摊还时间界，而且具有实际效用，因为研究表明在许多应用中，当一个节点被访问时，它很可能不久再被访问。另外，相比AVL树，伸展树不要求保留高度或平衡信息，这在某种程度上节省空间并简化代码。

摊还代价

一般来说，当M次操作的序列的总的最坏情形运行时间为，我们就说它的摊还（amortized）运行时间为。因此，我们可以说一颗伸展树每次操作的摊还代价是。摊还时间界比平均时间界要强，因为二叉查找树每次操作的平均时间为，但是对于连续M次操作仍可能花费时间。摊还时间界的计算和证明一般需要借助位势函数来实现。

伸展树的展开

splay(x, t)操作是通过一系列的旋转操作将t中的元素x推到树根的过程。
令X是访问路径上的一个非根节点。如果X的父节点是树根，那么只需要旋转X和树根即完成展开操作；如果X的父节点不是树根，那么X就会右父亲（P）和祖父（G），此时会有两种情况下的旋转操作。
之字形展开（zig-zag）
之字形情形如下图所示，X是右儿子，P是左儿子；或者X是左儿子，P是右儿子。这种情形下，我们执行一次像AVL双旋转操作即可。

依照上述的分析，展开操作的直接实现，需要从根沿树往下完成一次遍历，找到元素X（如果X元素不存在，那么展开就对访问路径上最后的节点实施），然后再从底向上遍历一次来实现展开操作。这样需要大量的系统开销，并且还需要处理许多特殊的情形。然而，可以直接在从根沿树寻找元素的同时实施旋转，结果得到在实践中更快地展开过程，这种操作称为自顶向下伸展树。

自顶向下伸展树

顾名思义，自顶向下伸展树的展开操作splay(x, root)是从上往下进行的，即从根元素开始寻找x元素的同时，实施旋转操作。下图中列举出三种可能情况下的旋转（忽略三种对称的旋转）：单旋转、一字形和之字形的旋转。

合并
一旦执行完最后一步展开，需要将L，R，中间树T合并成一棵树。做法如下图所示：

下面给出一个实际的自顶向下展开的实例：

实现

SplayTree的类架构
包括一个构造方法，用来分配nullNode标记，我们使用nullNode逻辑上表示一个null引用，并反复使用这种技术来简化程序。节点使用普通的二叉树节点。

public class SplayTree<AnyType extends Comparable<? super AnyType>>
{

    public SplayTree()
    {
        nullNode = new BinaryNode<AnyType>( null );
        nullNode.left = nullNode.right = nullNode;
        root = nullNode;
    }
    
    private BinaryNode<AnyType> root;
    private BinaryNode<AnyType> nullNode;
    private BinaryNode<AnyType> header = new BinaryNode<AnyType>( null ); // For splay
    private BinaryNode<AnyType> newNode = null;  // Used between different inserts
    
    /**
     * Insert into the tree.
     * @param x the item to insert.
     */
    public void insert( AnyType x )
    {}

    /**
     * Remove from the tree.
     * @param x the item to remove.
     */
    public void remove( AnyType x )
    {}

    public AnyType findMin()
    {}

    public AnyType findMax( )
    {}

    public boolean contains( AnyType x )
    {}

    public void makeEmpty( )
    {
        root = nullNode;
    }

    public boolean isEmpty( )
    {
        return root == nullNode;
    }
    
    /**
     * Internal method to perform a top-down splay.
     * The last accessed node becomes the new root.
     * @param x the target item to splay around.
     * @param t the root of the subtree to splay.
     * @return the subtree after the splay.
     */
    private BinaryNode<AnyType> splay( AnyType x, BinaryNode<AnyType> t )
    {}

    /**
     * Rotate binary tree node with left child.
     * For AVL trees, this is a single rotation for case 1.
     */
    private static <AnyType> BinaryNode<AnyType> rotateWithLeftChild( BinaryNode<AnyType> k2 )
    {}

    /**
     * Rotate binary tree node with right child.
     * For AVL trees, this is a single rotation for case 4.
     */
    private static <AnyType> BinaryNode<AnyType> rotateWithRightChild( BinaryNode<AnyType> k1 )
    {}

    // Basic node stored in unbalanced binary search trees
    private static class BinaryNode<AnyType>
    {
        BinaryNode( AnyType theElement )
        {
            this( theElement, null, null );
        }

        BinaryNode( AnyType theElement, BinaryNode<AnyType> lt, BinaryNode<AnyType> rt )
        {
            element  = theElement;
            left     = lt;
            right    = rt;
        }

        AnyType element;            // The data in the node
        BinaryNode<AnyType> left;   // Left child
        BinaryNode<AnyType> right;  // Right child
    }

自顶向下的展开（splay）
我们使用带有左链和右链的一个头header最终引用左树的根和右树的根。由于这两棵树初始为空，因此使用一个头分别对应初始状态右树的最小节点或左树的最大节点。这种做法可以使得程序避免空树检查。
第一次左树变成非空时，右链将被初始化并在以后保持不变；这样，在自顶向下查找的最后右链（header.right）将包含左树的根。类似地，左链（header.left）最终将包含右树的根。
注意：在上面介绍的单旋转（包括简化的之字形旋转）中，在编程时，无需任何rotate操作，只需要改变一些节点的链即可实现对应效果；对于一字形展开，只需要通过一次单旋转，然后改变一些节点的链即可实现对应效果。

/**
     * Internal method to perform a top-down splay.
     * The last accessed node becomes the new root.
     * @param x the target item to splay around.
     * @param t the root of the subtree to splay.
     * @return the subtree after the splay.
     */
    private BinaryNode<AnyType> splay( AnyType x, BinaryNode<AnyType> t )
    {
        BinaryNode<AnyType> leftTreeMax, rightTreeMin;

        header.left = header.right = nullNode;
        leftTreeMax = rightTreeMin = header;

        nullNode.element = x;   // Guarantee a match

        for( ; ; )
        {
            int compareResult = x.compareTo( t.element );
            
            if( compareResult < 0 )
            {
                if( x.compareTo( t.left.element ) < 0 )
                    t = rotateWithLeftChild( t );
                if( t.left == nullNode )
                    break;
                // Link Right
                rightTreeMin.left = t;
                rightTreeMin = t;
                t = t.left;
            }
            else if( compareResult > 0 )
            {
                if( x.compareTo( t.right.element ) > 0 )
                    t = rotateWithRightChild( t );
                if( t.right == nullNode )
                    break;
                // Link Left
                leftTreeMax.right = t;
                leftTreeMax = t;
                t = t.right;
            }
            else
                break;
        }   

        leftTreeMax.right = t.left;
        rightTreeMin.left = t.right;
        t.left = header.right;
        t.right = header.left;
        return t;
    }

    /**
     * Rotate binary tree node with left child.
     * For AVL trees, this is a single rotation for case 1.
     */
   private static <AnyType> BinaryNode<AnyType> rotateWithLeftChild( BinaryNode<AnyType> k2 )
    {
        BinaryNode<AnyType> k1 = k2.left;
        k2.left = k1.right;
        k1.right = k2;
        return k1;
    }

    /**
     * Rotate binary tree node with right child.
     * For AVL trees, this is a single rotation for case 4.
     */
    private static <AnyType> BinaryNode<AnyType> rotateWithRightChild( BinaryNode<AnyType> k1 )
    {
        BinaryNode<AnyType> k2 = k1.right;
        k1.right = k2.left;
        k2.left = k1;
        return k2;
    }

自顶向下的insert
将x插入到树中的步骤如下。

1. 一个新的节点（newNode）被分配，其值为x。
2. 如果树是空的，那么就建立一颗单节点树，newNode即为root，插入完成。

3. 如果树是非空的，我们围绕被插入的值x展开root。
   I. 如果展开后新根的数据等于x（即树中已经包含元素为x的节点），那么直接返回，插入完成；
   II. 如果新根的数据大于x，那么新根及其右子树就变成newNode的一颗右子树，而新根的左子树则成为newNode的左子树，newNode成为新的根。
   III. 如果新根的数据小于x，那么新根及其左子树就变成newNode的一颗左子树，而新根的右子树则成为newNode的右子树，newNode成为新的根。
   以图12-4为例，若将19插入原始的树中，那么第一步正是图12-4中所示的展开过程。因为19大于新根18，所以新根18及其左子树成为19的左子树，新根18的右子树则成为19的右子树，并且19成为新的根。

   
   
   
   

   代码如下：

 /**
     * Insert into the tree.
     * @param x the item to insert.
     */
    public void insert( AnyType x )
    {
        if( newNode == null )
            newNode = new BinaryNode<AnyType>( null );
        newNode.element = x;

        if( root == nullNode )
        {
            newNode.left = newNode.right = nullNode;
            root = newNode;
        }
        else
        {
            root = splay( x, root );
            
            int compareResult = x.compareTo( root.element );
            
            if( compareResult < 0 )
            {
                newNode.left = root.left;
                newNode.right = root;
                root.left = nullNode;
                root = newNode;
            }
            else
            if( compareResult > 0 )
            {
                newNode.right = root.right;
                newNode.left = root;
                root.right = nullNode;
                root = newNode;
            }
            else
                return;   // No duplicates
        }
        newNode = null;   // So next insert will call new
    }

自顶向下的删除
伸展树的删除是容易的，因为一次展开将删除目标放在根处。代码如下：

 /**
     * Remove from the tree.
     * @param x the item to remove.
     */
    public void remove( AnyType x )
    {
        if( !contains( x ) )
            return;

        BinaryNode<AnyType> newTree;

            // If x is found, it will be splayed to the root by contains
        if( root.left == nullNode )
            newTree = root.right;
        else
        {
            // Find the maximum in the left subtree
            // Splay it to the root; and then attach right child
            newTree = root.left;
            newTree = splay( x, newTree );
            newTree.right = root.right;
        }
        root = newTree;
    }