本文共 8427 字，大约阅读时间需要 28 分钟。

完整代码：代码#include 
   
    #include 
    
     int     size; //结点数量#define        NUM        20typedef struct tree_node{    struct tree_node*    left;    struct tree_node*    right;    int        item;}tree_node;tree_node* splay (int i, tree_node* t) {    tree_node N, *l, *r, *y;    if (t == NULL)         return t;    N.left = N.right = NULL;     l = r = &N;      for (;;)     {         if (i < t->item)          {             if (t->left == NULL)                  break;             if (i < t->left->item)              {                 y = t->left;                           /* rotate right */                 t->left = y->right;                 y->right = t;                 t = y;                 if (t->left == NULL)                      break;             }             r->left = t;                               /* link right */            r = t;             t = t->left;         } else if (i > t->item)         {             if (t->right == NULL)                  break;             if (i > t->right->item)              {                 y = t->right;                          /* rotate left */                 t->right = y->left;                 y->left = t;                 t = y;                 if (t->right == NULL)                      break;             }             l->right = t;                              /* link left */             l = t;             t = t->right;         } else {             break;         }     }     l->right = t->left;                                /* assemble */     r->left = t->right;     t->left = N.right;     t->right = N.left;     return t; }  /* **将i插入树t中,返回树的根结点(item值==i) */ tree_node* ST_insert(int i, tree_node *t) {     /* Insert i into the tree t, unless it's already there.    */     /* Return a pointer to the resulting tree.                 */     tree_node* node;          node = (tree_node *) malloc (sizeof (tree_node));     if (node == NULL){         printf("Ran out of space\n");         exit(1);     }     node->item = i;     if (t == NULL) {         node->left = node->right = NULL;         size = 1;         return node;     }     t = splay(i,t);     if (i < t->item) {  //令t为i的右子树         node->left = t->left;         node->right = t;         t->left = NULL;         size ++;         return node;     } else if (i > t->item) { //令t为i的左子树         node->right = t->right;         node->left = t;         t->right = NULL;         size++;         return node;    } else {          free(node); //i值已经存在于树t中         return t;     } }   /* **从树中删除i,返回树的根结点 */ tree_node* ST_delete(int i, tree_node* t) {     /* Deletes i from the tree if it's there.               */     /* Return a pointer to the resulting tree.              */     tree_node* x;     if (t==NULL)          return NULL;     t = splay(i,t);     if (i == t->item) {               /* found it */         if (t->left == NULL) { //左子树为空,则x指向右子树即可             x = t->right;         } else {             x = splay(i, t->left); //查找左子树中最大结点max,令右子树为max的右子树             x->right = t->right;         }         size--;         free(t);         return x;     }     return t;                         /* It wasn't there */ }  void ST_inoder_traverse(tree_node*    node) {     if(node != NULL)     {         ST_inoder_traverse(node->left);         printf("%d ", node->item);         ST_inoder_traverse(node->right);     } }  void ST_pre_traverse(tree_node*    node) {     if(node != NULL)    {         printf("%d ", node->item);         ST_pre_traverse(node->left);         ST_pre_traverse(node->right);     } }   void main() {     /* A sample use of these functions.  Start with the empty tree,         */     /* insert some stuff into it, and then delete it                        */     tree_node* root;     int i;      root = NULL;              /* the empty tree */     size = 0;      for(i = 0; i < NUM; i++)         root = ST_insert(rand()%NUM, root);      ST_pre_traverse(root);     printf("\n");     ST_inoder_traverse(root);      for(i = 0; i < NUM; i++)         root = ST_delete(i, root);      printf("\nsize = %d\n", size); }
    
   

MiYu原创, 转帖请注明 : 转载自     

 

伸展树(Splay Tree)是AVL树不错的替代，它有以下几个特点：

(1)它是二叉查找树的改进，所以具有二叉查找树的有序性。 (2)对伸展树的操作的平摊复杂度是O(log2n)。 (3)伸展树的空间要求、编程难度非常低。

提到伸展树，就不得不提到AVL树和Read-Black树，虽然这两种树能够保证各种操作在最坏情况下都为logN，但是两都实现都比较复杂。而在实际情况中，90%的访问发生在10%的数据上。因此，我们可以重构树的结构，使得被经常访问的节点朝树根的方向移动。尽管这会引入额外的操作，但是经常被访问的节点被移动到了靠近根的位置，因此，对于这部分节点，我们可以很快的访问。这样，就能使得平摊复杂度为logN。

1、自底向上的伸展树

伸展操作Splay(x,S)是在保持伸展树有序性的前提下，通过一系列旋转操作将伸展树S中的元素x调整至树的根部的操作。 在旋转的过程中，要分三种情况分别处理： (1)Zig 或 Zag (2)Zig-Zig 或 Zag-Zag (3)Zig-Zag 或 Zag-Zig 1.1、Zig或Zag操作 节点x的父节点y是根节点。

1.2、Zig-Zig或Zag-Zag操作

节点x的父节点y不是根节点，且x与y同时是各自父节点的左孩子或者同时是各自父节点的右孩子。

1.3、Zig-Zag或Zag-Zig操作

节点x的父节点y不是根节点，x与y中一个是其父节点的左孩子而另一个是其父节点的右孩子。

2、自顶向下的伸展树

    在自底向上的伸展树中，我们需要求一个节点的父节点和祖父节点，因此这种伸展树难以实现。因此，我们可以构建自顶向下的伸展树。     当我们沿着树向下搜索某个节点X的时候，我们将搜索路径上的节点及其子树移走。我们构建两棵临时的树──左树和右树。没有被移走的节点构成的树称作中树。在伸展操作的过程中： (1)当前节点X是中树的根。 (2)左树L保存小于X的节点。 (3)右树R保存大于X的节点。 开始时候，X是树T的根，左右树L和R都是空的。和前面的自下而上相同，自上而下也分三种情况： 2.1、Zig操作

如上图，在搜索到X的时候，所查找的节点比X小，将Y旋转到中树的树根。旋转之后，X及其右子树被移动到右树上。很显然，右树上的节点都大于所要查找的节点。注意X被放置在右树的最小的位置，也就是X及其子树比原先的右树中所有的节点都要小。这是由于越是在路径前面被移动到右树的节点，其值越大。

2.2、Zig-Zig操作

这种情况下，所查找的节点在Z的子树中，也就是，所查找的节点比X和Y都小。所以要将X，Y及其右子树都移动到右树中。首先是Y绕X右旋，然后Z绕Y右旋，最后将Z的右子树（此时Z的右子节点为Y）移动到右树中。

2.3、Zig-Zag操作

这种情况中，首先将Y右旋到根。这和Zig的情况是一样的，然后变成上图右边所示的形状。此时，就与Zag(与Zig相反)的情况一样了。

最后，在查找到节点后，将三棵树合并。如图：

2.4、示例： 下面是一个查找节点19的例子。在例子中，树中并没有节点19,最后，距离节点最近的节点18被旋转到了根作为新的根。节点20也是距离节点19最近的节点，但是节点20没有成为新根，这和节点20在原来树中的位置有关系。

3、实现

3.1、splay操作

tree_node * splay (int i, tree_node * t) {    tree_node N, *l, *r, *y;    if (t == NULL)         return t;    N.left = N.right = NULL;    l = r = &N;    for (;;)    {        if (i < t->item)         {            if (t->left == NULL)                 break;            if (i < t->left->item)             {                y = t->left;                           /* rotate right */                t->left = y->right;                y->right = t;                t = y;                if (t->left == NULL)                     break;            }            r->left = t;                               /* link right */            r = t;            t = t->left;        } else if (i > t->item)        {            if (t->right == NULL)                 break;            if (i > t->right->item)             {                y = t->right;                          /* rotate left */                t->right = y->left;                y->left = t;                t = y;                if (t->right == NULL)                     break;            }            l->right = t;                              /* link left */            l = t;            t = t->right;        } else {            break;        }    }    l->right = t->left;                                /* assemble */    r->left = t->right;    t->left = N.right;    t->right = N.left;    return t;}

Rotate right(查找10)：

Link right：

Assemble：

Rotate left(查找20)：

Link left：

3.2、插入操作

/*  **将i插入树t中,返回树的根结点(item值==i)  */  tree_node* ST_insert(int i, tree_node *t) {      /* Insert i into the tree t, unless it's already there.    */      /* Return a pointer to the resulting tree.                 */      tree_node* node;            node = (tree_node *) malloc (sizeof (tree_node));     if (node == NULL){         printf("Ran out of space\n");         exit(1);     }     node->item = i;     if (t == NULL) {         node->left = node->right = NULL;         size = 1;         return node;     }     t = splay(i,t);     if (i < t->item) {  //令t为i的右子树         node->left = t->left;         node->right = t;         t->left = NULL;         size ++;         return node;     } else if (i > t->item) { //令t为i的左子树         node->right = t->right;         node->left = t;         t->right = NULL;         size++;         return node;     } else {          free(node); //i值已经存在于树t中         return t;     } }

3.3、删除操作/* **从树中删除i,返回树的根结点 */ tree_node* ST_delete(int i, tree_node* t) {     /* Deletes i from the tree if it's there.               */     /* Return a pointer to the resulting tree.              */     tree_node* x;     if (t==NULL)          return NULL;     t = splay(i,t);     if (i == t->item) {               /* found it */         if (t->left == NULL) { //左子树为空,则x指向右子树即可           x = t->right;         } else {             x = splay(i, t->left); //查找左子树中最大结点max,令右子树为max的右子树             x->right = t->right;         }         size--;         free(t);         return x;     }     return t;                         /* It wasn't there */ }