数据结构与算法 (C# 实现 ) 系列 ---AVLTree （一）
using System;
using System.Collections;
namespace DataStructure
{
///
1<summary>
2
3/// AVLTree 的摘要说明。-----平衡二叉查找树
4
5/// </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();
}