/******************************************************************************************
 * Data Structures in C++
 * ISBN: 7-302-33064-6 & 7-302-33065-3 & 7-302-29652-2 & 7-302-26883-3
 * Junhui DENG, deng@tsinghua.edu.cn
 * Computer Science & Technology, Tsinghua University
 * Copyright (c) 2006-2013. All rights reserved.
 ******************************************************************************************/

/*
 * AVLÊ÷
 * »ùÓÚBSTreeµÄÀ©³ä
 */

package dsa;

public class AVLTree extends BSTree implements Dictionary {
   /**************************** ¹¹Ôì·½·¨ ****************************/
   public AVLTree() { super(); }
   public AVLTree(BinTreePosition r) { super(r); }
   public AVLTree(BinTreePosition r, Comparator c) { super(r, c); }

   /**************************** ´Êµä·½·¨£¨¸²¸Ç¸¸ÀàBSTree£© ****************************/
   //²åÈëÌõÄ¿(key, value)£¬²¢·µ»Ø¸ÃÌõÄ¿
   public Entry insert(Object key, Object value) {
      Entry e = super.insert(key, value);//µ÷ÓÃ¸¸Àà·½·¨Íê³É²åÈë
      root = rebalance(lastV.getParent(), root);//´Ó²åÈë½ÚµãµÄ¸¸Ç×¿ªÊ¼ÖØÐÂÆ½ºâ»¯
      return e;
   }

   //Èô´ÊµäÖÐ´æÔÚÒÔkeyÎª¹Ø¼üÂëµÄÌõÄ¿£¬Ôò½«Õª³ýÆäÖÐµÄÒ»¸ö²¢·µ»Ø£»·ñÔò£¬·µ»Ønull
   public Entry remove(Object key) {
      Entry e = super.remove(key);//µ÷ÓÃ¸¸Àà·½·¨Íê³ÉÉ¾³ý
      if (null != e) root = rebalance(lastV, root);//´ÓÉ¾³ý½ÚµãµÄ¸¸Ç×¿ªÊ¼ÖØÐÂÆ½ºâ»¯
      return e;
   }

   /**************************** ¸¨Öú·½·¨ ****************************/
   //´Ó½Úµãz¿ªÊ¼£¬×ÔÉÏ¶øÏÂÖØÐÂÆ½ºâ»¯
   //·µ»Øºó£¬rootÈÔÎªÆ½ºâºóµÄ£¨Õû¿Ã£©Ê÷µÄ¸ù½Úµã
   protected static BinTreePosition rebalance(BinTreePosition z, BinTreePosition r) {
      if (null == z) return r;
      while (true) {//´Óz¿ªÊ¼£¬ÏòÉÏÖðÒ»¼ì²ézµÄ×æÏÈ
         if (!isBalanced(z))  rotate(z);//Èôz½ÚµãÊ§È¥Æ½ºâ£¬ÔòÍ¨¹ýÐý×ªÊ¹Ö®ÖØÐÂÆ½ºâ
         if (!z.hasParent())  return z;
         z = z.getParent();//¼ÌÐø¼ì²éÆä¸¸Ç×
      }//while
   }

   //ÅÐ¶Ï½ÚµãvÊÇ·ñÆ½ºâ
   protected static boolean isBalanced(BinTreePosition v) {
      if (null == v) return true;
      int lH = (v.hasLChild()) ? (v.getLChild().getHeight()) : -1;
      int rH = (v.hasRChild()) ? (v.getRChild().getHeight()) : -1;
      int deltaH = lH - rH;
      return (-1 <= deltaH) && (deltaH <= 1);
   }

   //Í¨¹ýÐý×ª£¬Ê¹½ÚµãzµÄÆ½ºâÒò×ÓµÄ¾ø¶ÔÖµ²»³¬¹ý1£¨Ö§³ÖAVLÊ÷£©
   //·µ»ØÐÂµÄ×ÓÊ÷¸ù
   public static BinTreePosition rotate(BinTreePosition z) {
      BinTreePosition   y = tallerChild(z);//È¡yÎªz¸ü¸ßµÄº¢×Ó
      BinTreePosition   x = tallerChild(y);//È¡xÎªy¸ü¸ßµÄº¢×Ó
      boolean cType = z.isLChild();//¼ÇÂ¼£ºzÊÇ·ñ×óº¢×Ó
      BinTreePosition   p = z.getParent();//pÎªzµÄ¸¸Ç×
      BinTreePosition   a, b, c;//×Ô×óÏòÓÒ£¬Èý¸ö½Úµã
      BinTreePosition   t0, t1, t2, t3;//×Ô×óÏòÓÒ£¬ËÄ¿Ã×ÓÊ÷
      /******** ÒÔÏÂ·ÖËÄÖÖÇé¿ö ********/
      if (y.isLChild()) {//ÈôyÊÇ×óº¢×Ó£¬Ôò
         c = z;   t3 = z.getRChild();
         if (x.isLChild()) {//ÈôxÊÇ×óº¢×Ó
            b = y;   t2 = y.getRChild();
            a = x;   t1 = x.getRChild();  t0 = (BSTreeNode)x.getLChild();
         } else {//ÈôxÊÇÓÒº¢×Ó
            a = y;   t0 = y.getLChild();
            b = x;   t1 = x.getLChild();  t2 = (BSTreeNode)x.getRChild();
         }
      } else {//ÈôyÊÇÓÒº¢×Ó£¬Ôò
         a = z;   t0 = z.getLChild();
         if (x.isRChild()) {//ÈôxÊÇÓÒº¢×Ó
            b = y;   t1 = y.getLChild();
            c = x;   t2 = x.getLChild();  t3 = (BSTreeNode)x.getRChild();
         } else {//ÈôxÊÇ×óº¢×Ó
            c = y;   t3 = y.getRChild();
            b = x;   t1 = x.getLChild();  t2 = (BSTreeNode)x.getRChild();
         }
      }
      //ÕªÏÂÈý¸ö½Úµã
      z.secede();
      y.secede();
      x.secede();
      //ÕªÏÂËÄ¿Ã×ÓÊ÷
      if (null != t0) t0.secede();
      if (null != t1) t1.secede();
      if (null != t2) t2.secede();
      if (null != t3) t3.secede();
      //ÖØÐÂÁ´½Ó
      a.attachL(t0); a.attachR(t1); b.attachL(a);
      c.attachL(t2); c.attachR(t3); b.attachR(c);
      //×ÓÊ÷ÖØÐÂ½ÓÈëÔ­Ê÷
      if (null != p)
         if (cType)  p.attachL(b);
         else           p.attachR(b);
      return b;//·µ»ØÐÂµÄ×ÓÊ÷¸ù
   }//rotate

   //·µ»Ø½ÚµãpµÄº¢×ÓÖÐµÄ¸ü¸ßÕß
   protected static BinTreePosition tallerChild(BinTreePosition v) {
      int   lH = v.hasLChild() ? v.getLChild().getHeight() : -1;
      int   rH = v.hasRChild() ? v.getRChild().getHeight() : -1;
      if (lH > rH)   return v.getLChild();
      if (lH < rH)   return v.getRChild();
      if (v.isLChild()) return v.getLChild();
      else                    return v.getRChild();
   }

   //·µ»Ø½ÚµãpµÄº¢×ÓÖÐµÄ¸ü°«Õß
   protected static BinTreePosition shorterChild(BinTreePosition v) {
      int   lH = v.hasLChild() ? v.getLChild().getHeight() : -1;
      int   rH = v.hasRChild() ? v.getRChild().getHeight() : -1;
      if (lH > rH)   return v.getRChild();
      if (lH < rH)   return v.getLChild();
      if (v.isLChild()) return v.getRChild();
      else                    return v.getLChild();
   }
}
