数据结构与算法(C#实现)系列---AVLTree（一）

数据结构与算法(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();

}