Chinaunix首页 | 论坛 | 博客
  • 博客访问: 3846098
  • 博文数量: 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-07-10 12:55:16

二叉搜索树,如果不平衡,搜索性能就会降低,极端情况下,就退化成了链表,而且,比链表要浪费存储空间。
上一篇博文的二叉搜索树的平衡策略,提出了一种解决办法。就是把中值的节点 提拔到根,然后对左子树和右子树做相同的操作,递归结束的时候,我们得到了一个完美平衡二叉树。

这篇博文介绍随机化的策略。
所谓随机化的策略,就是谁是二叉搜索树的根,并不取决插入 删除的先后次序。普通的二叉搜索树的平衡情况,完全取决于插入删除的次序。我们想想这么一种情况,如果按照从大到小的次序 依次插入,我们的二叉搜索树就很不幸的退化了链表。

随机化插入的实现思想:将一个新的节点插入到一个存在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;
}
}

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