二叉搜索树的C实现(2)---从根插入节点

二叉搜索树，有一个需求是，将新插入的节点放入根，这样做的好处有二

1 新插入的节点飘在二叉树的上面层，老的节点在下层，一般新节点被搜索的概率要高，

  这样做，可以提高搜索的效率

2 后面二叉搜索树进化成平衡二叉搜索树，需要这个从根插入的方法

从根插入，简单的说可以分成两步走：

1 标准插入

２　将插入节点，层层冒泡，直到冒泡冒到根。

如果节点ｎｏｄｅ不是ｒｏｏｔ，他一定有父亲ｐａｒｅｎｔ，会有两种情况

１　node 是父亲parent的右孩子，以ｐａｒｅｎｔ为轴左旋　

　　即下图的左－－>右。父parent被压下来，y 冒泡升上去。

２　node是父亲parent 的左孩子，以父ｐａｒｅｎｔ为轴右旋

　　即下图的左<－－右。父亲parent被压下来，ｘ冒泡升上去。

以此类推，我们关注的节点最终生成了ｒｏｏｔ。

按照我们提供的这种冒泡的方法，我们可以将任何一个节点提升为根节点。

首先根据ｋｅｙ找到这个节点，然后将节点层层冒泡，直至升为根　ｒｏｏｔ。

当然，我们也可以将第Ｋ大的数升为ｒｏｏｔ，方法是

１　调用bst_select(root,K),返回第Ｋ大的节点node,

２　调用bst_bubble（root,node）,把node，升为ｒｏｏｔ

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);

}