怎么理解并掌握Java的AVL树

这篇文章主要介绍“怎么理解并掌握Java的AVL树”，在日常操作中，相信很多人在怎么理解并掌握Java的AVL树问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”怎么理解并掌握Java的AVL树”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！

一、摘要

在上篇文章，我们详细的介绍了二叉树的算法以及代码实践，我们知道不同的二叉树形态结构，对查询效率也会有很大的影响，尤其是当树的形态结构变成一个链条结构的时候，查询最后一个元素的效率极底，如何解决这个问题呢?

关键在于如何最大限度的减小树的深度，从而提高查询效率，正是基于这一点，平衡二叉查找树出现了!

平衡二叉查找树，算法由Adel'son-Vel'skii和 Landis两位大神发明，同时也俗称AVL 树，来自两位大神的姓名缩写，特性如下：

• 它的左子树和右子树都是平衡二叉树;

• 且它的左子树和右子树的深度之差的绝对值(平衡因子 ) 不超过1;

简单的说，就是为了保证平衡，当前节点的左子树、右子树的高度差不超过1!

废话也不多说了，直奔主题，算法思路如下!

二、算法思路

平衡二叉查找树的查找思路，与二叉树是一样，每次查询的时候对半分，只查询一部分，以达到提供效率的目的，插入、删除也一样，最大的不同点：每次插入或者删除之后，需要计算节点高度，然后按需进行调整!

如何调整呢?主要方法有：左旋转、右旋转!

下面我们分别来分析一下插入、删除的场景调整。

2.1、插入场景

我们来分析一下插入的场景，如下：

场景一

当我们在40的左边或者右边插入的时候，也就是50的左边，只需绕80进行右旋转，即可达到树高度差不超过1!

场景二

当我们在60的左边或者右边插入的时候，也就是50的右边，需要进行两次旋转，先会绕50左旋转一次，再绕80右旋转一次，即可达到树高度差不超过1!

场景三

当我们在120的左边或者右边插入的时候，也就是90的右边，只需绕80进行左旋转，即可达到树高度差不超过1!

场景四

当我们在85的左边或者右边插入的时候，也就是90的左边，需要进行两次旋转，先会绕90右旋转一次，再绕80左旋转一次，即可达到树高度差不超过1!

总结

对于插入这种操作，总共其实只有这四种类型的插入，即：单次左旋转、单次右旋转、左旋转-右旋转、右旋转-左旋转，总结如下：

• 当插入节点位于需要旋转节点的左节点的左子树时，只需右旋转;

• 当插入节点位于需要旋转节点的左节点的右子树时，需要左旋转-右旋转;

• 当插入节点位于需要旋转节点的右节点的右子树时，只需左旋转;

• 当插入节点位于需要旋转节点的右节点的左子树时，需要右旋转-左旋转;

2.2、删除场景

接下来，我们分析一下删除场景!

其实，删除场景跟二叉树的删除思路是一样的，不同的是需要调整，删除的节点所在树，需要层层判断节点的高度差是否大于1，如果大于1，就进行左旋转或者右旋转!

场景一

当删除的节点，只有左子树时，直接将左子树转移到上层即可!

场景二

当删除的节点，只有右子树时，直接将右子树转移到上层即可!

场景三

当删除的节点，有左、右子树时，因为当前节点的左子树的最末端的右子树或者当前节点的右子树的最末端的左子树，最接近当前节点，找到其中任意一个，然后将其内容替换并移除最末端节点，即可实现删除!

总结

第三种场景稍微复杂了一些，但基本都是这么一个套路，与二叉树不同的是，删除之后需要判断树高，对超过1的进行调整，类似上面插入的左旋转、右旋转操作!

三、代码实践

接下来，我们从代码层面来定义一下树的实体结构，如下：

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}

输出结果如下：

到此，关于“怎么理解并掌握Java的AVL树”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注亿速云网站，小编会继续努力为大家带来更多实用的文章！