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