二叉搜索树，如果不平衡，搜索性能就会降低，极端情况下，就退化成了链表，而且，比链表要浪费存储空间。
上一篇博文的二叉搜索树的平衡策略，提出了一种解决办法。就是把中值的节点 提拔到根，然后对左子树和右子树做相同的操作，递归结束的时候，我们得到了一个完美平衡二叉树。
这篇博文介绍随机化的策略。
所谓随机化的策略，就是谁是二叉搜索树的根，并不取决插入 删除的先后次序。普通的二叉搜索树的平衡情况，完全取决于插入删除的次序。我们想想这么一种情况，如果按照从大到小的次序 依次插入，我们的二叉搜索树就很不幸的退化了链表。
随机化插入的实现思想：将一个新的节点插入到一个存在N个节点的数中去，新节点出现在根位置的概率是1/(N+1),因为我们依据概率来决定是否插入到根。 如果不是插入到根，我们使用上述方法递归插入到左子树
或者是右子树。
bst_node* bst_insert_random(bst_node *root,bst_node* node)
{
if (root == NULL)
return node;
if(rand()counter+1))
return bst_insert_top(root,node);
if(node->key < root->key)
{
root->left = bst_insert_random(root->left,node);
root->left->parent =root;
}
else
{
root->right = bst_insert_random(root->right,node);
root->right->parent = root;
}
root->counter++;
return root;
}
-------------------------------------------------------------------------------
OK，插入比较容易实现，下面分析删除操作的随机化。
首先，对删除节点，我们换一个思路，删除节点node，其实就是相当于把节点node的左子树和右子树结合成
一个新的子树，然后交给node的parent托管。
我们首先实现将节点的左右子树连接成一个新树。
b是右子树，a是左子树，b中的任何一个节点都比a中的任何一个节点大。
我们选择b子树的最小的节点作为新根，则b的其他节点在新根的右边，a连接到新根的左边，
如此操作，我们就将左右子树结合成了一个新子树。有了新子树，因为父亲节点被删掉了，
所以由爷爷来负责托管新子树，即爷爷变成了新子树的新父亲。
如上图所示，我们要删除节点9，那么我们首先将9的两个孩子连接成一棵子树。
我们选择了右子树（即17为根的那棵子树）的最小节点 11，提拔成右子树的根，同时也作为新子树的根，
然后原来的左子树（即5为根的那棵子树），作为11的左孩子。这样我们就得到了父亲9不在了之后，
左右孩子就团结成了一棵新树。然后是确立新的父子关系，原来的爷爷（节点27）变成新生成子树的父亲。
OK，可以安心的释放9这个节点了。
步骤
1 将被删除节点的左右孩子，组合成一棵新树 （bst_joinLR实现）
2 新树的父亲设为删除节点的父亲。
3 释放删除节点。
bst_node* bst_joinLR(bst_node* a,bst_node* b)
{
if (b == NULL)
return a;
b = bst_select_root(b,0);
b->left = a;
if(a)
{
a->parent = b;
b->counter += a->counter;
}
return b;
}
bst_node* bst_deleteR(bst_node* root,bst_node*node)
{
bst_node* par = node->parent;
if (par == NULL)
{
root = bst_joinLR(node->left,node->right);
}
else
{
bst_down_counter(root, node);
if(par->left == node)
{
par->left =bst_joinLR(node->left,node->right);
if(par->left)
par->left->parent = par;
}
else
{
par->right = bst_joinLR(node->left,node->right);
if(par->right)
par->right->parent = par;
}
}
bst_freenode(node);
return root;
}
-----------------------------------------------------------------------------------
上面的删除过程，其实存在缺点的，缺点就是位于第一步，生成新子树。
我们总是选择删除节点的右孩子的最小节点作为根，这严重不公平，左孩子表示了强烈的愤慨。而且这种策略会带来潜在的不平衡。
优化方案是：概率决定左孩子做根还是右孩子做根。大树优先做根。原因是如果小树做根，大量的节点会位于新 根一侧，造成不平衡加剧。
我们将bst_deleteR中的bst_joinLR函数替换成我们的优化版本bst_joinLR_random，bst_deleteR函数就变成了随机二叉搜索树的删除函数了。
bst_node* bst_joinLR_random(bst_node*a ,bst_node*b)
{
if(a==NULL)
return b;
if(b ==NULL)
return a;
if(rand()/RAND_MAX*(a->counter+b->counter+1) < (a->counter))
{
a->counter += b->counter;
a->right = bst_joinLR(a->right,b);
if(a->right)
a->right->parent = a;
return a;
}
else
{
b->counter += a->counter;
b->left = bst_joinLR(a,b->left);
if(b->left)
b->left->parent = b;
return b;
}
}
阅读(4341) | 评论(0) | 转发(1) |
