三、代码实践
接下来，我们从代码层面来定义一下树的实体结构，如下：
1public class AVLNode<E extends Comparable<E>> { 2 3 /**节点关键字*/ 4 E key; 5 6 /**当前节点树高*/ 7 int height; 8 9 /**当前节点的左子节点*/ 10 AVLNode<E> lChild = null; 11 12 /**当前节点的右子节点*/ 13 AVLNode<E> rChild = null; 14 15 public AVLNode(E key) { 16 this.key = key; 17 } 18 19 @Override 20 public String toString() { 21 return "AVLNode{" + 22 "key=" + key + 23 ", height=" + height + 24 ", lChild=" + lChild + 25 ", rChild=" + rChild + 26 '}'; 27 } 28}
我们创建一个算法类AVLSolution，完整实现如下：
1public class AVLSolution<E extends Comparable<E>> { 2 3 /**定义根节点*/ 4 public AVLNode<E> root = null; 5 6 /** 7 * 插入 8 * @param key 9 */ 10 public void insert(E key){ 11 System.out.println("插入[" + key + "]:"); 12 root = insertAVL(key,root); 13 } 14 15 private AVLNode insertAVL(E key, AVLNode<E> node){ 16 if(node == null){ 17 return new AVLNode<E>(key); 18 } 19 //左子树搜索 20 if(key.compareTo(node.key) < 0){ 21 //当前节点左子树不为空,继续递归向下搜索 22 node.lChild = insertAVL(key,node.lChild); 23 //出现不平衡，只会是左子树比右子树高，大于1的时候，就进行调整 24 if(getHeight(node.lChild) - getHeight(node.rChild) == 2){ 25 if(key.compareTo(node.lChild.key) < 0){ 26 //如果插入的节点位于当前节点的左节点的左子树，进行单次右旋转 27 node = rotateRight(node); 28 }else{ 29 //如果插入的节点位于当前节点的左节点的右子树，先左旋转再右旋转 30 node = rotateLeftRight(node); 31 } 32 } 33 }else if(key.compareTo(node.key) > 0){ 34 //当前节点右子树不为空,继续递归向下搜索 35 node.rChild = insertAVL(key,node.rChild); 36 //出现不平衡，只会是右子树比左子树高，大于1的时候，就进行调整 37 if(getHeight(node.rChild) - getHeight(node.lChild) == 2){ 38 if(key.compareTo(node.rChild.key) < 0){ 39 //如果插入的节点位于当前节点的右节点的左子树，先右旋转再左旋转 40 node = rotateRightLeft(node); 41 }else{ 42 //如果插入的节点位于当前节点的右节点的右子树，进行单次左旋转 43 node = rotateLeft(node); 44 } 45 } 46 } else{ 47 //key已经存在，直接返回 48 } 49 //因为节点插入，树高发生变化，更新节点高度 50 node.height = updateHeight(node); 51 return node; 52 } 53 54 /** 55 * 删除 56 * @param key 57 */ 58 public void delete(E key){ 59 root = deleteAVL(key,root); 60 } 61 62 private AVLNode deleteAVL(E key, AVLNode<E> node){ 63 if(node == null){ 64 return null; 65 } 66 if(key.compareTo(node.key) < 0){ 67 //左子树查找 68 node.lChild = deleteAVL(key,node.lChild); 69 //可能会出现，右子树比左子树高2 70 if (getHeight(node.rChild) - getHeight(node.lChild) == 2){ 71 node = rotateLeft(node); 72 } 73 } else if(key.compareTo(node.key) > 0){ 74 //右子树查找 75 node.rChild = deleteAVL(key, node.rChild); 76 //可能会出现，左子树比右子树高2 77 if (getHeight(node.lChild) - getHeight(node.rChild) == 2){ 78 node = rotateRight(node); 79 } 80 }else{ 81 //找到目标元素，删除分三种情况 82 //1.当前节点没有左子树，直接返回当前节点右子树 83 //2.当前节点没有右子树，直接返回当前节点右子树 84 //3.当前节点有左子树、右子树的时候，寻找当前节点的右子树的最末端的左子树，进行替换和移除 85 if(node.lChild == null){ 86 return node.rChild; 87 } 88 if(node.rChild == null){ 89 return node.lChild; 90 } 91 //找到当前节点的右子树的最末端的左子树，也就是右子树最小节点 92 AVLNode<E> minLChild = searchDeleteMin(node.rChild); 93 //删除最小节点，如果高度变化，进行调整 94 minLChild.rChild = deleteMin(node.rChild); 95 minLChild.lChild = node.lChild;//将当前节点的左子树转移到最小节点上 96 97 node = minLChild;//覆盖当前节点 98 //因为是右子树发生高度变低，因此可能需要调整 99 if(getHeight(node.lChild) - getHeight(node.rChild) == 2){ 100 node = rotateRight(node); 101 } 102 } 103 node.height = updateHeight(node); 104 return node; 105 } 106 107 /** 108 * 搜索 109 * @param key 110 * @return 111 */ 112 public AVLNode<E> search(E key){ 113 return searchAVL(key, root); 114 } 115 116 private AVLNode<E> searchAVL(E key, AVLNode<E> node){ 117 if(node == null){ 118 return null; 119 } 120 //左子树搜索 121 if(key.compareTo(node.key) < 0){ 122 return searchAVL(key, node.lChild); 123 }else if(key.compareTo(node.key) > 0){ 124 return searchAVL(key, node.rChild); 125 } else{ 126 //key已经存在，直接返回 127 return node; 128 } 129 } 130 131 /** 132 * 查找需要删除的元素 133 * @param node 134 * @return 135 */ 136 private AVLNode<E> searchDeleteMin(AVLNode<E> node){ 137 if (node == null){ 138 return null; 139 } 140 while (node.lChild != null){ 141 node = node.lChild; 142 } 143 return node; 144 } 145 146 /** 147 * 删除元素 148 * @param node 149 * @return 150 */ 151 private AVLNode<E> deleteMin(AVLNode<E> node){ 152 if(node == null){ 153 return null; 154 } 155 if (node.lChild == null){ 156 return node.rChild; 157 } 158 //移除最小节点 159 node.lChild = deleteMin(node.lChild); 160 //此时移除的是左节点，判断是否平衡高度被破坏 161 if(getHeight(node.rChild) - getHeight(node.lChild) == 2){ 162 //进行调整 163 node = rotateLeft(node); 164 } 165 return node; 166 167 } 168 169 /** 170 * 单次左旋转 171 * @param node 172 * @return 173 */ 174 private AVLNode<E> rotateLeft(AVLNode<E> node){ 175 System.out.println("节点：" + node.key + "，单次左旋转"); 176 AVLNode<E> x = node.rChild;//获取旋转节点的右节点 177 node.rChild = x.lChild;//将旋转节点的右节点的左节点转移，作为旋转节点的右子树 178 x.lChild = node;//将旋转节点作为旋转节点的右子树的左子树 179 180 //更新调整节点高度(先调整旋转节点node) 181 node.height = updateHeight(node); 182 x.height = updateHeight(x); 183 return x; 184 } 185 186 /** 187 * 单次右旋转 188 * @return 189 */ 190 private AVLNode<E> rotateRight(AVLNode<E> node){ 191 System.out.println("节点：" + node.key + "，单次右旋转"); 192 AVLNode<E> x = node.lChild;//获取旋转节点的左节点 193 node.lChild = x.rChild;//将旋转节点的左节点的右节点转移，作为旋转节点的左子树 194 x.rChild = node;//将旋转节点作为旋转节点的左子树的右子树 195 196 //更新调整节点高度(先调整旋转节点node) 197 node.height = updateHeight(node); 198 x.height = updateHeight(x); 199 return x; 200 } 201 202 /** 203 * 左旋转-右旋转 204 * @param node 205 * @return 206 */ 207 private AVLNode<E> rotateLeftRight(AVLNode<E> node){ 208 System.out.println("节点：" + node.key + "，左旋转-右旋转"); 209 //先对当前节点的左节点进行左旋转 210 node.lChild = rotateLeft(node.lChild); 211 //再对当前节点进行右旋转 212 return rotateRight(node); 213 } 214 215 /** 216 * 右旋转-左旋转 217 * @param node 218 * @return 219 */ 220 private AVLNode<E> rotateRightLeft(AVLNode<E> node){ 221 System.out.println("节点：" + node.key + "，右旋转-左旋转"); 222 //先对当前节点的右节点进行右旋转 223 node.rChild = rotateRight(node.rChild); 224 return rotateLeft(node); 225 226 } 227 228 /** 229 * 获取节点高度，如果为空，等于-1 230 * @param node 231 * @return 232 */ 233 private int getHeight(AVLNode<E> node){ 234 return node != null ? node.height: -1; 235 } 236 237 /** 238 * 更新节点高度 239 * @param node 240 * @return 241 */ 242 private int updateHeight(AVLNode<E> node){ 243 //比较当前节点左子树、右子树高度，获取节点高度 244 return Math.max(getHeight(node.lChild), getHeight(node.rChild)) + 1; 245 } 246 247 /** 248 * 前序遍历 249 * @param node 250 */ 251 public void frontTreeIterator(AVLNode<E> node){ 252 if(node != null){ 253 System.out.println("key:" + node.key); 254 frontTreeIterator(node.lChild);//遍历当前节点左子树 255 frontTreeIterator(node.rChild);//遍历当前节点右子树 256 } 257 } 258 259 /** 260 * 中序遍历 261 * @param node 262 */ 263 public void middleTreeIterator(AVLNode<E> node){ 264 if(node != null){ 265 middleTreeIterator(node.lChild);//遍历当前节点左子树 266 System.out.println("key:" + node.key); 267 middleTreeIterator(node.rChild);//遍历当前节点右子树 268 } 269 } 270 271 /** 272 * 后序遍历 273 * @param node 274 */ 275 public void backTreeIterator(AVLNode<E> node){ 276 if(node != null){ 277 backTreeIterator(node.lChild);//遍历当前节点左子树 278 backTreeIterator(node.rChild);//遍历当前节点右子树 279 System.out.println("key:" + node.key); 280 } 281 } 282 283}
测试代码，如下：
1public class AVLClient { 2 3 public static void main(String[] args) { 4 //创建一个Integer型的数据结构 5 AVLSolution<Integer> avlTree = new AVLSolution<Integer>(); 6 7 //插入节点 8 System.out.println("========插入元素========"); 9 avlTree.insert(new Integer(100)); 10 avlTree.insert(new Integer(85)); 11 avlTree.insert(new Integer(120)); 12 avlTree.insert(new Integer(60)); 13 avlTree.insert(new Integer(90)); 14 avlTree.insert(new Integer(80)); 15 avlTree.insert(new Integer(130)); 16 System.out.println("========中序遍历元素========"); 17 18 //中序遍历 19 avlTree.middleTreeIterator(avlTree.root); 20 System.out.println("========查找key为100的元素========"); 21 22 //查询节点 23 AVLNode<Integer> searchResult = avlTree.search(120); 24 System.out.println("查找结果：" + searchResult); 25 System.out.println("========删除key为90的元素========"); 26 27 //删除节点 28 avlTree.delete(90); 29 System.out.println("========再次中序遍历元素========"); 30 31 //中序遍历 32 avlTree.middleTreeIterator(avlTree.root); 33 } 34}
输出结果如下：
四、总结
平衡二叉树查找树，俗称AVL树，在查询的时候，操作与普通二叉查找树上的查找操作相同；插入的时候，每一次插入结点操作最多只需要单旋转或双旋转；如果是动态删除，删除之后必须检查从删除结点开始到根结点路径上的所有结点的平衡因子，也就是高度差，如果超过1就需要调整，最多可能需要O（logN）次旋转。
整体上来说，平衡二叉树优于普通二叉查找树！
