数据结构（四）-- AVL树基础

AVL树介绍

在介绍AVL树之前，我们需要先了解一个概念，那就是平衡二叉树。 上面链接是百度百科的解释，不过我个人还是喜欢用简单易懂的话来解释一些拗口的概念，平衡二叉树首先它是一棵二叉树。 那么平衡指的是什么平衡呢？其实就是树的左右子树相对平衡，如果说左子树很大，右子树很小，那么这个树就不平衡，就往一边“倒”。 不过在平衡二叉树中这个平衡限制的没有那么严格，它只要求任意一个节点的左子树与右子树的高度差不超过1。

那么AVL树和平衡二叉树有什么联系呢？AVL树的名称是因为最早是两位俄罗斯的大佬分别名为G.M. Adelson-Velsky和E.M. Landis提出的数据结构，所以取了两位大佬名字的首字母作为名字。 AVL树是最早发明的自平衡二叉树。

本文首发于心安-XinAnzzZ 的个人博客，转载请注明出处~

平衡因子

前面的文章中，我们讲了二分搜索树，今天我们说的AVL树是基于二分搜索树的一种数据结构，不同的是，我们需要维持二分搜索树的每个节点的平衡性。 这里我们引入平衡因子的概念，一个节点的平衡因子指的是这棵树的左子树高度减去右子树高度（H左 - H右）。 由于概念中限制了，两棵子树的高度差不超过1就算是平衡，那么也就是说平衡因子为-1、0、1都说明以这个节点为根的树是平衡的。 所以我们要想保证二分搜索树平衡就需要让每一个节点的平衡因子的绝对值都不大于1。

既然要维护平衡因子，就需要记录每个子树的高度。所以，节点类Node代码如下：

<pre spellcheck="false" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" lang="java" cid="n8" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: Monaco, Consolas, "Andale Mono", "DejaVu Sans Mono", monospace; margin-top: 0px; margin-bottom: 20px; background-image: inherit; background-size: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: inherit; font-size: 0.9rem; display: block; break-inside: avoid; text-align: left; white-space: normal; position: relative !important; padding: 10px 30px 10px 0px; border: 1px solid; width: inherit; background-position: inherit inherit; background-repeat: inherit inherit;"> public class AVLTree<K extends Comparable<K>, V> {
private class Node {
K key;
​
V value;
​
// 节点的左右指针
Node left, right;
​
// 节点所在的树的高度
int height;
​
Node() {
this(null, null);
}
​
Node(K key, V value) {
this.key = key;
this.value = value;
// 初始状态节点的高度为1
this.height = 1;
}
}
}</pre>

<pre spellcheck="false" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" lang="java" cid="n10" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: Monaco, Consolas, "Andale Mono", "DejaVu Sans Mono", monospace; margin-top: 0px; margin-bottom: 20px; background-image: inherit; background-size: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: inherit; font-size: 0.9rem; display: block; break-inside: avoid; text-align: left; white-space: normal; position: relative !important; padding: 10px 30px 10px 0px; border: 1px solid; width: inherit; background-position: inherit inherit; background-repeat: inherit inherit;"> public class AVLTree<K extends Comparable<K>, V> {
private class Node {
K key;
​
V value;
​
// 节点的左右指针
Node left, right;
​
// 节点所在的树的高度
int height;
​
Node() {
this(null, null);
}
​
Node(K key, V value) {
this.key = key;
this.value = value;
// 初始状态节点的高度为1
this.height = 1;
}
}
​
/*** 获取节点的高度 /
private int getHeight(Node node) {
if (node == null)
return 0;
return node.height;
}
​
/** 获取节点的平衡因子 */
private int getBalanceFactor(Node node) {
if (node == null)
return 0;
return getHeight(node.left) - getHeight(node.right);
}
}</pre>

<pre spellcheck="false" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" lang="java" cid="n13" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: Monaco, Consolas, "Andale Mono", "DejaVu Sans Mono", monospace; margin-top: 0px; margin-bottom: 20px; background-image: inherit; background-size: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: inherit; font-size: 0.9rem; display: block; break-inside: avoid; text-align: left; white-space: normal; position: relative !important; padding: 10px 30px 10px 0px; border: 1px solid; width: inherit; background-position: inherit inherit; background-repeat: inherit inherit;"> public void put(K key, V value) {
Node newNode = new Node(key, value);
root = put(root, newNode);
}
​
private Node put(Node node, Node newNode) {
if (node == null) {
size++;
return newNode;
}
​
if (newNode.key.compareTo(node.key) < 0) {
node.left = put(node.left, newNode);
} else if (newNode.key.compareTo(node.key) > 0) {
node.right = put(node.right, newNode);
} else {
node.value = newNode.value;
}
​
return node;
}</pre>

**​

感谢阅读，欢迎在评论区和博主沟通交流，也欢迎加入博主的个人qq群

[ NullPointerException

36635506](https://shang.qq.com/wpa/qunwpa?idkey=5af77859bfdd857f1f1810990bfc261a7d7f2b04672c6e47070f84a980027570)讨（chui）论（niu）。

​**

示例代码Github

插入新元素之后，就有可能出现“不平衡”的状态出现，也就是节点的平衡因子的绝对值不再小于等于1，所以我们就需要对该节点进行结构转换，让该节点继续“保持平衡”。 这一步经常被称为“左旋和右旋”，其原理及代码实现将会在下一小节 AVL树的左旋与右旋中为大家介绍。

这里的代码是基于之前实现的二分搜索树的插入元素的代码的，所以直接复制过来：

往AVL树中插入一个元素

为了方便后面的代码编写，增加两个辅助函数，分别用于获取节点的高度和平衡因子：