前文二叉搜索树的C实现（2）中提到了，我们可以把二叉搜索树中的任意一个节点提拔成根，
方法如下：
１ 调用bst_select(root,K),返回第Ｋ大的节点node
２ 调用bst_bubble（root,node）,把node，升为root。
注 其实bst_select(root,K) 返回的是第K+1大的节点，因为bst_select（root，0）是最小节点。
bst_node* bst_select_root(bst_node* root,int k)
{
if(root == NULL)
{
printf("[bst_select_root] root is null\n");
return root;
}
if(k>root->counter || k < 0)
{
printf("k is not valid (%d-%d)\n",root->counter,k);
return root;
}
bst_node * node = bst_select(root,k);
if (node != NULL)
return bst_bubble(root,node);
else
return root;
}
bst_select函数在二叉搜索树C实现中已经实现了，为了方便阅读，在此再次贴出代码
bst_node* bst_select(bst_node* root,int k)
{
if(root == NULL)
return NULL;/*not find the kth node*/
int t=0;
if(root->left ==NULL)
t = 0;
else
t = root->left->counter;
if(t>k)
return bst_select(root->left,k);
else if(t
return bst_select(root->right,k-t-1);
return root;
}
既然我们可以把任何一个节点提拔成根，这就启发了我们如何将二叉搜索树平衡，就是把key值是
中间的那个节点提拔成 根，这样左右就平衡了。如果我们递归操作，那么，我们就得到平衡二叉搜索树。
前提条件是，我们必须知道每棵树有多少个节点，树的节点个数需要维护一个专门的字段，counter。
表示以node为根的树共有多少个节点
node->counter = node->left->counter+node->right->counter +1;
当然上面的等式只是解释counter定义用的，实际需要讨论 左右孩子不存在的情况。
好在我们前文的代码中已经维护了counter这个字段。
bst_node* bst_balance(bst_node* root)
{
if(root == NULL)
return root ;
if(root->counter < 2 )
return root;
root = bst_select_root(root,root->counter/2);
root->left = bst_balance(root->left);
if(root->left)
root->left->parent = root;
root->right = bst_balance(root->right);
if(root->right)
root->right->parent = root;
return root;
}
参考文献：
1 算法：C语言实现 Robert Sedgewick著
阅读(3181) | 评论(0) | 转发(2) |
