Chinaunix首页 | 论坛 | 博客
  • 博客访问: 154955
  • 博文数量: 27
  • 博客积分: 414
  • 博客等级: 下士
  • 技术积分: 250
  • 用 户 组: 普通用户
  • 注册时间: 2011-10-06 15:52
个人简介

身为挨踢人,却不想被挨踢。努力多学点。

文章分类

全部博文(27)

文章存档

2012年(17)

2011年(10)

我的朋友

分类:

2011-11-03 09:10:55

二叉搜索树,有一个需求是,将新插入的节点放入根,这样做的好处有二
1 新插入的节点飘在二叉树的上面层,老的节点在下层,一般新节点被搜索的概率要高,
  这样做,可以提高搜索的效率
2 后面二叉搜索树进化成平衡二叉搜索树,需要这个从根插入的方法

从根插入,简单的说可以分成两步走:
1 标准插入
2 将插入节点,层层冒泡,直到冒泡冒到根。
如果节点node不是root,他一定有父亲parent,会有两种情况
1 node 是父亲parent的右孩子,以parent为轴左旋 
  即下图的左-->右。父parent被压下来,y 冒泡升上去。
2 node是父亲parent 的左孩子,以父parent为轴右旋
  即下图的左<--右。父亲parent被压下来,x冒泡升上去。

以此类推,我们关注的节点最终生成了root。


按照我们提供的这种冒泡的方法,我们可以将任何一个节点提升为根节点。
首先根据key找到这个节点,然后将节点层层冒泡,直至升为根 root。

当然,我们也可以将第K大的数升为root,方法是
1 调用bst_select(root,K),返回第K大的节点node,
2 调用bst_bubble(root,node),把node,升为root


bst_node* bst_left_rotate(bst_node* node,bst_node* root)
{
bst_node* right = node->right;
/*for recursive ,consider that if root is not an real root of a tree */
bst_node* par = (node == root)?NULL:node->parent;

node->right = right->left;
if(right->left)
right->left->parent = node;

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

if(par)
{
if(node == par->left)
par->left = right;
else
par->right =right;
}
else
{
root = right;
}

node->parent = right;
#ifdef OPERATION_SELECT
right->counter = node->counter;
node->counter -= ((right->right)==NULL)?1:(right->right->counter+1);
#endif

return root;
}

bst_node* bst_right_rotate(bst_node* node,bst_node* root)
{
bst_node* left = node->left;
bst_node*par = (node == root)?NULL:node->parent;

node->left = left->right;
if(left->right)
left->right->parent = node;
left->right = node;
left->parent = par;

if(par)
{
if (par->left == node)
par->left = left;
else
par->right = left;
}

else
root = left;
node->parent = left;
#ifdef OPERATION_SELECT
left->counter = node->counter;
(node->counter) -= ((left->left)==NULL)?1:(left->left->counter+1);
#endif

return root;
}


/*before call this function ,make sure that node is not null*/
bst_node* bst_bubble(bst_node* root,bst_node* node)
{
bst_node* par;
par = node->parent;
while(par && node != root)
{
if(node == par->left)
root = bst_right_rotate(par,root);
else
root = bst_left_rotate(par,root);
par = node->parent;
}
return root;
}

/*before call this function,make sure that node is not in the tree */
bst_node* bst_insert_top(bst_node* root,bst_node* node)
{
if(node == NULL)
{
printf("node is null,just return \n");
return root;
}
bst_node* root_tmp = bst_insert(root,node);
return bst_bubble(root_tmp,node);
}



阅读(666) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~