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>