Chinaunix首页 | 论坛 | 博客
  • 博客访问: 3846678
  • 博文数量: 146
  • 博客积分: 3918
  • 博客等级: 少校
  • 技术积分: 8584
  • 用 户 组: 普通用户
  • 注册时间: 2010-10-17 13:52
个人简介

个人微薄: weibo.com/manuscola

文章分类

全部博文(146)

文章存档

2016年(3)

2015年(2)

2014年(5)

2013年(42)

2012年(31)

2011年(58)

2010年(5)

分类:

2011-06-28 22:58:50

二叉搜索树,有一个需求是,将新插入的节点放入根,这样做的好处有二
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);
}



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