伸展树（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的实现省略。

以下是类定义

 #ifndef _splaytree_h_

 #define _splaytree_h_

 template<typename Comparable>

 class SplayTree

 {

 public:

     SplayTree()

     {

         nullNode = new BinaryNode;

         nullNode->left = nullNode->right = nullNode;

         root = nullNode;

     }

     ~SplayTree()

     {

         makeEmpty();

         delete nullNode;

     }

     SplayTree(const Splay& rhs);

     const SplayTree& operator=(const SplayTree&rhs);

 　　 // 此处省略操作方法

 private:

     struct BinaryNode

     {

         Comparable element;

         BinaryNode *left;

         BinaryNode *right;

         BinaryNode(const Comparable& theElement, BinaryNode *lt, BinaryNode* rt) :element(theElement), left(lt), right(rt){}

     };

     BinaryNode *root;

     BinaryNode *nullNode;

 // Internal method to perform a top-down splay.

     void insert(const Comparable& x, BinaryNode*&t)const;

     void remove(const Comparable& x, BinaryNode*&t)const;

     BinaryNode* findMin(BinaryNode* t)const;

     BinaryNode* findMax(BinaryNode* t)const;

     bool contains(const Comparable&x, BinaryNode*t)const;

     void makeEmpty(BinaryNode*&t);

     void printTree(BinaryNode*t)const;

     BinaryNode* clone(BinaryNode*t)const;

     void rotationWithLeftChild(BinaryNode*&k2);

     void rotationWithRightChild(BinaryNode*& k1);

     void splay(const Comparable& x, BinaryNode *&t);

 };

 #endif

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



 template<typename Comparable>

 void SplayTree<Comparable>::splay(const Comparable& x, BinaryNode*& t)

 {

     BinaryNode *leftTreeMax, *rightTreeMin;

     static BinaryNode header;

     header.left = header.right = nullNode;         //nullNode逻辑上表示一个NULL指针

     leftTreeMax = rightTreeMin = &header;  

     nullNode->element = x;   //guarantee a match.

     for (;;)

         if (x < t->element)

         {

             if ((x < t->left->element))

                 rotationWithLeftChild(t);

             if (t->left == nullNode)

                 break;
　　　　　　　　　　　　// Link Right

             rightTreeMin->left = t;

             rightTreeMin = t;

             t = t->left;

         }

         else if (t->element < x)

         {

             if (t->right->element < x)

                 rotationWithRightChild(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;

 }

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

 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->right;

             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.

 }

remove和makeEmpty的实现：

 void remove(const Comparable& x)

 {

     BinaryNode *newNode;

     splay(x, root);

     if (root->element != x)

         return;

     if (root->left == nullNode)

         newTree = root->right;

     else

     {

         newTree = root->left;

         splay(x, newTree);   // 在左子树中寻找最大的项，把它伸展到根部

         newTree->right = root->right; //连接右子树

     }

     delete root;

     root = newTree;

 }

 void makeEmpty()

 {

     whiel(!isEmpty())

     {

         findMax();

         remove(root->element);

     }

 }

巴特西

伸展树（SplayTree）的实现

最新文章

热门文章