伸展树,解释起来真的很晕。先看一下我写的关于伸展树的理论部分吧:伸展树,据说比AVL树要简单一些。简单个球啊,写完了我还是晕晕的,所以又看了很久。
但是,总有那么一瞬,总有那么一句话,会让你茅塞顿开。 所以,我再简单讲一遍自顶向下伸展树原理,自底向上是真的,好理解,但是实现成本太高。
为了叙述的方便,上图的右旋叫做X绕Y右旋,左旋叫做Y绕X左旋。
当我们沿着树向下搜索某个节点X的时候,我们将搜索路径上的节点及其子树移走。我们构建两棵临时的树──左树和右树。没有被移走的节点构成的树称作中树。在伸展操作的过程中: 1、当前节点X是中树的根。 2、左树L保存小于X的节点。 3、右树R保存大于X的节点。 开始时候,X是树T的根,左右树L和R都是空的。
和自底向上一样,自顶向下也分了三种情况。
如上图,在搜索到X的时候,所查找的节点比X小,将Y旋转到中树的树根。旋转之后,X及其右子树被移动到右树上。很显然,右树上的节点都大于所要查找的节点。注意X被放置在右树的最小的位置,也就是X及其子树比原先的右树中所有的节点都要小。这是由于越是在路径前面被移动到右树的节点,其值越大。读者可以分析一下树的结构,原因很简单。(就这句,给我点醒了)
通了一点之后,后面就好办了。
在这种情况下,所查找的节点在Z的子树中,也就是,所查找的节点比X和Y都小。所以要将X,Y及其右子树都移动到右树中。首先是Y绕X右旋,然后Z绕Y右旋,最后将Z的右子树(此时Z的右子节点为Y)移动到右树中。注意右树中挂载点的位置。
在这种情况中,首先将Y右旋到根。这和Zig的情况是一样的。然后变成上图右边所示的形状。接着,对Z进行左旋,将Y及其左子树移动到左树上。这样,这种情况就被分成了两个Zig情况。这样,在编程的时候就会简化,但是操作的数目增加(相当于两次Zig情况)。
将中树的左右子树分别连接到左树的右子树和右树的左子树上。将左右树作为X的左右子树。重新最成了一所查找的节点为根的树。
下面是一个查找节点19的例子: 在例子中,树中并没有节点19,最后,距离节点最近的节点18被旋转到了根作为新的根。节点20也是距离节点19最近的节点,但是节点20没有成为新根,这和节点20在原来树中的位置有关系。
而一直困扰我的,就是第二步到第三步的转化,为什么要把20提上去,现在明白了。
#include <stdlib.h>
#include <stdio.h>
int size; /* number of nodes in the tree */
/* Not actually needed for any of the operations */
typedef struct tree_node Tree;
struct tree_node
{
Tree * left, * right;
int item;
};
Tree * splay (int i, Tree * t)
{
/* Simple top down splay, not requiring i to be in the tree t. */
/* What it does is described above. */
Tree 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;
}
/* Here is how sedgewick would have written this. */
/* It does the same thing. */
Tree * sedgewickized_splay (int i, Tree * t)
{
Tree 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 && i < t->left->item)
{
y = t->left;
t->left = y->right;
y->right = t;
t = y;
}
if (t->left == NULL)
break;
r->left = t;
r = t;
t = t->left;
}
else if (i > t->item)
{
if (t->right != NULL && i > t->right->item)
{
y = t->right;
t->right = y->left;
y->left = t;
t = y;
}
if (t->right == NULL)
break;
l->right = t;
l = t;
t = t->right;
}
else
break;
}
}
l->right=t->left;
r->left=t->right;
t->left=N.right;
t->right=N.left;
return t;
}
Tree * insert(int i, Tree * t)
{
/* Insert i into the tree t, unless it's already there. */
/* Return a pointer to the resulting tree. */
Tree * new_node;
new_node = (Tree *) malloc (sizeof (Tree));
if (new_node == NULL)
{
printf("Ran out of space\n");
exit(1);
}
new_node ->item = i;
if (t == NULL)
{
new_node->left = new_node->right = NULL;
size = 1;
return new_node;
}
t = splay(i,t);
if (i < t->item)
{
new_node->left = t->left;
new_node->right = t;
t->left = NULL;
size ++;
return new_node;
}
else if (i > t->item)
{
new_node->right = t->right;
new_node->left = t;
t->right = NULL;
size++;
return new_node;
}
else
{
/* We get here if it's already in the tree */
/* Don't add it again */
free(new_node);
return t;
}
}
Tree * delete(int i, Tree * t)
{
/* Deletes i from the tree if it's there. */
/* Return a pointer to the resulting tree. */
Tree * x;
if (t==NULL)
return NULL;
t = splay(i,t);
if (i == t->item)
{ /* found it */
if (t->left == NULL)
x = t->right;
else
{
x = splay(i, t->left);
x->right = t->right;
}
size--;
free(t);
return x;
}
return t; /* It wasn't there */
}
int main(int argv, char *argc[])
{
/* A sample use of these functions. Start with the empty tree, */
/* insert some stuff into it, and then delete it */
Tree * root;
int i;
root = NULL; /* the empty tree */
size = 0;
for (i = 0; i < 1024; i++)
{
root = insert((541*i) & (1023), root);
}
printf("size = %d\n", size);
for (i = 0; i < 1024; i++)
{
root = delete((541*i) & (1023), root);
}
printf("size = %d\n", size);
}