前言
在上一篇博文(数据结构之二叉树(三)——二叉查找树)中曾指出二叉查找树会出现退化的情况，导致查询效率最差可退化至O(n)。维基百科中提到，一般的二叉查找树的查询复杂度是跟目标节点到树根的距离（即深度）有关，因此当结点的深度普遍较大时，查询的均摊复杂度会上升，为了更高效的查询，平衡树应运而生了。AVL树是一种典型的平衡二叉查找树。下面，我们一起来探讨一下AVL树。
定义和性质
定义：一棵AVL树需要满足以下的条件:
(1) 它的左子树和右子树都是AVL树。
(2) 左子树和右子树的高度差不能超过1。
性质:
(1) 一棵n个节点的AVL树的其高度保持在O(log2(n)),不会超过3/2log2(n+1) 。
(2) 一棵n个节点的AVL树的平均搜索长度保持在O(log2(n))。
(3) 一棵n个节点的AVL树删除一个结点做平衡化旋转所需要的时间为O(log2(n))。
在AVL树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O(log2(n))。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。引入AVL树的目的是为了提高二叉树的搜索的效率，减少树的平均搜索长度。为此，就必须每向二叉树插入一个结点时调整树的结构，使得二叉树搜索保持平衡，从而可能降低树的高度，减少树的平均搜索长度。
图1 - 一棵典型的AVL树
设计与实现
数据结构
由于AVL树和树的高度密切相关，为了实现方便，在之前TreeNode的基础上添加height属性，来记录节点的高度。
class AVLNode {
int val;
AVLNode left = null;
AVLNode right = null;
int height;
public AVLNode(int val, int height) {
this.val = val;
this.height = height;
}
public AVLNode(int val) {
this(val, 1);
}
}
需要说明的是规定空节点高度为0，叶子节点的高度为1，根节点的高度最大。如下图所示。
AVL树的高度
计算高度
/**
* 获取树高度
*
* @param root
* @return
*/
public int height(AVLNode root) {
if (root == null) {
return 0;
}
int leftHeight = height(root.left);
int rightHeight = height(root.right);
return 1 + Math.max(leftHeight, rightHeight);
}
查找元素
AVL树查找元素实现方法与普通的二叉排序树相同。
/**
* AVL树查找元素
*
* @param root AVL树的根节点
* @param val 需要查找的目标值
* @return
*/
public AVLNode search(AVLNode root, int val) {
if (root == null) {
return null;
}
if (val < root.val) {
return search(root.left, val);
} else if (val > root.val) {
return search(root.right, val);
} else {
return root;
}
}
插入元素
由于在向AVL树中插入新节点时，可能会破坏树的平衡性。因此，需要在保持二叉查找树特性的前提下，调整各个节点的链接关系，使之重新满足平衡条件。链接关系的调整可通过旋转来实现，其中旋转可分为RR、LL、RL、LR四种类型。那为什么是这4种呢？可以这样思考：由于在平衡条件被打破时需要立即对不平衡的AVL树进行调整，即“步步调整，步步平衡”。因此，不平衡的AVL树高度差最大为2。下面，我们用几个简单实例来进行说明，其中AVL树中，黄色节点为失衡根节点，绿色节点为旋转节点。
(1) RR型：调整方式为直接左旋：失衡根节点作旋转节点左孩子即可。RR型
(2) LL型：调整方式为直接右旋：失衡根节点作旋转节点右孩子即可。可以明显看出，这种情况与LL型是对称的。LL型
(3) RL型：这种情况下单一左旋转不能满足二叉查找树特性要求，因此，需要先右旋转换为RR型，然后再左旋以满足平衡条件。RL型
(4) LR型：该情况与RL型是对称的，不再赘述。LR型
下面，给出Java实现代码。
/**
* RR型：左旋
*
* @param root
* @return
*/
private AVLNode leftRotate(AVLNode root) {
AVLNode node = root.right;
root.right = node.left;
node.left = root;
root.height = height(root);
node.height = height(node);
return node;
}
/**
* LL型：右旋
*
* @param root
* @return
*/
private AVLNode rightRotate(AVLNode root) {
AVLNode node = root.left;
root.left = node.right;
node.right = root;
root.height = height(root);
node.height = height(node);
return node;
}
/**
* RL型：右旋-左旋
*
* @param root
* @return
*/
private AVLNode rightLeftRotate(AVLNode root) {
root.right = rightRotate(root.right);
return leftRotate(root);
}
/**
* LR型：左旋-右旋
*
* @param root
* @return
*/
private AVLNode leftRightRotate(AVLNode root) {
root.left = leftRotate(root.left);
return rightRotate(root);
}
/**
* 增加新节点
*
* @param root AVL树的根节点
* @param val 需要增加的目标值
* @return
*/
public AVLNode insert(AVLNode root, int val) {
if (root == null) {
root = new AVLNode(val);
return root;
}
if (val < root.val) {
root.left = insert(root.left, val);
if (height(root.left) - height(root.right) == 2) {
// LL型
if (root.left.val == val) {
root = rightLeftRotate(root);
} else { // LR型
root = leftRightRotate(root);
}
}
} else if (val > root.val) {
root.right = insert(root.right, val);
if (height(root.right) - height(root.left) == 2) {
// RR型
if (root.right.val == val) {
root = leftRightRotate(root);
} else { // RL型
root = rightLeftRotate(root);
}
}
}
// 重新计算节点高度
root.height = height(root);
return root;
}
删除元素
AVL树的删除操作与BST树非常类似，只是AVL树需要在删除节点后增加调整阶段以满足平衡条件。实现代码如下：
/**
* 删除元素
*
* @param root
* @param val
* @return
*/
public AVLNode delete(AVLNode root, int val) {
if (root == null) {
return null;
}
// 左子树查找该元素
if (val < root.val) {
root.left = delete(root.left, val);
// 检查是否平衡
if (height(root.right) - height(root.left) == 2) {
AVLNode currentNode = root.right;
if (height(currentNode.left) > height(currentNode.right)){
// LL型
root = rightRotate(root);
} else {
// LR型
root = leftRightRotate(root);
}
}
} else if (val > root.val) {
// 右子树查找该元素
root.right = delete(root.right, val);
if (height(root.left) - height(root.right) == 2){
AVLNode currentNode = root.left;
if (height(currentNode.right) > height(currentNode.left)){
// RR型
root = leftRotate(root);
} else {
// RL型
root = rightLeftRotate(root);
}
}
} else { // 找到该元素
if (root.left != null && root.right != null) {
// 使用前继节点替换该节点
root.val = predecessor(root).val;
root.left = delete(root.left, root.val);
} else { // 仅有一个孩子节点或者只是叶子节点
root = root.left != null ? root.left : root.right;
}
}
if (root != null){
// 重新计算节点高度
root.height = height(root);
}
return root;
}
完整代码
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
/**
* 自平衡AVL树：AVL树实现
*
* @Author: Jeremy
* @Date: 2019/6/27 11:29
*/
class AVLNode extends TreeNode {
int val;
AVLNode left = null;
AVLNode right = null;
int height;
public AVLNode(int val, int height) {
super(val);
this.val = val;
this.height = height;
}
public AVLNode(int val) {
this(val, 1);
}
}
public class AVLTree {
/**
* 获取树高度
*
* @param root
* @return
*/
public int height(AVLNode root) {
if (root == null) {
return 0;
}
int leftHeight = height(root.left);
int rightHeight = height(root.right);
return 1 + Math.max(leftHeight, rightHeight);
}
/**
* AVL树查找元素
*
* @param root AVL树的根节点
* @param val 需要查找的目标值
* @return
*/
public AVLNode search(AVLNode root, int val) {
if (root == null) {
return null;
}
if (val < root.val) {
return search(root.left, val);
} else if (val > root.val) {
return search(root.right, val);
} else {
return root;
}
}
/**
* RR型：左旋
*
* @param root
* @return
*/
private AVLNode leftRotate(AVLNode root) {
AVLNode node = root.right;
root.right = node.left;
node.left = root;
root.height = height(root);
node.height = height(node);
return node;
}
/**
* LL型：右旋
*
* @param root
* @return
*/
private AVLNode rightRotate(AVLNode root) {
AVLNode node = root.left;
root.left = node.right;
node.right = root;
root.height = height(root);
node.height = height(node);
return node;
}
/**
* RL型：右旋-左旋
*
* @param root
* @return
*/
private AVLNode rightLeftRotate(AVLNode root) {
root.right = rightRotate(root.right);
return leftRotate(root);
}
/**
* LR型：左旋-右旋
*
* @param root
* @return
*/
private AVLNode leftRightRotate(AVLNode root) {
root.left = leftRotate(root.left);
return rightRotate(root);
}
/**
* 增加新节点
*
* @param root AVL树的根节点
* @param val 需要增加的目标值
* @return
*/
public AVLNode insert(AVLNode root, int val) {
if (root == null) {
root = new AVLNode(val);
return root;
}
if (val < root.val) {
root.left = insert(root.left, val);
if (height(root.left) - height(root.right) == 2) {
// LL型
if (root.left.val == val) {
root = rightLeftRotate(root);
} else { // LR型
root = leftRightRotate(root);
}
}
} else if (val > root.val) {
root.right = insert(root.right, val);
if (height(root.right) - height(root.left) == 2) {
// RR型
if (root.right.val == val) {
root = leftRightRotate(root);
} else { // RL型
root = rightLeftRotate(root);
}
}
}
// 重新计算节点高度
root.height = height(root);
return root;
}
/**
* 删除元素
*
* @param root
* @param val
* @return
*/
public AVLNode delete(AVLNode root, int val) {
if (root == null) {
return null;
}
// 左子树查找该元素
if (val < root.val) {
root.left = delete(root.left, val);
// 检查是否平衡
if (height(root.right) - height(root.left) == 2) {
AVLNode currentNode = root.right;
if (height(currentNode.left) > height(currentNode.right)){
// LL型
root = rightRotate(root);
} else {
// LR型
root = leftRightRotate(root);
}
}
} else if (val > root.val) {
// 右子树查找该元素
root.right = delete(root.right, val);
if (height(root.left) - height(root.right) == 2){
AVLNode currentNode = root.left;
if (height(currentNode.right) > height(currentNode.left)){
// RR型
root = leftRotate(root);
} else {
// RL型
root = rightLeftRotate(root);
}
}
} else { // 找到该元素
if (root.left != null && root.right != null) {
// 使用前继节点替换该节点
root.val = predecessor(root).val;
root.left = delete(root.left, root.val);
} else { // 仅有一个孩子节点或者只是叶子节点
root = root.left != null ? root.left : root.right;
}
}
if (root != null){
// 重新计算节点高度
root.height = height(root);
}
return root;
}
/**
* 最小节点
* @param root
* @return
*/
public AVLNode min(AVLNode root){
if (root == null){
return null;
}
AVLNode currentNode = root;
while (currentNode.left !=null){
currentNode = currentNode.left;
}
return currentNode;
}
/**
* 最大节点
* @param root
* @return
*/
public AVLNode max(AVLNode root){
if (root == null){
return null;
}
AVLNode currentNode = root;
while (currentNode.right !=null){
currentNode = currentNode.right;
}
return currentNode;
}
/**
* 寻找后继节点
* @param root
* @return
*/
public AVLNode successor(AVLNode root){
return min(root.right);
}
/**
* 寻找前继节点
* @param root
* @return
*/
public AVLNode predecessor(AVLNode root){
return max(root.left);
}
/**
* 中序遍历二叉树，非递归
*
* @param root
*/
public void inOrderTraverseNoRecursion(AVLNode root) {
LinkedList<AVLNode> stack = new LinkedList<>();
AVLNode currentNode = root;
while (currentNode != null || !stack.isEmpty()) {
// 一直循环到二叉树最左端的叶子结点（currentNode是null）
while (currentNode != null) {
stack.push(currentNode);
currentNode = currentNode.left;
}
currentNode = stack.pop();
System.out.print(currentNode.val + "(" + currentNode.height + ") ");
currentNode = currentNode.right;
}
System.out.print("\n");
}
/**
* 按行遍历二叉树
*
* @param root
* @return
*/
public int[][] printTreeByRow(AVLNode root) {
List<List<Integer>> list = new ArrayList<>();
LinkedList<AVLNode> queue = new LinkedList();
queue.push(root);
List<Integer> tmp = new ArrayList<>();
AVLNode last = root;
AVLNode nLast = null;
while (!queue.isEmpty()) {
AVLNode top = queue.poll();
tmp.add(top.val);
if (top.left != null) {
queue.add(top.left);
nLast = top.left;
}
if (top.right != null) {
queue.add(top.right);
nLast = top.right;
}
// 当last == top时代表该换行了
if (last == top) {
last = nLast;
list.add(tmp);
tmp = new ArrayList<>();
}
}
int[][] res = new int[list.size()][];
for (int i = 0; i < list.size(); i++) {
res[i] = new int[list.get(i).size()];
for (int j = 0; j < list.get(i).size(); j++) {
res[i][j] = list.get(i).get(j);
}
}
return res;
}
public static void main(String[] args) {
AVLTree avlTree = new AVLTree();
// 构建AVL树
AVLNode root = null;
root = avlTree.insert(root, 8);
root = avlTree.insert(root, 3);
root = avlTree.insert(root, 10);
root = avlTree.insert(root, 1);
root = avlTree.insert(root, 6);
root = avlTree.insert(root, 9);
root = avlTree.insert(root, 14);
root = avlTree.insert(root, 4);
root = avlTree.insert(root, 7);
root = avlTree.insert(root, 13);
// 计算高度
int height = avlTree.height(root);
System.out.println(height);
// 中序遍历
avlTree.inOrderTraverseNoRecursion(root);
// 查找
AVLNode node = avlTree.search(root, 13);
System.out.println(node.val);
System.out.println(avlTree.height(node));
// 插入13
root = avlTree.insert(root, 13);
int[][] res = avlTree.printTreeByRow(root);
for (int j = 0; j < res.length; j++) {
System.out.println(Arrays.toString(res[j]));
}
// 最小节点
AVLNode minNode = avlTree.min(root);
System.out.println("最小节点值： " + minNode.val);
// 最大节点
AVLNode maxNode = avlTree.max(root);
System.out.println("最大节点值： " + maxNode.val);
// 直接后继
AVLNode successorNode = avlTree.successor(root);
System.out.println(root.val + "的直接后继： " + successorNode.val);
// 直接前继
AVLNode predecessorNode = avlTree.predecessor(root);
System.out.println(root.val + "的直接前继： " + predecessorNode.val);
root = avlTree.delete(root, 8);
avlTree.inOrderTraverseNoRecursion(root);
res = avlTree.printTreeByRow(root);
for (int j = 0; j < res.length; j++) {
System.out.println(Arrays.toString(res[j]));
}
}
}
效率分析
AVL 的操作代价分析：
(1) 查找代价： AVL是严格平衡的BST（平衡因子不超过1）。那么查找过程与BST一样，只是AVL不会出现最差情况的BST(单支树)。因此查找效率最好，最坏情况都是O(logN)数量级的。
(2) 插入代价： AVL必须要保证严格平衡，那么每一次插入数据使得AVL中某些节点的平衡因子超过1就必须进行旋转操作。事实上，AVL的每一次插入节点操作最多只需要旋转1次(单旋转或双旋转)。因此，总体上插入操作的代价仍然在O(logN)级别上(插入节点需要首先查找插入的位置)。
(3) 删除代价：AVL树删除节点之后必须检查从删除节点开始到根节点路径上的所有节点的平衡因子。因此删除的代价稍微要大一些。每一次删除操作最多需要O(logN)次旋转。因此，删除操作的时间复杂度为O(logN)+O(logN)=O(2logN)。
总结
本篇博文主要介绍了AVL的定义和性质，使用Java对AVL树进行了实现，并且对AVL树的查找、增加和删除效率进行了分析，希望能对大家有所帮助，也欢迎大家积极留言，批评指正。
接下来，我会继续介绍另一种平衡二叉树——红黑树，敬请期待～
推荐阅读
- 数据结构之二叉树(五)——红黑树(待更新)
写在最后
欢迎大家关注我的个人博客复旦猿。
