当前页面位置: » 丰搜网 » 文档中心 » 详细内容
数据结构与算法(c#实现)系列---avltree（一）
数据结构与算法(c#实现)系列---avltree（一）
using system;xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" />
using system.collections;
namespace datastructure
{
/// <summary>
/// avltree 的摘要说明。-----平衡二叉查找树
/// </summary>
public class avltree:bst
{
protected int height;//空树的高定义为-1;
//构造一棵空的二叉查找树
public avltree():base()
{
//
// todo: 在此处添加构造函数逻辑
//
height=-1;
}
public avltree(object _obj):base(_obj)
{
height=0;
}
//------------------------------------------------------------------
protected override object getemptyinstance(uint _degree)
{ return new avltree(); }
//------------------------------------------------------------------
protected int balancefactor()
{
if (this.isempty() )
return 0;
return ((avltree)this.left).height-((avltree)this.right).height;
}
//调整高度
protected void adjustheight(){ this.height=math.max( ((avltree)this.left).height, ((avltree)this.right).height)+1; }
//平衡时的四种旋转方式
protected void llrotation()
{
if( this.isempty() )
throw new exception("my:invalid operation!");
avltree avlb=new avltree(this.key);
avlb.attachsubtree(1,(avltree)this[0][1]);
avlb.attachsubtree(2,(avltree)this[1]);
this.key=this[0].key;
this[0]=this[0][0];
this[1]=avlb;
//调整两个节点的高度
((avltree)this.right).adjustheight();
this.adjustheight();
}
protected void lrrotation()
{
if( this.isempty() )
throw new exception("my:invalid operation!");
((avltree)this.left).rrrotation();
this.llrotation();
}
protected void rrrotation()
{
if( this.isempty() )
throw new exception("my:invalid operation!");
avltree avlb=new avltree(this.key);
avlb.attachsubtree(1,(avltree)this[0]);
avlb.attachsubtree(2,(avltree)this[1][0]);
//avla.attachsubtree(1,avlb);
//this=avla;
this.key=this[1].key;
this[0]=avlb;
this[1]=this[1][1];
//调整两个节点的高度
((avltree)this.left).adjustheight();
this.adjustheight();
}
protected void rlrotation()
{
if( this.isempty() )
throw new exception("my:invalid operation!");
((avltree)this.right).llrotation();
this.rrrotation();
}
