[数据结构与算法]平衡二叉树实现

由于程序太长，分成了几部分，后面附上源码。

1 /** 2 * 平衡二叉搜索（排序）树 3 * 4 * 平衡二叉搜索树双称为AVL树，它也是一棵二叉搜索树，是对二叉搜索树的一种改进，或都是具有下列性质的二叉树：它 5 * 的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。 6 * 7 * 平衡因子（Balance Factor,BF）定义为该节点的左子树的深度减去其右子树的深度，则平衡二叉树上所有节点的平 8 * 衡因子只可能是-1、0和1。只要树上有一个节点的平衡因子的绝对值大于1，则该二叉树就是不平衡的了。 9 * 10 * 使用二叉排序树保持平衡的基本思想是：每当在二叉排序树中插入一个节点时，首先检查是否因插入而破坏了平衡，若11 * 是，则找出其中的最小不平衡二叉树，在保持二叉排序树特性的情况下，调整最小不平衡子s树中节点之间的关系，以达12 * 到新的平衡。所谓最小不平衡子树指离插入节点最近且以平衡因子的绝对值大于1的节点作为根的子树。13 * 14 * 对于平衡二叉搜索树，保持树的平衡的基本机制就是旋转。旋转是对树的元素顺序进行调节。旋转的目的是消除由于临15 * 时插入和删除对树的平衡产生的影响。16 * 17 * 有四种旋转：18 * 1)绕某元素左旋转19 *80 ← p9020 */\ /\21 * 60 90 ← r → 80 1 * /\ /\ /23 *85 120 60 85 10024 * /25 * 10026 * 27 * 2)绕某元素右旋转28 *p → 100 8529 */\/\30 *l → 85 120→ 60 10031 * /\\ /\32 * 60 90 80 90 12033 * \34 * 8035 * 36 * 3)绕某元素的左子节点左旋转，接着再绕该元素自己右旋转。此情况下就是 左旋与右旋 的结合，具体操作时可以分37 * 解成这两种操作，只是围绕点不一样而已38 * 39 * 先绕100的左子节点80左旋转，接着再绕100左旋转40 * 41 *左旋 右旋42 * 100→p → 100 → 9043 * /\ /\ /\44 * p → 80 120 l → 90 12080 10045 * /\ //\ \46 * 60 90 ← r80 60 85 12047 *//\48 * 85 60 8549 * 50 * 4)绕某元素的右子节点右旋转，接着再绕该元素自己左旋转。此情况下就是 右旋与左旋 的结合，具体操作时可以分解51 * 成这两种操作，只是围绕点不一样而已52 * 53 * 先绕80的右子节点80右旋转，接着再绕80左旋转54 * 右旋左旋55 *80→80 ← p→ 8556 */\ /\ /\57 * 60 100 ← p 60 85 ← r 80 10058 * /\ \ / /\59 * l → 85 1060 90 12060 * \ /\61 * 90 90 12062 * 63 * 平衡二叉树实现类 AVLTree 中的很多方法与排序二叉树是一新的，详细请参考 BinSearchTree 类中相应方法64 * 65 * AVLTree中的Entry对象与BinSearchTree中的Entry对象是有区别的，所以AVLTree类不能是BinSearchTree的66 * 了类，虽然很多的方法是一样的（如：contains、getEntry、successor、iterator），还有一些方法（add、de67 * leteEntry）只是在操作后增加了节点平衡因子调整动作，但不能直接继承于它。68 * 69 * 二叉搜索树与平衡二叉搜索树没有在Java集合框架中实现，但RED-BLACK树在TreeMap实现过，当然TreeSet也是，70 * 因为它是基于TreeMap实现的，TreeSet对象基本上就是一个忽略了每个元素值部分的TreeMap对象。71 * 72 */

1 package tree.avl; 2 3 import java.util.AbstractSet; 4 import java.util.Iterator; 5 6 /** 7 * 平衡二叉搜索（排序）树 8 * 9 * @author jzj 10 * @data -12-25 11 */ 12 public class AVLTree<E extends Comparable<E>> extends AbstractSet<E> { 13private Entry<E> root;//根节点 14private int size;//树节点个数 15 16private static class Entry<E> { 17 E elem;//数据域 18 Entry<E> parent;//父节点 19 Entry<E> left;//左节点 20 Entry<E> right;//右节点 21 /* 22* 树的平衡因子，等号表示左子树和右子树有同样的高度。如果L，左子树比右子树高1。如果为R，则意味着右 23* 子树比左高1。刚创建时是平衡的，所以为= 24* 50 25* /R\ 26* 20 80 27* /L /R\ 28* 10 70 100 29* = = /=\ 30* 92 103 31* = = 32*/ 33 char balanceFactor = '='; 34 35 //构造函数只有两个参数，左右节点是调用add方法时设置 36 public Entry(E elem, Entry<E> parent) { 37 this.elem = elem; 38 this.parent = parent; 39 } 40} 41 42private class TreeIterator implements Iterator<E> { 43 44 private Entry<E> lastReturned = null; 45 private Entry<E> next; 46 47 TreeIterator() { 48 49 next = root; 50 if (next != null) 51 while (next.left != null) 52 next = next.left; 53 54 } 55 56 public boolean hasNext() { 57 58 return next != null; 59 60 } 61 62 public E next() { 63 64 lastReturned = next; 65 next = successor(next); 66 return lastReturned.elem; 67 68 } 69 70 public void remove() { 71 72 if (lastReturned.left != null && lastReturned != null) 73 next = lastReturned; 74 deleteEntry(lastReturned); 75 lastReturned = null; 76 77 } 78} 79 80/** 81* 左旋转：结果就是将p移到它的左子节点的位置，而p的右子节点被移到该元素原来位置 82* @param p 旋转元素 83*/ 84private void rotateLeft(Entry<E> p) { 85 /* 86 * 围绕50左旋转: 87 *p → 50 90 88 *\ /\ 89 * r → 90→ 50 100 90 *\ 91 *100 92 * 93 * 围绕80左旋转:r的左子树变成p的右子树。因为位于r的左子树上的任意一个元素值大于p且小于r，所以r的左子 94 * 树可以成为p的右子树这是没有问题的。其实上面也发生了同样的现象，只是r的左子树为空罢了 95 * p → 80 90 96 */\ /\ 97 *60 90 ← r→80 120 98 * /\/\ / 99 *85 120 60 85 100100 */101 * 100102 * 103 * 围绕80在更大范围内旋转：元素不是围绕树的根旋转。旋转前后的树都是二叉搜索树。且被旋转元素80上的所104 * 有元素在旋转中不移动（50、30、20、40这四个元素还是原来位置）105 * 5050106 * / \ / \107 *30 80 ← p 30 90108 */\ /\ /\ / \109 * 20 40 60 90 ← r→20 40 80 10 * /\ /\ /111 * 85 120 60 85 100112 * /113 * 100114 * 115 * 节点数据结构:116 * +------------------+117 * | elem | p | l | r |118 * +------------------+119 * 120 * +------------------+121 * | 50 |NULL|NULL| r |122 * +------------------+123 * ↖⑥ ↘④124 * +---------------+125 * |80| p | l | r | ← p 126 * +---------------+127 * ↗ ↙↖③ ↘①128 * +----------------+ +---------------+129 * |60| p |NULL|NULL| |90| p | l | r | ← r130 * +----------------+ +---------------+131 * ↗② ↙⑤ ↖↘ 132 * +----------------+ +---------------+133 * |85| p |NULL|NULL| |90| p | l |NULL|134 * +----------------+ +---------------+135 * ↗↙ 136 * +-----------------+137 * |100| p |NULL|NULL|138 * +-----------------+139 */140 141 Entry<E> r = p.right;//旋转元素的右子节点142 //把旋转元素的右子节点的左子节点接到旋转元素的右子树143 p.right = r.left;//①144 //如果旋转元素的右子节点存在左子节点的话，同时修改该节点的父节指针指向145 if (r.left != null) {146 //把旋转元素的右子节点的左子节点的父设置成旋转元素147 r.left.parent = p;//②148 }149 //将旋转元素的右子节点的父设置成旋转元素的父，这里有可以p为根节点，那么旋转后p就成根节点150 r.parent = p.parent;//③151 152 //如果旋转元素为根元素，则旋转后，旋转元素的右子节点r将成为根节点153 if (p.parent == null) {154 root = r;155 }//否则p不是根节点，如果p是他父节点的左节点时156 else if (p.parent.left == p) {157 //让p的父节点的左指针指向r158 p.parent.left = r;159 }//否则如果p是他父节点的右节点时160 else {161 //让p的父节点的右指针指向r162 p.parent.right = r;//④163 }164 //让旋转元素的左节点指向旋转元素p165 r.left = p;//⑤166 //让旋转元素的父节点指向旋转元素右节点r167 p.parent = r;//⑥168}169 170/**171* 右旋转：结果就是将p移到它的右子节点的位置，而p的左子节点被移到该元素原来位置172* 与左旋转是完全对称的，将左旋转中的lef与rigth互换即可得到，这里就不详细解释了173* @param p 旋转元素174*/175private void rotateRight(Entry<E> p) {176 177 /*178 * 围绕100右旋转:179 * p → 100 90180 * //\181 * l → 90→ 50 100182 */183 * 50184 * 185 * 围绕80右旋转:l的右子树变成p的左子树。因为位于l的右子树上的任意一个元素值小于p且小于l，所以l的右186 * 子树可以成为p的左子树这是没有问题的。其实上面也发生了同样的现象，只是l的右子树为空罢了187 * 188 * p → 80 60189 */\ /\ 190 * l → 60 90 →50 80191 */\ \ /\192 * 50 7055 70 90 193 *\ 194 *55195 */196 197 Entry<E> l = p.left;198 p.left = l.right;199 if (l.right != null) {200 l.right.parent = p;201 }202 l.parent = p.parent;203 204 if (p.parent == null) {205 root = l;206 } else if (p.parent.right == p) {207 p.parent.right = l;208 } else {209 p.parent.left = l;210 }211 l.right = p;212 p.parent = l;213}214 215/**216* AVLTree类的add方法类似于BinSerrchTree类的add方法，但是沿着根向下前进到插入点时，需记录这样一个被插217* 入Entry对象最近的祖先：该祖先的平衡因子balanceFactor值是L或R(即不歼)，且让ancestor指向这个祖先节218* 点，该祖先节有什么用呢，从ancestor的子开始到新增节点路径上的所有祖先节点都是平衡，这些祖先节点会因为219* 新增节点而变得不平衡了，需要重新调整平衡因子，这个分界点在调整平衡因子时非常有用220* 221* @param elem 要新增元素的数据域222* @return223*/224public boolean add(E elem) {225 //如果树为空，则直接插入226 if (root == null) {227 root = new Entry<E>(elem, null);228 size++;229 return true;230 } else {231 Entry<E> tmp = root;//新增节点的父节点，从根节点下面开始找插入点232 Entry<E> ancestor = null;//平衡因子不为 = 的最近祖先节点233 int comp; //比较结果234 while (true) {//死循环，直接找到插入点退出循环235 comp = pareTo(tmp.elem);236 //如果已存在该元素，则直接返回失败237 if (comp == 0) {238 return false;239 }240 241 //记录不平衡的祖先节点242 if (tmp.balanceFactor != '=') {243 //如果哪个祖先节点不平衡，则记录，当循环完后，ancestor指向的就是最近一个244 //不平衡的祖先节点245 ancestor = tmp;246 }247 248 //如果小于当前比较节点，则在其左边插入249 if (comp < 0) {250 251 //如果左子树不为空，继续循环在左边找插入点252 if (tmp.left != null) {253tmp = tmp.left;254 } else {//否则插入255tmp.left = new Entry<E>(elem, tmp);256//插入后要进行平衡调整257fixAfterInsertion(ancestor, tmp.left);258size++;259return true;260 }261 } else {//在右边插入262 263 //如果右子树不为空，继续循环在右边找插入点264 if (tmp.right != null) {265tmp = tmp.right;266 } else {//否则插入267tmp.right = new Entry<E>(elem, tmp);268//插入后要进行平衡调整269fixAfterInsertion(ancestor, tmp.right);270size++;271return true;272 }273 }274 275 }276 }277}278 279/**280* 当新增节点后，会改变某些节点的平衡因子，所以添加节点后需重新调整平衡因子281* 282* 根据前人们的分析与研究，可分为6种情况283* 284* @param ancestor 新增元素的最近一个不平衡的祖先节点285* @param inserted 新增元素286*/287protected void fixAfterInsertion(Entry<E> ancestor, Entry<E> inserted) {288 E elem = inserted.elem;289 290 if (ancestor == null) {291 /*292 * 情况1：ancestor的值为null，即被插入Entry对象的每个祖先的平衡因子都是 =，此时新增节点后293 * ，树的高度不会发生变化，所以不需要旋转，我们要作的就是调整从根节点到插入节点的路径上的所有294 * 节点的平衡因子罢了295 * 296 * 新增55后调整297 * 50 → 50298 * /=\ /R\299 * 25 70 25 70300 */=\ /=\ /=\ /L\301 * 15 30 60 9015 30 60 90302 * = = = == = /L =303 *55304 *=305 */306 //根节点的平衡因子我们单独拿出来调整，因为adjustPath的参数好比是一个开区间，它不包括两头参数307 //本身，而是从nserted.paraent开始到to的子节点为止，所以需单独调整，其他分支也一样308 if (pareTo(root.elem) < 0) {309 root.balanceFactor = 'L';310 } else {311 root.balanceFactor = 'R';312 }313 //再调用adjustPath方法调整新增节点的父节点到root的某子节点路径上的所有祖先节点的314 //平衡因子315 adjustPath(root, inserted);316 } else if ((ancestor.balanceFactor == 'L' && pareTo(ancestor.elem) > 0)317 || (ancestor.balanceFactor == 'R' && pareTo(ancestor.elem) < 0)) {318 /*319 * 情况2：320 * ancestor.balanceFactor的值为 L，且在ancestor对象的右子树插入，或ancestor.balanceFac321 * tor的值为 R，且在ancestor对象的左子树插入，这两插入方式都不会引起树的高度发生变化，所以我们322 * 也不需要旋转，直接调整平衡因子即可323 * 新增55后调整324 * ancestor → 50 → 50325 * /L\/=\326 *25 70 25 70327 * /R\ /=\ /R\ /L\328 * 15 30 60 90 15 30 60 90329 * /L/L /L330 *2828 55331 * 新增28后调整332 * ancestor → 50 → 50333 * /R\/=\334 *25 70 25 70335 * /=\ /L\ /R\ /L\336 * 15 30 60 90 15 30 60 90337 * /L /L /L338 * 55 28 55339 */340 //先设置ancestor的平衡因子为 平衡341 ancestor.balanceFactor = '=';342 //然后按照一般策略对inserted与ancestor间的元素进行调整343 adjustPath(ancestor, inserted);344 } else if (ancestor.balanceFactor == 'R'345 && pareTo(ancestor.right.elem) > 0) {346 /*347 * 情况3：348 * ancestor.balanceFactor的值为 R，并且被插入的Entry位于ancestor的右子树的右子树上， 此349 * 种情况下会引起树的不平衡，所以先需绕ancestor进行旋转，再进行平衡因子的调整350 *351 * 新增93先调整因子再绕70左旋352 * → 50→ 50353 * /R\ /R\354 *25 70 ← ancestor25 90355 * /L /R\/L /=\356 * 15 60 90 15 70 98357 * == /=\ = /=\ /L358 *80 98 60 80 93359 *= /= = = =360 * 93361 * =362 */363 ancestor.balanceFactor = '=';364 //围绕ancestor执行一次左旋365 rotateLeft(ancestor);366 //再调整ancestor.paraent（90）到新增节点路径上祖先节点平衡367 adjustPath(ancestor.parent, inserted);368 } else if (ancestor.balanceFactor == 'L'369 && pareTo(ancestor.left.elem) < 0) {370 /*371 * 情况4：372 * ancestor.balanceFactor的值为 L，并且被插入的Entry位于ancestor的左子树的左子树上，373 * 此种情况下会引起树的不平衡，所以先需绕ancestor进行旋转，再进行平衡因子的调整374 * 375 * 新增13先调整因子再绕50右旋376 * → 50 ← ancestor → 20377 * /L\ /=\378 *20 70 10 50379 * /=\ /=\/R\ /=\380 * 10 30 60 90 5 15 30 70381 * /=\ /=\= == /L /=\ /=\382 *5 15 25 35 13 25 35 60 90383 *= /= = == = = = = 384 * 13 385 * = 386 */387 ancestor.balanceFactor = '=';388 //围绕ancestor执行一次右旋389 rotateRight(ancestor);390 //再调整ancestor.paraent（20）到新增节点路径上祖先节点平衡391 adjustPath(ancestor.parent, inserted);392 } else if (ancestor.balanceFactor == 'L'393 && pareTo(ancestor.left.elem) > 0) {394 /*395 * 情况5：396 * ancestor.balanceFactor的值为 L，并且被插入的Entry位于ancestor的左子树的右子树上。此397 * 种情况也会导致树不平衡，此种与第6种一样都需要执行两次旋转（执行一次绕ancestor的左子节点左398 * 旋，接着执行一次绕ancestor执行一次右旋）后，树才平衡，最后还需调用 左-右旋 专有方法进行平衡399 * 因子的调整400 */401 rotateLeft(ancestor.left);402 rotateRight(ancestor);403 //旋转后调用 左-右旋 专有方法进行平衡因子的调整404 adjustLeftRigth(ancestor, inserted);405 } else if (ancestor.balanceFactor == 'R'406 && pareTo(ancestor.right.elem) < 0) {407 408 /*409 * 情况6：410 * ancestor.balanceFactor的值为 R，并且被插入的Entry位于ancestor的右子树的 左子树上，此411 * 种情况也会导致树不平衡，此种与第5种一样都需要执行两次旋转（执行一次绕ancestor的右子节点右旋412 * ，接着执行一次绕ancestor执行一次左旋）后，树才平衡，最后还需调用 右-左旋 专有方法进行平衡因413 * 子的调整414 */415 rotateRight(ancestor.right);416 rotateLeft(ancestor);417 //旋转后调用 右-左旋 专有方法进行平衡因子的调整418 adjustRigthLeft(ancestor, inserted);419 }420}

1/** 2* 调整指定路径上的节点的平衡因子 3* 4* 注，指定的路径上的所有节点一定是平衡的，因此如果被插入元素小于某个祖先节点， 5* 则这个祖先节点新的平衡因子是 L，反之为 R。 6* 7* @param inserted 从哪里元素开始向上调整，但不包括该，即从父开始） 8* @param to 直到哪个元素结束,但不包括该元素，一般传进来的为ancestor 9*/ 10protected void adjustPath(Entry<E> to, Entry<E> inserted) { 11 E elem = inserted.elem; 12 Entry<E> tmp = inserted.parent; 13 //从新增节点的父节点开始向上回溯调整，直到结尾节点to止 14 while (tmp != to) { 15 /* 16 * 插入30，则在25右边插入，这样父节点平衡会被打破，右子树就会比左子树高1，所以平衡因子为R；祖 17 * 先节点50的平衡因子也被打破，因为在50的左子树上插入的，所以对50来说，左子树会比右子树高1，所 18 * 以其平衡因子为L 19 * 50 50 20 * /=\ 插入30 /L\ 21 * 25 70 → 25 70 22 * = = R\ = 23 * 30 24 * = 25 */ 26 //如果新增元素比祖先节点小，则是在祖先节点的左边插入，则自然该祖先的左比右子树会高1 27 if (pareTo(tmp.elem) < 0) { 28 29 tmp.balanceFactor = 'L'; 30 } else { 31 //否则会插到右边，那么祖先节点的右就会比左子树高1 32 tmp.balanceFactor = 'R'; 33 } 34 tmp = tmp.parent;//再调整祖先的祖先 35 } 36} 37 38/** 39* 进行 左-右旋转 后平衡因子调整 40* 分三种情况 41* @param ancestor 42* @param inserted 43*/ 44protected void adjustLeftRigth(Entry<E> ancestor, Entry<E> inserted) { 45 E elem = inserted.elem; 46 if (ancestor.parent == inserted) { 47 /* 48 * 第1种，新增的节点在旋转完成后为ancestor父节点情况： 49 * 50 * 新增40绕30左旋绕50右旋 51 * →50 ← ancestor → 50 → 52 */L/L53 * 3040 54 * =\ /= 55 *40 30 56 *= = 57 * 58 *调整平衡因子 59 *40 → 40 60 */=\ /=\ 61 * 30 50 30 50 62 * = L = = 63 *64 * 注，这里的 左-右旋 是在fixAfterInsertion方法中的第5种情况中完成的，在这里只是平衡因子的 65 * 调整，图是为了好说明问题而放在这个方法中的，下面的两个分支也是一样 66 */ 67 ancestor.balanceFactor = '='; 68 } else if (pareTo(ancestor.parent.elem) < 0) { 69 /* 70 * 第2种，新增的节点在旋转完成后为不为ancestor父节点，且新增节点比旋转后ancestor的父节点要小 71 * 的情况 72 * 73 * 由于插入元素(35)比旋转后ancestor(50)的父节点(40)要小， 所以新增节点会在其左子树中 74 * 75 * 新增35绕20左旋 76 * →50 ← ancestor → 50 77 */L\/L\ 78 * 20 90 40 90 79 * /=\ /=\/=\ /=\ 80 *10 40 70 10020 45 70 100 81 * /=\ /=\= = /=\82 * 5 15 30 4510 30 83 * = = =\ =/=\ =\ 84 *355 15 35 85 *= = = = 86 * 87 * 绕50右旋 调整平衡因子 88 *→ 40→40 89 * /=\ /=\ 90 * 20 50 20 50 91 * /=\ /L\/=\ /R\ 92 *10 30 45 90 10 30 45 90 93 * /=\ =\ /=\ /=\ R\ /=\ 94 * 5 15 35 70 100 5 15 35 70 100 95 * = = = = = = = = = = 96 * 97 */ 98 ancestor.balanceFactor = 'R'; 99 //调整ancestor兄弟节点到插入点路径上节点平衡因子100 adjustPath(ancestor.parent.left, inserted);101 } else {102 /*103 * 第2种，新增的节点在旋转完成后为不为ancestor父节点，且新增节点比旋转后ancestor的父节点要大的104 * 情况105 * 106 * 由于插入元素(42)比旋转后ancestor(50)的父节点(40)要大，所以新增节点会在其右子树中107 * 108 * 新增42 绕20左旋109 * →50 ← ancestor→50110 */L\/L\111 * 20 90 40 90112 * /=\ /=\/=\ /=\113 *10 40 70 10020 45 70 100114 * /=\ /=\= = /=\ /=115 * 5 15 30 45 10 30 42 116 * = = = /= /=\= =117 * 42 5 15 118 * == = 119 *120 * 绕50右旋 调整平衡因子121 * →40 →40122 * /=\ /=\123 * 20 50 20 50124 * /=\ /L\/L\ /=\125 *10 30 45 90 10 30 45 90126 * /=\ /= /=\ /=\ /L /=\127 * 5 15 42 70 1005 15 42 70 100128 * = = = = = = = = = =129 *130 */131 ancestor.parent.left.balanceFactor = 'L';132 133 ancestor.balanceFactor = '=';134 //调整ancestor节点到插入点路径上节点平衡因子135 adjustPath(ancestor, inserted);136 }137}138 139/**140* 进行 右-左旋转 后平衡因子调整141* 142* 与adjustLeftRigth方法一样，也有三种情况，这两个方法是对称的143* @param ancestor144* @param inserted145*/146protected void adjustRigthLeft(Entry<E> ancestor, Entry<E> inserted) {147 E elem = inserted.elem;148 if (ancestor.parent == inserted) {149 /*150 * 第1种，新增的节点在旋转完成后为ancestor父节点情况： 151 * 152 * 新增40绕50右旋绕30左旋 153 * → 30 ← ancestor → 30→154 * R\ R\ 155 * 50 40 156 * /==\157 *40 50158 *= =159 *160 *40 调整平衡因子 40161 */=\ → /=\162 * 30 50 30 50163 * R = = =164 * 165 * 注，这里的 右-左旋 是在fixAfterInsertion方法中的第6种情况中完成的，这里只是 平衡因子的调166 * 整，图是为了好说明问题而放在这个方法中的，下面的两个分支也是一样167 */168 ancestor.balanceFactor = '=';169 } else if (pareTo(ancestor.parent.elem) > 0) {170 /*171 * 第2种，新增的节点在旋转完成后为不为ancestor父节点，且新增节点比旋转后172 * ancestor的父节点要大的情况173 * 174 * 由于插入元素(73)比旋转后ancestor(50)的父节点(70)要大， 所以新增节点会175 * 在其右子树中176 * 177 * 新增73绕90右旋178 * → 50 ← ancestor → 50179 */R\/R\180 * 20 90 20 70181 * /=\ /=\/=\ /=\182 *10 40 70 9510 40 65 90183 *= = /=\ /=\= = = /=\ 184 *65 75 93 97 75 95185 *= /= = = /= /=\186 * 73 73 93 97187 * = 188 *189 * 绕50左旋 调整平衡因子190 * →70→70191 * /=\ /=\192 * 50 90 50 90193 * /R\ /=\/L\ /=\194 *20 65 75 95 20 65 75 95195 * /=\ = /= /=\ /=\ = /L /=\196 * 10 40 73 93 97 10 40 73 93 97197 * = = = = = = = = = =198 *199 */200 ancestor.balanceFactor = 'L';201 adjustPath(ancestor.parent.right, inserted);202 } else {203 /*204 * 第2种，新增的节点在旋转完成后为不为ancestor父节点，且新增节点比旋转后ancestor的父节点要小205 * 的情况206 * 207 * 由于插入元素(73)比旋转后ancestor(50)的父节点(70)要大， 所以新增节点会在其右子树中208 * 209 * 新增63绕90右旋210 * → 50 ← ancestor → 50211 */R\/R\212 * 20 90 20 70213 * /=\ /=\/=\ /=\214 *10 40 70 9510 40 65 90215 *= = /=\ /=\= = /= /=\ 216 *65 75 93 97 63 75 95217 */= = = == = /=\218 * 63 93 97219 * == =220 *221 * 绕50左旋 调整平衡因子222 * →70→70223 * /=\ /=\224 * 50 90 50 90225 * /R\ /=\/=\ /R\226 * 20 65 75 95 20 65 75 95227 * /=\ /= = /=\ /=\ /L /=\228 * 10 40 63 93 97 10 40 63 93 97229 * = = = = == = = = = 230 */231 ancestor.parent.right.balanceFactor = 'R';232 ancestor.balanceFactor = '=';233 adjustPath(ancestor, inserted);234 }235}236 237/**238* 删除指定节点239* 240* @param elem241* @return boolean242*/243public boolean remove(E elem) {244 Entry<E> e = getEntry(elem);245 if (e == null)246 return false;247 deleteEntry(e);248 return true;249}250 251private Entry<E> getEntry(E e) {252 Entry<E> tmp = root;253 int c;254 while (tmp != null) {255 c = pareTo(tmp.elem);256 if (c == 0) {257 return tmp;258 } else if (c < 0) {259 tmp = tmp.left;260 } else {261 tmp = tmp.right;262 }263 }264 return null;265}266 267private void deleteEntry(Entry<E> p) {268 if (p.left != null && p.right != null) {269 270 Entry<E> s = successor(p);271 272 p.elem = s.elem;273 274 p = s;275 }276 277 if (p.left == null && p.right == null) {278 279 if (p.parent == null) {280 root = null;281 } else if (p == p.parent.left) {282 p.parent.left = null;283 } else {284 p.parent.right = null;285 }286 287 } else {288 289 Entry<E> rep;290 if (p.left != null) {291 rep = p.left;292 } else {293 rep = p.right;294 }295 296 rep.parent = p.parent;297 298 if (p.parent == null) {299 root = rep;300 } else if (p == p.parent.left) {301 p.parent.left = rep;302 } else {303 p.parent.right = rep;304 }305 306 }307 fixAfterDeletion(p.elem, p.parent);308 309 p.parent = null;310 p.left = null;311 p.right = null;312 313 size--;314}315 316/**317* 查找指定节点的中序遍历序列的直接后继节点，此方法的实现与二叉搜索树类（BinSearchTree.java）的此方法是318* 一样的，具体的思路请参考二叉搜索树类中的相应方法319* 320* @param e 需要查找哪个节点的直接后继节点321* @return Entry<E> 直接后继节点322*/323private Entry<E> successor(Entry<E> e) {324 if (e == null) {325 return null;326 }//如果待找的节点有右子树，则在右子树上查找327 else if (e.right != null) {328 //默认后继节点为右子节点（如果右子节点没有左子树时即为该节点）329 Entry<E> p = e.right;330 while (p.left != null) {331 //注，如果右子节点的左子树不为空，则在左子树中查找，且后面找时要一直向左拐332 p = p.left;333 }334 return p;335 }//如果待查节点没有右子树，则要在祖宗节点中查找后继节点 336 else {337 338 //默认后继节点为父节点（如果待查节点为父节点的左子树，则后继为父节点）339 Entry<E> p = e.parent;340 Entry<E> c = e;//当前节点，如果其父不为后继，则下次指向父节点341 //如果待查节点为父节点的右节点时，继续向上找，一直要找到c为左子节点，则p才是后继342 while (p != null && c == p.right) {343 c = p;344 p = p.parent;345 }346 return p;347 }348}

1/** 2* 删除节点后平衡调整实现 3* 4* @param elem 被删除节点的数据域 5* @param ancestor 被删除节点的祖先节点，从父节点向上迭代 6*/ 7protected void fixAfterDeletion(E elem, Entry<E> ancestor) { 8 9 boolean heightHasDecreased = true;//树的高度是否还需要减小 10 11 /* 12* 1、如果删除的是根节点，则ancestor为空，此时不需调整了，直接退出 13* 2、如果删除的不是根节点，且根节点都已调整，则退出 14* 3、如果删除的不是根节点，且树的高度不需再减小（heightHasDecreased为false），退出 15*/ 16 while (ancestor != null && heightHasDecreased) { 17 18 int comp = pareTo(ancestor.elem); 19 20 /* 21 * 当要删除的节点有左右子树时，comp就会等于0，比如下面要删除33这个节点，删除方法deleteEntry 22 * 会用36替换掉33节点中的数据的elem，删除后会调用fixAfterDeletion(p.elem, p.parent)方 23 * 法来调整平衡因子，p又是指向的36，所以p.elem与p.parent.elem是相等的，都是36 24 * 25 * 82 26 * /L\ 27 * 42 95 28 * /=\ R\ 29 * 33 48 96 30 */=\ /=\ 31 *29 36 43 75 32 */ 33 34 //从ancestor的右子树中删除节点 35 if (comp >= 0) { 36 // ancestor 的平衡因子为 '=' 37 if (ancestor.balanceFactor == '=') { 38 39 /* 删除15 调整因子 40 *20 → 20 41 */L\ /L\ 42 * → 10 5010 50 43 */=\ /L 44 * 5 155 45 */ 46 ancestor.balanceFactor = 'L'; 47 heightHasDecreased = false; 48 49 } // ancestor 的平衡因子为 'R' 50 else if (ancestor.balanceFactor == 'R') { 51 /* 删除15 调整因子下次循环调整20的因子 52 *20 → → 20 ← ancestor → ... 53 */L\ /L\ 54 * → 10 5010 50 55 */R\ R\/=\ R\ 56 * 5 15 60 5 18 60 57 * R\ 58 * 18 59 */ 60 ancestor.balanceFactor = '='; 61 ancestor = ancestor.parent; 62 63 }// ancestor 的平衡因子为 'L' 64 else if (ancestor.balanceFactor == 'L') { 65 // ancestor 的左子节点平衡因子为 '=' 66 if (ancestor.left.balanceFactor == '=') { 67 68/* 删除60 调整因子 绕50右旋 69*20 →→ 20 → 20 70*/R\ / \ /R\ 71*10 50 ← ancestor 10 50 ← 10 45 72*/L /L\ / /L\ /L /R\ 73* 5 45 60 5 45 60 5 35 50 ← 74*/=\ /R\ /L 75*35 48 35 48 48 76*/ 77ancestor.left.balanceFactor = 'R'; 78ancestor.balanceFactor = 'L'; 79rotateRight(ancestor); 80heightHasDecreased = false; 81 82 }// ancestor 的左子节点平衡因子为 'L' 83 else if (ancestor.left.balanceFactor == 'L') { 84 85/* 删除60 调整因子 绕50右旋 下次循环调整20的因子 86*20 →→ 20→ 20 ← p→ ... 87*/R\ / \ /R\ 88*10 50 ← ancestor 10 50 ←10 45 89*/L /L\ / /=\/L /=\ 90* 5 45 60 5 45 60 5 35 50 ← ancestor 91*/L/= = 92*3535 93*/ 94Entry<E> p = ancestor.parent; 95ancestor.balanceFactor = '='; 96ancestor.left.balanceFactor = '='; 97rotateRight(ancestor); 98ancestor = p; 99 100 } // ancestor 的左子节点平衡因子为 'R'101 else if (ancestor.left.balanceFactor == 'R') {102 103Entry<E> p = ancestor.parent;104 105// ancestor 的左子节点的右子节点的平衡因子为 'L'106if (ancestor.left.right.balanceFactor == 'L') {107 108 /* 删除60 调整因子109*20 → 20 110*/R\/ \111* 10 50 ← ancestor 10 50 ← ancestor112* /L\ /L\/ \ /R\113* 5 12 45 60 5 12 45 70114* /L /R\ R\//=\ 115* 342 48 70 342 48 116*/L /= 117* 46 46118* 119* 绕45左旋 绕50右旋 下次循环调整20的因子120* →20 → 20 ← p→ ...121*/R\/R\122* 10 50 ←10 48123* /L\ /R\/L\ /=\124* 5 12 48 70 5 12 45 50 ← ancestor125* /L /= /L /=\ R\126*3 45 342 46 70127*/=\128* 42 46129*/130 ancestor.balanceFactor = 'R';131 ancestor.left.balanceFactor = '=';132 133}// ancestor 的左子节点的右子节点的平衡因子为 'R' 134else if (ancestor.left.right.balanceFactor == 'R') {135 136 /* 删除60 调整因子137*20 → 20 138*/R\/ \139* 10 50 ← ancestor 10 50 ← 140* /L\ /L\/ \ /=\141* 5 12 45 60 5 12 45 70142* /L /R\ R\//L\ 143* 342 48 70 342 48 144* R\ =\ 145* 49 49146* 147* 绕45左旋 绕50右旋 下次循环调整20的因子148* →20 → 20 ← p→ ...149*/R\/R\150* 10 50 ←10 48151* /L\ /=\/L\ /=\152* 5 12 48 70 5 12 45 50 ← ancestor153* /L /=\/L /L /=\154*3 45 49 342 49 70155*/L156* 42 157*/158 ancestor.balanceFactor = '=';159 ancestor.left.balanceFactor = 'L';160 161}// ancestor 的左子节点的右子节点的平衡因子为 '=' 162else {163 /* 删除60 调整因子164*20 → 20 165*/R\/ \166* 10 50 ← ancestor 10 50 ← 167* /L\ /L\/ \ /=\168* 5 12 45 60 5 12 45 70169* /L /R\ R\//=\ 170* 342 48 70 342 48 171*/=\/=\ 172* 46 49 46 49173* 174* 绕45左旋 绕50右旋 下次循环调整20的因子175* →20 → 20 ← p→ ...176*/R\/R\177* 10 50 ←10 48178* /L\ /=\/L\ /=\179* 5 12 48 70 5 12 45 50 ← ancestor180* /L /=\/L /=\ /=\181*3 45 49 342 46 49 70182*/=\183* 42 46184*/185 ancestor.balanceFactor = '=';186 ancestor.left.balanceFactor = '=';187 188}189ancestor.left.right.balanceFactor = '=';190rotateLeft(ancestor.left);191rotateRight(ancestor);192ancestor = p;193 }194 }195 196 }197 //从ancestor的左子树中删除节点,与上面是对称的198 else if (comp < 0) {199 200 if (ancestor.balanceFactor == '=') {201 202 ancestor.balanceFactor = 'R';203 heightHasDecreased = false;204 } else if (ancestor.balanceFactor == 'L') {205 206 ancestor.balanceFactor = '=';207 ancestor = ancestor.parent;208 209 } else if (ancestor.balanceFactor == 'R') {210 211 if (ancestor.right.balanceFactor == '=') {212 213ancestor.balanceFactor = 'R';214ancestor.right.balanceFactor = 'L';215rotateLeft(ancestor);216heightHasDecreased = false;217 218 } else if (ancestor.right.balanceFactor == 'R') {219 220Entry<E> p = ancestor.parent;221ancestor.balanceFactor = '=';222ancestor.right.balanceFactor = '=';223rotateLeft(ancestor);224ancestor = p;225 226 } else if (ancestor.right.balanceFactor == 'L') {227 228Entry<E> p = ancestor.parent;229if (ancestor.right.left.balanceFactor == 'R') {230 231 ancestor.balanceFactor = 'L';232 ancestor.right.balanceFactor = '=';233 234} else if (ancestor.right.left.balanceFactor == 'L') {235 236 ancestor.balanceFactor = '=';237 ancestor.right.balanceFactor = 'R';238 239} else {240 241 ancestor.balanceFactor = '=';242 ancestor.right.balanceFactor = '=';243 244}245ancestor.right.left.balanceFactor = '=';246rotateRight(ancestor.right);247rotateLeft(ancestor);248ancestor = p;249 250 }251 }252 }253 }254}255 256public boolean contains(E o) {257 258 Entry<E> e = root;259 260 int comp;261 262 while (e != null) {263 264 comp = pareTo(e.elem);265 if (comp == 0)266 return true;267 else if (comp < 0)268 e = e.left;269 else270 e = e.right;271 272 }273 return false;274}275 276//验证树是否是平衡二叉树277public boolean isAVL() {278 279 return checkAVL(root);280 281}282 283/**284* 验证指定的树是否是平衡二叉树285* @param p286* @return287*/288public static <E extends Comparable<E>> boolean checkAVL(Entry<E> p) {289 290 if (p == null)291 return true;292 //左子树与右子树绝对值不能超过 1，并且左右子树也是平衡二叉树293 return (Math.abs(h(p.left) - h(p.right)) <= 1 && checkAVL(p.left) && checkAVL(p.right));294 295}296 297/**298* 求指定节点的高度299* @param <E>300* @param p301* @return302*/303protected static <E extends Comparable<E>> int h(Entry<E> p) {304 305 if (p == null)306 return -1;307 return 1 + Math.max(h(p.left), h(p.right));308}309 310/**311* 树的高度312* @return313*/314public int height() {315 316 return h(root);317 318}319 320//树的高度非递归求法321public int heightIter() {322 323 int height = -1;324 for (Entry<E> temp = root; temp != null; height++)325 if (temp.balanceFactor == 'L')326 temp = temp.left;327 else328 temp = temp.right;329 return height;330}331 332@Override333public Iterator<E> iterator() {334 return new TreeIterator();335}336 337@Override338public int size() {339 return size;340}341 }

测试：

1 package tree.avl; 2 3 import java.util.Iterator; 4 import java.util.Random; 5 6 public class AVLTreeTest { 7public static void main(String[] args) { 8 AVLTree myTree = new AVLTree(); 9 Random random = new Random();10 System.out.print("随机产生的节点为：");11 int num = 0;12 //直到树的节点数为n止13 while (myTree.size() < 10) {14 num = new Integer(random.nextInt(100));15 myTree.add(num);16 System.out.print(num + " ");17 }18 System.out.println("");19 if (myTree.isAVL()) {20 System.out.println("这棵平衡二叉树的总节点数：" + myTree.size());21 System.out.println("这棵平衡二叉树的高度是：" + myTree.height());22 System.out.println("在树中查找 " + num + " 节点:"23 + myTree.contains(new Integer(num)));24 System.out.println("在树中查找 100 节点:" + myTree.contains(new Integer(100)));25 System.out.print("中序遍历：");26 Iterator itr = myTree.iterator();27 while (itr.hasNext()) {28 System.out.print(itr.next() + " ");29 }30 System.out.println("");31 32 myTree.remove(num);33 System.out.print("删除节点 " + num + " 后遍历：");34 itr = myTree.iterator();35 while (itr.hasNext()) {36 System.out.print(itr.next() + " ");37 }38 System.out.println("");39 40 System.out.println("使用迭代器删除所有节点");41 itr = myTree.iterator();42 while (itr.hasNext()) {43 itr.next();44 itr.remove();45 }46 System.out.println("删除后树的总节点数：" + myTree.size());47 } else {48 System.out.println("failure");49 }50}51 }