伸展树（SplayTree）的实现

优点：伸展树(splay tree)是一种能自我调整的二叉搜索树(BST)。虽然某一次的访问操作所花费的时间比较长，但是平摊（amortized）之后的访问操作（例如旋转）时间能达到O(logn)的复杂度。对于某一个被访问的节点，在接下来的一段时间内再次频繁访问它（90%的情况下是这样的，即符合90-10规则，类似于CPU内或磁盘的cache设计原理）的应用模式来说，伸展树是一种很理想的数据结构。另外一点与其他平衡二叉树的区别是，伸展树不需要存储任何像AVL树中平衡因子(balance factor)那样的平衡信息，可以节省空间的开销。

缺点：不像其他平衡二叉树那样即使最坏情况下也能达到O(logn)访问时间，它的最坏情况下只有O(n)，跟单向链表一样。另外，伸展树的查找操作会修改树的结构，这与普通意义上的查找为只读操作习惯不太一样。

实现方式：伸展树的实现有两种方式，一是自底向上(bottom-up)，另外一种是自顶向下(top-down)。

考虑到实现的难易程度，自顶向下的实现方式比较简单，因为自底向上需要保存已经被访问的节点，而自顶向下可以在搜索的过程中同时完成splay操作。

虽然两者得出的树结构不太一样，但是它们的平摊时间复杂度都是O(logn)。两种实现的基本操作就是splay，splay将最后被访问到的节点提升为根节点。

在自顶向下(top-down)的实现中，需要将输入的树拆成三颗树，分别为左树L，中树M和右树R。其中M树维护当前还未被访问到的节点，L树中所有节点的值都小于M树中的任何节点值，R树中所有节点的值都大于M树中的任何节点值。L树中只需要知道当前的最大节点 (leftTreeMax)，而R树中只需要知道当前的最小节点(rightTreeMin)。左右两棵树的根节点分别可以通过nullNode节点（它是leftTreeMax和rightTreeMin的初始值，而且splay过程中变量nullNode本身未变化,只改变它的左右孩子节点）的右和左孩子节点得到，因为leftTreeMax中加入一个新的节点或子树时都是将新的节点作为leftTreeMax的右孩子，而不是左孩子（注意这里的顺序），rightTreeMin跟leftTreeMax相反。自顶向下的zig-zig或zag-zag需要做旋转操作，zig-zig的旋转操作叫rotationWithLeftChild,旋转后目标节点的父节点和祖父节点加入R树，zag-zag的旋转操作叫rotationWithRightChild,旋转后目标节点的父节点和祖父节点加入L树。另外zig-zag或zag-zig可以分别简化为zig或zag操作，这样可以将zig-zag和zig合二为一，从而只需考虑一种情况，而不需要将两种情况单独考虑。zig操作将目标节点的父节点加入R树，zag操作将目标节点的父节点加入L树。注意L和R树中每次加入新节点都需更新变量leftTreeMax或rightTreeMin。自顶向下splay操作的最后一步是重组(re-assemble)：将M树的左孩子设置为L树的根节点，将M树的右孩子设置为R树的根节点，然后M树原来的左孩子成为leftTreeMax的右孩子，M树原来的右孩子成为rightTreeMin的左孩子。

注：rotationWithRightChild和rotationWithLeftChild的实现省略。

以下是类定义

 1 #ifndef _splaytree_h_
 2 #define _splaytree_h_
 3 
 4 template<typename Comparable>
 5 class SplayTree
 6 {
 7 public:
 8     SplayTree()
 9     {
10         nullNode = new BinaryNode;
11         nullNode->left = nullNode->right = nullNode;
12         root = nullNode;
13     }
14 
15     ~SplayTree()
16     {
17         makeEmpty();
18         delete nullNode;
19     }
20 
21     SplayTree(const Splay& rhs);
22     const SplayTree& operator=(const SplayTree&rhs);
23 　　 // 此处省略操作方法
24 
25 private:
26     struct BinaryNode
27     {
28         Comparable element;
29         BinaryNode *left;
30         BinaryNode *right;
31 
32         BinaryNode(const Comparable& theElement, BinaryNode *lt, BinaryNode* rt) :element(theElement), left(lt), right(rt){}
33     };
34 
35     BinaryNode *root;
36     BinaryNode *nullNode;
37 // Internal method to perform a top-down splay.
38     void insert(const Comparable& x, BinaryNode*&t)const;
39     void remove(const Comparable& x, BinaryNode*&t)const;
40     BinaryNode* findMin(BinaryNode* t)const;
41     BinaryNode* findMax(BinaryNode* t)const;
42     bool contains(const Comparable&x, BinaryNode*t)const;
43     void makeEmpty(BinaryNode*&t);
44     void printTree(BinaryNode*t)const;
45     BinaryNode* clone(BinaryNode*t)const;
46 
47     void rotationWithLeftChild(BinaryNode*&k2);
48     void rotationWithRightChild(BinaryNode*& k1);
49     void splay(const Comparable& x, BinaryNode *&t);
50 };
51 
52 #endif

接着splay的实现： 1 #include"splaytree.h"

 2 
 3 template<typename Comparable>
 4 void SplayTree<Comparable>::splay(const Comparable& x, BinaryNode*& t)
 5 {
 6     BinaryNode *leftTreeMax, *rightTreeMin;
 7     static BinaryNode header;
 8 
 9     header.left = header.right = nullNode;         //nullNode逻辑上表示一个NULL指针
10     leftTreeMax = rightTreeMin = &header;  
11 
12     nullNode->element = x;   //guarantee a match.
13 
14     for (;;)                    
15         if (x < t->element)
16         {
17             if ((x < t->left->element))
18                 rotationWithLeftChild(t); 
19             if (t->left == nullNode)
20                 break;
　　　　　　　　　　　　// Link Right
21             rightTreeMin->left = t;
22             rightTreeMin = t;
23             t = t->left;
24         }
25         else if (t->element < x)
26         {
27             if (t->right->element < x)
28                 rotationWithRightChild(t);
29             if (t->right == nullNode)
30                 break;
　　　　　　　　　　　　// Link Left
31             leftTreeMax->right = t;
32             leftTreeMax = t;
33             t = t->right;
34         }
35         else
36             break;
37 
38         leftTreeMax->right = t->left;
39         rightTreeMin->left = t->right;
40         t->left = header.right;
41         t->right = header.left;
42 }

header.left和header.right分别引用R和L的根。（这不是输入错误，而是遵守链的指向）

 1 void insert(const Comparable& x)
 2 {
 3     static BinaryNode* newNode = NULL; 
 4     if (newNode == NULL)
 5         newNode = new BinaryNode;
 6     newNode->element = x;
 7 
 8     if (root == nullNode)
 9     {
10         newNode->left = newNode->right = nullNode;
11         root = newNode;
12     }
13     else
14     {
15         splay(x, root);
16         if (x < root->element)
17         {
18             newNode->left = root->right;
19             newNode->right = root;
20             root->left = nullNode;
21             root = newNode;
22         }
23         else if (root->element < x)
24         {
25             newNode->right = root->right;
26             newNode.left = root;
27             root->right = nullNode;
28             root = newNode;
29         }
30         else
31             return;
32     }
33     newNode = NULL; // So next insert will call new.
34 }

remove和makeEmpty的实现：

 1 void remove(const Comparable& x)
 2 {
 3     BinaryNode *newNode;
 4     splay(x, root);
 5     if (root->element != x)
 6         return;
 7     if (root->left == nullNode)
 8         newTree = root->right;
 9     else
10     {
11         newTree = root->left;
12         splay(x, newTree);   // 在左子树中寻找最大的项，把它伸展到根部
13         newTree->right = root->right; //连接右子树
14     }
15     delete root;
16     root = newTree;
17 }
18 
19 void makeEmpty()
20 {
21     whiel(!isEmpty())
22     {
23         findMax();
24         remove(root->element);
25     }
26 }