1 package ren.laughing.datastructure.baseImpl;  2   3 /**  4  * 自平衡二叉查找树AVL 继承二叉查找树  5  *   6  * @author Laughing_Lz  7  * @time 2016年4月20日  8  */  9 public class AVLTree extends BSTree { 10     /** 11      * 统一平衡方法 旋转操作 12      *  13      * @param z 14      *            z是失衡的结点 15      * @return 返回平衡后子树的根结点 16      */ 17     private BinTreeNode rotate(BinTreeNode z) { 18         BinTreeNode y = heightSubT(z);// 取y为z更高的孩子 19         BinTreeNode x = heightSubT(y);// 取x为y更高的孩子 20         boolean isLeft =z.isLChild();//标记z是否是左孩子 21         BinTreeNode p = z.getParent();//取z的父结点 22         BinTreeNode a,b,c; 23         BinTreeNode t0,t1,t2,t3; 24         //以下分四种情况重命名 25         if(y.isLChild()){
   //1如果y是左孩子 26             c = z; 27             t3 = z.getRChild(); 28             if(x.isLChild()){
   //1.1如果x是左孩子(左左失衡) 29                 a = x; 30                 b = y; 31                 t0 = x.getLChild(); 32                 t1 = x.getRChild(); 33                 t2 = y.getRChild(); 34             }else{
   //1.2如果x是右孩子(左右失衡) 35                 b = x; 36                 a = y; 37                 t1 = x.getLChild(); 38                 t2 = x.getRChild(); 39                 t0 = y.getLChild(); 40             } 41         }else{
   //2如果y是右孩子 42             a = z; 43             t0 = z.getLChild(); 44             if(x.isRChild()){
   //2.1如果x是右孩子(右右失衡) 45                 c = x; 46                 b = y; 47                 t2 = x.getLChild(); 48                 t3 = x.getRChild(); 49                 t1 = y.getLChild(); 50             }else{
   //2.2如果x是左孩子(右左失衡) 51                 b = x; 52                 c = y; 53                 t1 = x.getLChild(); 54                 t2 =x.getRChild(); 55                 t3 = y.getRChild(); 56             } 57         } 58 //        x.server();//疑问，已经赋值给a b c 还有何用？★ 59 //        y.server(); 60 //        z.server(); 61         a.server();//断开与父结点的连接 62         b.server(); 63         c.server(); 64         if(t0 != null){ 65             t0.server(); 66         } 67         if(t1 != null){ 68             t1.server(); 69         } 70         if(t2 != null){ 71             t2.server(); 72         } 73         if(t3 != null){ 74             t3.server(); 75         } 76         b.setLChild(a);//重新设置左右孩子，平衡 77         b.setRChild(c); 78         a.setLChild(t0); 79         a.setRChild(t1); 80         c.setLChild(t2); 81         c.setRChild(t3); 82         if(isLeft){ 83             p.setLChild(b); 84         }else{ 85             p.setRChild(b); 86         } 87         return b;//返回平衡后子树的根 88     } 89  90     /** 91      * 获取结点v较高的子树 92      *  93      * @param v 94      * @return 95      */ 96     private BinTreeNode heightSubT(BinTreeNode v) { 97         if (v == null) { 98             return null; 99         }100         int lH = -1;// 若没有左子树，默认左子树高度为-1101         if (v.hasLChild()) {102             lH = v.getLChild().getHeight();103         }104         int rH = -1;// 若没有右子树，默认右子树高度为-1105         if (v.hasRChild()) {106             rH = v.getRChild().getHeight();107         }108         if (lH > rH) {109             return v.getLChild();110         } else if (lH < rH) {111             return v.getRChild();112         } else {
   // 若两边子树等高113             if (v.isLChild()) {114                 return v.getLChild();115             } else {116                 return v.getRChild();117             }118         }119     }120     /**121      * 重写BSTree的insert方法122      * insert之后要重新平衡123      */124     @Override125     public void insert(Object obj) {126         super.insert(obj);127         root = reBalance(startBN);//重新平衡树128     }129     /**130      * 重新平衡AVL树131      * @param startBN132      * @return 返回平衡后的AVL树根结点133      */134     private BinTreeNode reBalance(BinTreeNode startBN) {135         if(startBN == null){136             return root;137         }138         BinTreeNode c = startBN;139         while(startBN != null){
   //从startBN开始，向上逐一检查 z 的祖先★140             if(!isBalance(startBN)){
   //若startBN失衡，则旋转使之重新平衡★141                 startBN = rotate(startBN);142             }143             c = startBN;144             startBN = startBN.getParent();//继续检查其父亲145         }146         return c;147     }148     /**149      * 判断该结点是否平衡150      * @param startBN151      * @return152      */153     private boolean isBalance(BinTreeNode startBN) {154         if(startBN == null){155             return true;156         }157         int lH = startBN.hasLChild()?startBN.getLChild().getHeight():-1;158         int rH = startBN.hasRChild()?startBN.getRChild().getHeight():-1;159         return (Math.abs(lH-rH) <= 1);160     }161     /**162      * 重写BSTree的remove方法163      */164     @Override165     public Object remove(Object ele) {166         Object obj = super.remove(ele);167         root = reBalance(startBN);//重新平衡AVL树168         return obj;169     }170 }