数据结构与算法(C#实现)系列---AVLTree（一）
using System;
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();
}
|