3.AVL树
3.3 AVL 树
概述
历史
AVL 树是一种自平衡二叉搜索树，由托尔·哈斯特罗姆在 1960 年提出并在 1962 年发表。它的名字来源于发明者的名字：Adelson-Velsky 和 Landis，他们是苏联数学家，于 1962 年发表了一篇论文，详细介绍了 AVL 树的概念和性质。
在二叉搜索树中，如果插入的元素按照特定的顺序排列，可能会导致树变得非常不平衡，从而降低搜索、插入和删除的效率。为了解决这个问题，AVL 树通过在每个节点中维护一个平衡因子来确保树的平衡。平衡因子是左子树的高度减去右子树的高度。如果平衡因子的绝对值大于等于 2，则通过旋转操作来重新平衡树。
AVL 树是用于存储有序数据的一种重要数据结构，它是二叉搜索树的一种改进和扩展。它不仅能够提高搜索、插入和删除操作的效率，而且还能够确保树的深度始终保持在 O(log n) 的水平。随着计算机技术的不断发展，AVL 树已经成为了许多高效算法和系统中必不可少的一种基础数据结构。
前面介绍过，如果一棵二叉搜索树长的不平衡，那么查询的效率会受到影响，如下图
通过旋转可以让树重新变得平衡，并且不会改变二叉搜索树的性质（即左边仍然小，右边仍然大）
如何判断失衡？
如果一个节点的左右孩子，高度差超过 1，则此节点失衡，才需要旋转
处理高度
如何得到节点高度？一种方式之前做过的一道题目：E05. 求二叉树的最大深度（高度），但由于求高度是一个非常频繁的操作，因此将高度作为节点的一个属性，将来新增或删除时及时更新，默认为 1（按力扣说法）
static class AVLNode {
int height = 1;
int key;
Object value;
AVLNode left;
AVLNode right;
// ...
}
求高度代码
这里加入了 height 函数方便求节点为 null 时的高度
private int height(AVLNode node) {
return node == null ? 0 : node.height;
}
更新高度代码
将来新增、删除、旋转时，高度都可能发生变化，需要更新。下面是更新高度的代码
private void updateHeight(AVLNode node) {
node.height = Integer.max(height(node.left), height(node.right)) + 1;
}
何时触发失衡判断？
定义平衡因子（balance factor）如下
平衡因子 = 左子树高度 - 右子树高度
当平衡因子
- bf = 0，1，-1 时，表示左右平衡
- bf > 1 时，表示左边太高
- bf < -1 时，表示右边太高
对应代码
private int bf(AVLNode node) {
return height(node.left) - height(node.right);
}
当插入新节点，或删除节点时，引起高度变化时，例如
目前此树平衡，当再插入一个 4 时，节点们的高度都产生了相应的变化，8 节点失衡了
在比如说，下面这棵树一开始也是平衡的
当删除节点 8 时，节点们的高度都产生了相应的变化，6 节点失衡了
失衡的四种情况
LL
- 失衡节点（图中 8 红色）的 bf > 1，即左边更高
- 失衡节点的左孩子（图中 6）的 bf >= 0 即左孩子这边也是左边更高或等高
LR
- 失衡节点（图中 8）的 bf > 1，即左边更高
- 失衡节点的左孩子（图中 6 红色）的 bf < 0 即左孩子这边是右边更高
对称的还有两种情况
RL
- 失衡节点（图中 3）的
bf <-1，即右边更高 - 失衡节点的右孩子（图中 6 红色）的 bf > 0，即右孩子这边左边更高
RR
- 失衡节点（图中 3）的
bf <-1，即右边更高 - 失衡节点的右孩子（图中 6 红色）的
bf <= 0，即右孩子这边右边更高或等高
实现
解决失衡
失衡可以通过树的旋转解决。什么是树的旋转呢？它是在不干扰元素顺序的情况下更改结构，通常用来让树的高度变得平衡。
观察下面一棵二叉搜索树，可以看到，旋转后，并未改变树的左小右大特性，但根、父、孩子节点都发生了变化
4 2
/ \ 4 right / \
2 5 --------------------> 1 4
/ \ <-------------------- / \
1 3 2 left 3 5
右旋
旋转前
- 红色节点，旧根（失衡节点）
- 黄色节点，旧根的左孩子，将来作为新根，旧根是它右孩子
- 绿色节点，新根的右孩子，将来要换爹作为旧根的左孩子
旋转后
代码
private AVLNode rightRotate(AVLNode red) {
AVLNode yellow = red.left;
AVLNode green = yellow.right;
yellow.right = red;
red.left = green;
return yellow;
}
左旋
旋转前
- 红色节点，旧根（失衡节点）
- 黄色节点，旧根的右孩子，将来作为新根，旧根是它左孩子
- 绿色节点，新根的左孩子，将来要换爹作为旧根的右孩子
旋转后
代码
private AVLNode leftRotate(AVLNode red) {
AVLNode yellow = red.right;
AVLNode green = yellow.left;
yellow.left = red;
red.right = green;
return yellow;
}
左右旋
指先左旋左子树，再右旋根节点（失衡），这时一次旋转并不能解决失衡
左子树旋转后
根右旋前
根右旋后
代码
private AVLNode leftRightRotate(AVLNode root) {
root.left = leftRotate(root.left);
return rightRotate(root);
}
右左旋
指先右旋右子树，再左旋根节点（失衡）
右子树右旋后
根左旋前
根左旋后
代码
private AVLNode rightLeftRotate(AVLNode root) {
root.right = rightRotate(root.right);
return leftRotate(root);
}
判断及调整平衡代码
private AVLNode balance(AVLNode node) {
if (node == null) {
return null;
}
int bf = bf(node);
if (bf > 1 && bf(node.left) >= 0) {
return rightRotate(node);
} else if (bf > 1 && bf(node.left) < 0) {
return rightLeftRotate(node);
} else if (bf < -1 && bf(node.right) > 0) {
return leftRightRotate(node);
} else if (bf < -1 && bf(node.right) <= 0) {
return rightRotate(node);
}
return node;
}
以上四种旋转代码里，都需要更新高度，需要更新的节点是红色、黄色，而绿色节点高度不变
新增
public void put(int key, Object value) {
root = doPut(root, key, value);
}
private AVLNode doPut(AVLNode node, int key, Object value) {
if (node == null) {
return new AVLNode(key, value);
}
if (key == node.key) {
node.value = value;
return node;
}
if (key < node.key) {
node.left = doPut(node.left, key, value);
} else {
node.right = doPut(node.right, key, value);
}
updateHeight(node);
return balance(node);
}
删除
public void remove(int key) {
root = doRemove(root, key);
}
private AVLNode doRemove(AVLNode node, int key) {
if (node == null) {
return null;
}
if (key < node.key) {
node.left = doRemove(node.left, key);
} else if (node.key < key) {
node.right = doRemove(node.right, key);
} else {
if (node.left == null) {
node = node.right;
} else if (node.right == null) {
node = node.left;
} else {
AVLNode s = node.right;
while (s.left != null) {
s = s.left;
}
s.right = doRemove(node.right, s.key);
s.left = node.left;
node = s;
}
}
if (node == null) {
return null;
}
updateHeight(node);
return balance(node);
}
完整代码备份
public class AVLTree {
static class AVLNode {
int height = 1;
int key;
Object value;
AVLNode left;
AVLNode right;
public AVLNode(int key) {
this.key = key;
}
public AVLNode(int key, Object value) {
this.key = key;
this.value = value;
}
public AVLNode(int key, Object value, AVLNode left, AVLNode right) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
}
}
AVLNode root;
private AVLNode leftRotate(AVLNode p) {
AVLNode r = p.right;
AVLNode b = r.left;
r.left = p;
p.right = b;
updateHeight(p);
updateHeight(r);
return r;
}
private void updateHeight(AVLNode node) {
node.height = Integer.max(height(node.left), height(node.right)) + 1;
}
private AVLNode rightRotate(AVLNode r) {
AVLNode a = r.left;
AVLNode b = a.right;
a.right = r;
r.left = b;
updateHeight(r);
updateHeight(a);
return a;
}
private AVLNode leftRightRotate(AVLNode p) {
AVLNode r = p.left;
p.left = leftRotate(r);
return rightRotate(p);
}
private AVLNode rightLeftRotate(AVLNode p) {
AVLNode r = p.right;
p.right = rightRotate(r);
return leftRotate(p);
}
private int height(AVLNode node) {
return node == null ? 0 : node.height;
}
public void remove(int key) {
root = doRemove(root, key);
}
private AVLNode doRemove(AVLNode node, int key) {
if (node == null) {
return null;
}
if (key < node.key) {
node.left = doRemove(node.left, key);
} else if (node.key < key) {
node.right = doRemove(node.right, key);
} else {
if (node.left == null) {
node = node.right;
} else if (node.right == null) {
node = node.left;
} else {
AVLNode s = node.right;
while (s.left != null) {
s = s.left;
}
s.right = doRemove(node.right, s.key);
s.left = node.left;
node = s;
}
}
if (node == null) {
return null;
}
updateHeight(node);
return balance(node);
}
public void put(int key, Object value) {
root = doPut(root, key, value);
}
private AVLNode doPut(AVLNode node, int key, Object value) {
if (node == null) {
return new AVLNode(key, value);
}
if (key == node.key) {
node.value = value;
return node;
}
if (key < node.key) {
node.left = doPut(node.left, key, value);
} else {
node.right = doPut(node.right, key, value);
}
updateHeight(node);
return balance(node);
}
private int bf(AVLNode node) {
return height(node.left) - height(node.right);
}
private AVLNode balance(AVLNode node) {
if (node == null) {
return null;
}
int bf = bf(node);
if (bf > 1 && bf(node.left) >= 0) {
return rightRotate(node);
} else if (bf > 1 && bf(node.left) < 0) {
return rightLeftRotate(node);
} else if (bf < -1 && bf(node.right) > 0) {
return leftRightRotate(node);
} else if (bf < -1 && bf(node.right) <= 0) {
return rightRotate(node);
}
return node;
}
}
小结
AVL树的优点：
- AVL树是一种自平衡树，保证了树的高度平衡，从而保证了树的查询和插入操作的时间复杂度均为O(logn)。
- 相比于一般二叉搜索树，AVL树对查询效率的提升更为显著，因为其左右子树高度的差值不会超过1，避免了二叉搜索树退化为链表的情况，使得整棵树的高度更低。
- AVL树的删除操作比较简单，只需要像插入一样旋转即可，在旋转过程中树的平衡性可以得到维护。
AVL树的缺点：
- AVL树每次插入或删除节点时需要进行旋转操作，这个操作比较耗时，因此在一些应用中不太适用。
- 在AVL树进行插入或删除操作时，为保持树的平衡需要不断进行旋转操作，在一些高并发环节和大数据量环境下，这可能会导致多余的写锁导致性能瓶颈。
- AVL树的旋转操作相对较多，因此在一些应用中可能会造成较大的空间浪费。