0001 /* 0002 * AVL树 0003 * 基于BSTree的扩充 0004 */ 0005 0006 package dsa; 0007 0008 public class AVLTree extends BSTree implements Dictionary { 0009 /**************************** 构造方法 ****************************/ 0010 public AVLTree() { super(); } 0011 public AVLTree(BinTreePosition r) { super(r); } 0012 public AVLTree(BinTreePosition r, Comparator c) { super(r, c); } 0013 0014 /**************************** 词典方法(覆盖父类BSTree) ****************************/ 0015 //插入条目(key, value),并返回该条目 0016 public Entry insert(Object key, Object value) { 0017 Entry e = super.insert(key, value);//调用父类方法完成插入 0018 root = rebalance(lastV.getParent(), root);//从插入节点的父亲开始重新平衡化 0019 return e; 0020 } 0021 0022 //若词典中存在以key为关键码的条目,则将摘除其中的一个并返回;否则,返回null 0023 public Entry remove(Object key) { 0024 Entry e = super.remove(key);//调用父类方法完成删除 0025 if (null != e) root = rebalance(lastV, root);//从删除节点的父亲开始重新平衡化 0026 return e; 0027 } 0028 0029 /**************************** 辅助方法 ****************************/ 0030 //从节点z开始,自上而下重新平衡化 0031 //返回后,root仍为平衡后的(整棵)树的根节点 0032 protected static BinTreePosition rebalance(BinTreePosition z, BinTreePosition r) { 0033 if (null == z) return r; 0034 while (true) {//从z开始,向上逐一检查z的祖先 0035 if (!isBalanced(z)) rotate(z);//若z节点失去平衡,则通过旋转使之重新平衡 0036 if (!z.hasParent()) return z; 0037 z = z.getParent();//继续检查其父亲 0038 }//while 0039 } 0040 0041 //判断节点v是否平衡 0042 protected static boolean isBalanced(BinTreePosition v) { 0043 if (null == v) return true; 0044 int lH = (v.hasLChild()) ? (v.getLChild().getHeight()) : -1; 0045 int rH = (v.hasRChild()) ? (v.getRChild().getHeight()) : -1; 0046 int deltaH = lH - rH; 0047 return (-1 <= deltaH) && (deltaH <= 1); 0048 } 0049 0050 //通过旋转,使节点z的平衡因子的绝对值不超过1(支持AVL树) 0051 //返回新的子树根 0052 public static BinTreePosition rotate(BinTreePosition z) { 0053 BinTreePosition y = tallerChild(z);//取y为z更高的孩子 0054 BinTreePosition x = tallerChild(y);//取x为y更高的孩子 0055 boolean cType = z.isLChild();//记录:z是否左孩子 0056 BinTreePosition p = z.getParent();//p为z的父亲 0057 BinTreePosition a, b, c;//自左向右,三个节点 0058 BinTreePosition t0, t1, t2, t3;//自左向右,四棵子树 0059 /******** 以下分四种情况 ********/ 0060 if (y.isLChild()) {//若y是左孩子,则 0061 c = z; t3 = z.getRChild(); 0062 if (x.isLChild()) {//若x是左孩子 0063 b = y; t2 = y.getRChild(); 0064 a = x; t1 = x.getRChild(); t0 = (BSTreeNode)x.getLChild(); 0065 } else {//若x是右孩子 0066 a = y; t0 = y.getLChild(); 0067 b = x; t1 = x.getLChild(); t2 = (BSTreeNode)x.getRChild(); 0068 } 0069 } else {//若y是右孩子,则 0070 a = z; t0 = z.getLChild(); 0071 if (x.isRChild()) {//若x是右孩子 0072 b = y; t1 = y.getLChild(); 0073 c = x; t2 = x.getLChild(); t3 = (BSTreeNode)x.getRChild(); 0074 } else {//若x是左孩子 0075 c = y; t3 = y.getRChild(); 0076 b = x; t1 = x.getLChild(); t2 = (BSTreeNode)x.getRChild(); 0077 } 0078 } 0079 //摘下三个节点 0080 z.secede(); 0081 y.secede(); 0082 x.secede(); 0083 //摘下四棵子树 0084 if (null != t0) t0.secede(); 0085 if (null != t1) t1.secede(); 0086 if (null != t2) t2.secede(); 0087 if (null != t3) t3.secede(); 0088 //重新链接 0089 a.attachL(t0); a.attachR(t1); b.attachL(a); 0090 c.attachL(t2); c.attachR(t3); b.attachR(c); 0091 //子树重新接入原树 0092 if (null != p) 0093 if (cType) p.attachL(b); 0094 else p.attachR(b); 0095 return b;//返回新的子树根 0096 }//rotate 0097 0098 //返回节点p的孩子中的更高者 0099 protected static BinTreePosition tallerChild(BinTreePosition v) { 0100 int lH = v.hasLChild() ? v.getLChild().getHeight() : -1; 0101 int rH = v.hasRChild() ? v.getRChild().getHeight() : -1; 0102 if (lH > rH) return v.getLChild(); 0103 if (lH < rH) return v.getRChild(); 0104 if (v.isLChild()) return v.getLChild(); 0105 else return v.getRChild(); 0106 } 0107 0108 //返回节点p的孩子中的更矮者 0109 protected static BinTreePosition shorterChild(BinTreePosition v) { 0110 int lH = v.hasLChild() ? v.getLChild().getHeight() : -1; 0111 int rH = v.hasRChild() ? v.getRChild().getHeight() : -1; 0112 if (lH > rH) return v.getRChild(); 0113 if (lH < rH) return v.getLChild(); 0114 if (v.isLChild()) return v.getRChild(); 0115 else return v.getLChild(); 0116 } 0117 }