伸展树splaytree的C实现-top dowm

伸展树splaytree的C实现-top dowm (2011-07-14 23:38)转载

标签:  伸展树  splaytree  算法  数据结构  分类： algorthm

    上一篇博文，自底而上，因为前面讲过了bst_bubble,所以重在讲原理部分，没有什么成型的代码。读者完全可以根据二叉搜索树的根插入中的代码实现自底而上splay。

    这篇博文希望多些代码，少些啰嗦。搜索lookup，插入insert，删除remove都是以do_splay为核心实现的。所以，代码的核心是do_splay。本文用的是top down。如果将do_splay改为另外一种形式，插入删除完全不用修改。

    伸展树，我维护了parent字段，为的就是方便求前驱和后继，求前驱和后继的方法和标准的二茬搜索树一摸一样，我就不浪费笔墨了。

    下面这份代码为了方便好懂，牺牲了一点点性能上的东西，比如subleft 和subright两个节点，其实完全可以用一个节点。反正一个不断往左走，另一个不断往右走。不会冲突。为了代码的通俗易懂，这样小小的优化，被我放弃了。

    代码面前，没有秘密，来吧，Come on！

—————————————splaytree.h————————————————————

#ifndef __SPLAYTREE_H

#define __SPLAYTREE_H

typedef int   key_type ;

typedef struct _splaytree_node{

struct _splaytree_node *left;

struct _splaytree_node *right;

struct _splaytree_node *parent;

key_type key;

int data;

}splaytree_node;

typedef struct _splaytree{

  splaytree_node *root;

}splaytree;

#endif

——————————————————————————————————————————

——————————————splaytree.c——————————————————————

#include"splaytree.h"

#include

#include

#include

splaytree_node* splaytree_allocnode(key_type key,int data)

{

splaytree_node *node = NULL;

node = (splaytree_node*)malloc(sizeof(splaytree_node));

if(node == NULL)

return NULL;

else

{

node->key = key;

node->data = data;

node->left = node->right = node->parent = NULL;

return node;

}

}

splaytree_node* splaytree_freenode(splaytree_node* node)

{

if(node)

{

            free(node);

    node = NULL;

}

}

static void rotate_right(splaytree_node* root)

{

assert(root && root->parent == NULL && root->left != NULL);

splaytree_node* left = NULL;

left = root->left;

root->left = left->right;

if(left->right)

left->right->parent = root;

root->parent = left;

left->parent = NULL;

left->right = root;

}

static void rotate_left(splaytree_node* root)

{

assert(root && root->parent == NULL && root->right != NULL);

splaytree_node *right = NULL;

right = root->right;

root->right = right->left;

if(right->left)

right->left->parent = root;

root->parent = right;

right->parent = NULL;

right->left = root;

}

/*make sure that tree is not empty,which mean tree's root is not null*/

int do_splay(key_type key,splaytree *tree)

{

splaytree_node subleft = {0,};

splaytree_node subright = {0,};

splaytree_node* psubleft = &subleft;

splaytree_node* psubright = &subright;

splaytree_node* root = tree->root;

int ret ;

for(;;)

{

ret = key - root->key;

if(ret == 0)

break;

if(ret < 0)

{

splaytree_node* left ;

left = root->left;

if( left == NULL)

break;

if(ret = (key - left->key)< 0)

{

rotate_right(root);

root = left;

left = left->left;

if(left == NULL)

break;

}

/* 右连接：将当前根及其右子树连接到右树上。*/

psubright->left = root;

root->parent = psubright;

psubright = root;

root->left = NULL;

/*左子结点作为新根*/

root = left;

root->parent = NULL;

}

else

{

splaytree_node* right;

right = root->right;

if(right == NULL)

break;

if(ret = (key - right->key) > 0 )

{

rotate_left(root);

root = right;

right = right->right;

if(right == NULL)

break;

}

/*左连接：将当前根及其左子树连接到左树上。*/

psubleft->right = root;

root->parent = psubleft;

psubleft = root;

root->right = NULL;

/*右子结点作为新根。*/

root = right;

root->parent = NULL;

}

}

psubleft->right = root->left;

if(root->left)

root->left->parent = psubleft;

psubright->left = root->right;

if(root->right) 

root->right->parent = psubright;

root->left = subleft.right;

if(subleft.right)

subleft.right->parent = root;

root->right = subright.left;

if(subright.left)

subright.left->parent = root;

tree->root = root;

return ret;

}

splaytree_node* splaytree_lookup(key_type key,splaytree* tree)

{

if(tree->root == NULL)

return NULL;

if(do_splay(key,tree) != 0)

return NULL;

else

return tree->root;

}

int  splaytree_insert(splaytree_node* node,splaytree *tree)

{

splaytree_node* root = NULL;

int res;

if(tree->root == NULL)

{

tree->root = node;

return 0;

}

res = do_splay(node->key,tree);

if(res == 0)

return -1;

root = tree->root;

if(res < 0)

{

splaytree_node *left;

left = root->left;

node->left = left;

if(left)

left->parent = node;

node->right = root;

root->parent = node;

root->left = NULL;

}

else

{

splaytree_node* right;

right = root->right;

node->right = right;

if(right)

right->parent = node;

node->left = root;

root->parent = node;

root->right = NULL;

}

tree->root = node;

return 0;

}

int splaytree_remove(key_type key,splaytree* tree)

{

splaytree_node *node;

node = splaytree_lookup(key,tree);

if(node == NULL)

return -1;

splaytree_node *left = tree->root->left;

splaytree_node *right = tree->root->right;

splaytree_freenode(node);

left->parent = NULL;

right->parent = NULL;

if(left == NULL)

{

tree->root = right;

return 0;

}

else

{

tree->root = left;

do_splay(key,tree);

tree->root->right = right;

if(right)

right->parent = tree->root;

return 0;

}

}

————————————————————————————————————————————————

————————splaytre_test.c——————————————————————————————

#include

#include

#include

#include

#include"splaytree.h"

#define N 12

#define rand(X)  (rand()%X)

void test_insert()

{

int i;

int tmp;

splaytree tree;

splaytree_node *node[N];

tree.root = NULL;

for(i = 0;i

{

tmp = rand(200);

node[i] = splaytree_allocnode(tmp,tmp);

splaytree_insert(node[i],&tree);

}

}

void test()

{

splaytree tree;

tree.root = NULL;

test_insert();

//test_lookup();

//test_remove();

}

int main()

{

test();

return 0;

}

——————————————————————

阅读(1521) | 评论(0) | 转发(0) |

0

上一篇：测量一个函数的平均执行时间

下一篇：Outlook风格的单列使用不同的颜色显示新邮件数