Splay Tree

Splay Tree是一个小作品，欢迎帮助扩充这个条目。

参考WC2004，杨思雨论文

介绍

本节描述一种相对简单的数据结构，叫做伸展树（splay tree），它保证从空树开始任意连续M次对树的操作最多花费O(MlogN)时间。虽然这种保证并不排除任意单次操作花费O(N)时间的可能，而且这样的界也不如每次操作最坏情形的界为O(logN)时那么强，但是实际效果是一样的：不存在不好的输入序列。

Splay Tree 是二叉查找树的一种，它与平衡二叉树、红黑树不同的是，Splay Tree从不强制地保持自身的平衡，每当查找到某个节点n的时候，在返回节点n的同时，Splay Tree会将节点n旋转到树根的位置，这样就使得Splay Tree天生有着一种类似缓存的能力，因为每次被查找到的节点都会被搬到树根的位置，所以当80%的情况下我们需要查找的元素都是某个固定的节点，或者是一部分特定的节点时，那么在很多时候，查找的效率会是O(1)的效率！当然如果查找的节点是很均匀地分布在不同的地方时，Splay Tree的性能就会变得很差了，但Splay Tree的均摊时间复杂度还是O（logn）的。

这里先介绍一下左旋（zag）和右旋（zig）的操作 文件:Http://hi.csdn.net/attachment/201107/21/0 13112275721N3Z.gif

然后就是Splay Tree进行Splay操作的具体步骤，主要分两种情况：

文件:Http://hi.csdn.net/attachment/201107/21/0 1311227785J1FJ.gif 先看图中的左边，查找到的x节点的父节点是y，x是y的左子树，y的父节点z是根节点，y也是z的左子树，要把x旋转到根节点的位置，就要进行zig(y)，然后再进行zig(x)操作

再看图中的右边，查找到的z节点的父节点是y，z是y的右子树，y的父节点x是根节点，y也是x的右子树，要把z旋转到根节点的位置，就要进行zag(y)，然后进行zag(x)操作

若是途中的情况，若需要把x移动到根节点，则需要先进行zig(x)，然后再进行zag(x)操作

还有一种y是z的左子树，x是y的右子树的情况，这时就需要先进行zag(x)，然后再进行zig(x)操作了

操作

伸展Splay

   /**
    * Internal method to perform a top-down splay.
    * The last accessed node becomes the new root.
    * This method may be overridden to use a different
    * splaying algorithm, however, the splay tree code
    * depends on the accessed item going to the root.
    * x is the target item to splay around.
    * t is the root of the subtree to splay.
    */
   void splay( const Comparable & x, BinaryNode * & t )
   {
       BinaryNode *leftTreeMax, *rightTreeMin;
       static BinaryNode header;
       header.left = header.right = nullNode;
       leftTreeMax = rightTreeMin = &header;
       nullNode->element = x;   // Guarantee a match
       for( ; ; )
           if( x < t->element )
           {
               if( t->left == nullNode )
                   break;
               if( x < t->left->element )
                   rotateWithLeftChild( t );
               // Link Right
               rightTreeMin->left = t;
               rightTreeMin = t;
               t = t->left;
           }
           else if( t->element < x )
           {
               if( t->right == nullNode )
                   break;
               if( t->right->element < x )
                   rotateWithRightChild( t );
               // 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;
   }

插入Insert

   void insert( const Comparable & x )
   {
       static BinaryNode *newNode = NULL;
       if( newNode == NULL )
           newNode = new BinaryNode;
       newNode->element = x;
       if( root == nullNode )
       {
           newNode->left = newNode->right = nullNode;
           root = newNode;
       }
       else
       {
           splay( x, root );
           if( x < root->element )
           {
               newNode->left = root->left;
               newNode->right = root;
               root->left = nullNode;
               root = newNode;
           }
           else
           if( root->element < x )
           {
               newNode->right = root->right;
               newNode->left = root;
               root->right = nullNode;
               root = newNode;
           }
           else
               return;
       }
       newNode = NULL;   // So next insert will call new
   }

删除Delete

   void remove( const Comparable & x )
   {
       BinaryNode *newTree;
           // If x is found, it will be at the root
       if( !contains( x ) )
           return;   // Item not found; do nothing
       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;
           splay( x, newTree );
           newTree->right = root->right;
       }
       delete root;
       root = newTree;
   }

参考程序

• code in C
• code in Pascal
• code in C++