面试官提到的 AVL 树，到底是个啥

了解过平衡二叉树的朋友们，对它一定有印象，今天阿粉就与大家一起深入了解一下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> { 
 2 
 3    /**节点关键字*/ 
 4    E key; 
 5 
 6    /**当前节点树高*/ 
 7    int height; 
 8 
 9    /**当前节点的左子节点*/ 
10    AVLNode lChild = null; 
11 
12    /**当前节点的右子节点*/ 
13    AVLNode 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> { 
  2 
  3    /**定义根节点*/ 
  4    public AVLNode 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 node){ 
 16        if(node == null){ 
 17            return new AVLNode(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 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 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 search(E key){ 
113        return searchAVL(key, root); 
114    } 
115 
116    private AVLNode searchAVL(E key, AVLNode 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 searchDeleteMin(AVLNode 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 deleteMin(AVLNode 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 rotateLeft(AVLNode node){ 
175        System.out.println("节点：" + node.key + "，单次左旋转"); 
176        AVLNode 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 rotateRight(AVLNode node){ 
191        System.out.println("节点：" + node.key + "，单次右旋转"); 
192        AVLNode 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 rotateLeftRight(AVLNode 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 rotateRightLeft(AVLNode 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 node){ 
234        return node != null ? node.height: -1; 
235    } 
236 
237    /** 
238     * 更新节点高度 
239     * @param node 
240     * @return 
241     */ 
242    private int updateHeight(AVLNode 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 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 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 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 avlTree = new AVLSolution(); 
 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 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)次旋转。

整体上来说，平衡二叉树优于普通二叉查找树!

五、参考

[1] 简书 – nicktming – 二叉平衡树: https://www.jianshu.com/p/22c00b3731f5

[2] iteye – Heart.X.Raid – 平衡二叉查找树 [AVL]: https://www.iteye.com/blog/hxraid-609949