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();
           }