二叉树04.深度分析AVL树的实现与优化
引子
前段时间项目需要用到 AVL树,所以时隔多年又将其重新完整实现了一遍。
因此,这里的所有代码都是高度优化的,并且都是严谨分析和推导的结果。
首先,我会介绍6种失衡类型和4种旋转;
然后,重点介绍插入和删除的优化实现,并会给出严谨的分析和证明,解释为什么可以这么优化;
最后,我会用 AVL 树与 Java中 的 TreeMap (红黑树)进行性能对比,以验证优化结果。
代码仓库:https://github.com/patricklaux/perfect-code
系列文章
(1) 深度优先遍历之递归和非递归遍历
(2) 深度优先遍历之 Morris 遍历
(3) 一种无需队列的层序遍历算法 IDDFS
(4) 深度分析AVL树的实现与优化【本文】
1. 简介
AVL树是一种自平衡二叉查找树(Self-balancing binary search tree),得名于其发明者: Georgy Adelson-Velsky 和 Evgenii Landis。
相比于二叉查找树最坏情况下时间复杂度为 O(n),AVL树查找、插入和删除的平均时间复杂度和最坏时间复杂度均为 O(logn),其中 n 为树的节点数。
2. 高度与平衡因子
AVL树的平衡性质:其任意节点的左子树和右子树的高度差的绝对值小于等于1。
AVL节点
private class Node<K, V> { K key; // 键 V val; // 值 byte height; // 高度 Node<K, V> left; // 左孩子 Node<K, V> right; //右孩子 }
获取高度
// 空树的高度定义为 -1。 private byte height(Node<K, V> node) { return (node == null) ? -1 : node.height; }
更新高度
// 取左右子树的高度的大者再加1,即为父节点的高度 private void updateHeight(Node<K, V> parent) { parent.height = (byte) (Math.max(height(parent.left), height(parent.right)) + 1); }
平衡因子
二叉查找树的平衡因子 BF (Balance Factor) 的定义为两棵子树的高度之差。
// 平衡因子的计算 private int balanceFactor(Node<K, V> parent) { return height(parent.left) - height(parent.right); }
根据AVL树的平衡性质,其任意节点的平衡因子只能为 1,0 和 -1。当一个节点的平衡因子大于 1 或小于 -1,我们可以通过旋转来恢复其平衡性质。
3. 失衡和旋转
AVL树的失衡可以总结为6种类型:LL,L,RR,R,LR,RL。
3.1. 单旋转
LL(右旋)
图1:LL型
观察上图的两个小例子,我们可以发现 P 节点的平衡因子为 2,其左孩子 L 的平衡因子为 1,都是左子树更重(left-heavy),因此称为 LL。
其中 P 节点的平衡因子大于 1,因此需要修正。
对于 LL 型,只需一次右旋即可恢复平衡性质。
private Node<K, V> rotateRight(Node<K, V> parent) { Node<K, V> left = parent.left; parent.left = left.right; left.right = parent; updateHeight(parent); updateHeight(left); return left; }
L(右旋)
图2:L型
L 型只有在删除节点时才会出现。
为什么?
二叉查找树总是将新节点添加为叶子节点,且一次只能增加一个节点。
如图2所示,当P节点无右子树时,先添加任意一个叶子节点(K 或 M)都会触发旋转,L 节点不可能同时有两个孩子。
因此,这种情形只有在删除 P 节点的右孩子才会出现。
RR(左旋)
图3:RR型
private Node<K, V> rotateLeft(Node<K, V> parent) { Node<K, V> right = parent.right; parent.right = right.left; right.left = parent; updateHeight(parent); updateHeight(right); return right; }
R(左旋)
图4:R型
观察上图,我们可以发现 P 节点的平衡因子为 -2,右子树更重;其右孩子 R 的平衡因子为 0,因此称为 R。
R 型与 RR 型一样,只需一次左旋即可恢复平衡性质。
但不一样的是:R型旋转之后该子树的高度不变。
R 型只有在删除节点时才会出现。
3.2. 双旋转
LR(先左旋后右旋)
图5:LR型错误示例
观察上图的两个小例子,我们可以发现 P 节点的平衡因子为 2,左子树更重;其左孩子 L 的平衡因子为 -1,右子树更重,因此称为 LR。
其中 P 节点的平衡因子大于 1,因此需要修正。
对于 LR 型,如上图所示,直接右旋无法恢复平衡性质。
正确的做法应该是如下图所示,先左旋后右旋。
图6:LR型正确示例
private Node<K, V> rotateLeftRight(Node<K, V> parent) { parent.left = rotateLeft(parent.left); return rotateRight(parent); }
RL(先右旋后左旋)
图7:RL型错误示例
观察上图的两个小例子,我们可以发现 P 节点的平衡因子为 -2,右子树更重;其右孩子 S 的平衡因子为 1,左子树更重,因此称为 RL。
其中 P 节点的平衡因子小于 -1,因此需要修正。
对于 RL 型,如上图所示,直接左旋无法恢复平衡性质。
而应该如下图所示,先右旋后左旋。
图8:RL型正确示例
private Node<K, V> rotateRightLeft(Node<K, V> parent) { parent.right = rotateRight(parent.right); return rotateLeft(parent); }
3.3. 恢复平衡
根据上面分析,我们可以根据失衡类型来选择如何旋转,使树恢复平衡性质。
private Node<K, V> balance(Node<K, V> parent) { int factor = balanceFactor(parent); if (factor >= 2) { if (balanceFactor(parent.left) <= -1) { // LR(2, -1):先左旋后右旋 return rotateLeftRight(parent); } // LL(2, 1) 或 L(2, 0):右旋 return rotateRight(parent); } else if (factor <= -2) { if (balanceFactor(parent.right) >= 1) { // RL(-2, 1):先右旋后左旋 return rotateRightLeft(parent); } // RR(-2, -1) 或 R(-2, 0):左旋 return rotateLeft(parent); } else { return parent; } }
3.4. 小结
L, LL, R, RR, LR, RL是指失衡类型;左旋、右旋、先左旋后右旋、先右旋后左旋 是指旋转类型。
大多数文章总结了 4 种失衡类型,其实是指 4 种旋转类型。
意识到有 L 型和 R 型的存在,这是理解插入和删除之间区别的关键,后面还会谈到可以根据两者的区别写出性能更好的代码。
4. 查找
图9:查找
查找的逻辑比较简单,与普通二叉查找树完全一致。
public V get(K key) { Assert.notNull(key); Node<K, V> p = root; while (p != null) { int cmp = compare(p.key, key); if (cmp > 0) { p = p.left; } else if (cmp < 0) { p = p.right; } else { return p.val; } } return null; }
5. 插入
与普通二叉查找树相比较,AVL树插入新节点后多了更新高度和恢复平衡的过程。
简单例子
图10:插入
如例1,插入新节点 X 之后,Y 的高度不变,整棵树仍处于平衡状态,则无需任何操作。
如例2,插入新节点 M 之后,N, O, R, U 的高度都会加 1,需从插入节点的父节点开始更新高度直到根节点才结束。
如例3,插入新节点 K 之后,需对 N 进行旋转,旋转完成后,O节点的高度不变,恢复平衡的过程就可以提前终止。
这里给回溯下一个简单的定义:从被修改的节点开始沿父路径递归向上更新节点高度和根据AVL树的平衡性质恢复平衡的过程,称之为AVL树的回溯。
插入节点和删除节点后都需要回溯,例1 可以看作是提前终止回溯的一个特例。
什么情形可以提前终止回溯,是优化 AVL 树插入和删除性能的关键,等后面讲完删除节点之后再来详细分析。
代码实现
public void put(K key, V value) { Assert.notNull(key); Assert.notNull(value); if (root == null) { root = new Node<>(key, value); size.set(1); return; } Node<K, V> p = root; int depth = 0, maxDepth = root.height + 1; // 回溯路径 Node<K, V>[] path = new Node[maxDepth]; while (depth < maxDepth) { path[depth] = p; int cmp = compare(p.key, key); if (cmp > 0) { if (p.left == null) { p.left = new Node<>(key, value); size.increment(); if (p.right != null) { return; // 父节点高度不变,无需回溯(见例1) } break; } else { p = p.left; depth++; } } else if (cmp < 0) { if (p.right == null) { p.right = new Node<>(key, value); size.increment(); if (p.left != null) { return; // 父节点高度不变,无需回溯(见例1) } break; } else { p = p.right; depth++; } } else { p.val = value; return; // 树结构未改变,无需回溯 } } // 回溯 root = backtrack(path, depth); }
6. 删除
AVL 树的删除操作相对复杂一些,我们先看删除流程图,然后再结合例子来讲解。
删除流程
图11:删除流程
-
如果删除节点为叶子节点,直接删除;
-
如果删除节点为非叶节点,左子树较高则用前驱节点替换删除节点;右子树较高则用后继节点替换删除节点;
-
回溯,更新高度并恢复平衡性质。
选择较高子树的节点来替换删除节点是一个小优化,可以减少旋转。
简单例子
图12:删除-例1
如例1,X 为叶子节点,直接删除。删除节点 X 之后,Y 的高度不变,且 Y 仍处于平衡状态,因此无需任何其它操作。
代码实现
public V remove(K key) { Assert.notNull(key); if (root == null) { return null; } int depth = 0; Node<K, V> del = root; // 根节点至删除节点之间的回溯路径 Node<K, V>[] path = new Node[root.height]; while (del != null) { int cmp = compare(del.key, key); if (cmp == 0) { size.decrement(); if (root == del) { root = swap(root); return del.val; } Node<K, V> p = path[--depth]; // 节点交换 if (p.right == del) { p.right = swap(del); } else { p.left = swap(del); } // 回溯 root = backtrack(path, depth); return del.val; } path[depth] = del; del = (cmp > 0) ? del.left : del.right; ++depth; } return null; }
节点交换
private Node<K, V> swap(Node<K, V> del) { Node<K, V> pl = del.left, pr = del.right; if (height(pl) >= height(pr)) { if (pl != null) { // 左子树的高度大于等于右子树:前驱节点交换删除节点 return swapPredecessor(del, pl); } //没有子节点 return null; } // 右子树的高度大于左子树:后继节点交换删除节点 return swapSuccessor(del, pr); } private Node<K, V> swapPredecessor(Node<K, V> del, Node<K, V> swap) { // 删除节点至交换节点之间的回溯路径 Node<K, V>[] path = new Node[del.height]; int depth = 0; // 查找前驱节点 while (swap.right != null) { depth++; path[depth] = swap; swap = swap.right; } // 替换删除节点 if (depth > 0) { Node<K, V> p = path[depth]; p.right = swap.left; swap.left = del.left; } swap.right = del.right; // 回溯 path[0] = swap; return backtrack(path, depth); } private Node<K, V> swapSuccessor(Node<K, V> del, Node<K, V> swap) { // 删除节点至交换节点之间的回溯路径 Node<K, V>[] path = new Node[del.height]; int depth = 0; // 查找后继节点 while (swap.left != null) { depth++; path[depth] = swap; swap = swap.left; } // 替换删除节点 if (depth > 0) { Node<K, V> parent = path[depth]; parent.left = swap.right; swap.right = del.right; } swap.left = del.left; // 回溯 path[0] = swap; return backtrack(path, depth); }
7. 回溯
回溯代码非常简单,就是沿父路径循环向上更新高度和恢复平衡,需要考虑的是什么情形可以提前终止回溯。
代码实现
private Node<K, V> backtrack(Node<K, V>[] path, int depth) { for (int j = depth; j > 0; j--) { Node<K, V> p = path[j]; Node<K, V> pp = path[j - 1]; int height = p.height, newHeight; updateHeight(p); if (pp.left == p) { pp.left = balance(p); newHeight = pp.left.height; } else { pp.right = balance(p); newHeight = pp.right.height; } if (newHeight == height) { break; // 高度不变,停止回溯(见命题1 的证明) } } updateHeight(path[0]); return balance(path[0]); }
回溯分析
命题1
AVL树插入或删除一个节点后,回溯过程中任意一个节点的高度无变化且其已处于平衡状态,则无需继续回溯。
证明:
AVL树的回溯是为了更新节点高度和恢复平衡性质。
回溯过程是沿回溯路径从深度最大的节点向根节点循环顺序调整,那么已回溯的节点必定已更新高度和恢复平衡性质。
设 X 为回溯路径中的任意一个节点,X 的高度无变化且已处于平衡状态,那么未回溯调整的剩余节点均为其祖先节点。因此要证明命题为真,只需证明两点:
(1) X 的所有祖先节点的高度和平衡因子均无变化;
(2) X 的所有祖先节点已处于平衡状态。
二叉搜索树增删一个节点,仅可能改变回溯路径中的节点的高度。
即当一个节点处于回溯路径中,该节点的父节点的另一个孩子高度一定不变。因此,当 X 高度无变化时:根据二叉树高度的定义,其父节点的高度一定不变;根据平衡因子的定义,则父节点的平衡因子也一定不变。同理,其父节点的父节点高度和平衡因子也不变,由此可得 X 的所有祖先节点的高度和平衡因子均无变化。
这就证明了1。
AVL树的任意节点在增删一个节点之前,一定处于平衡状态,一个节点的平衡因子不变则表示该节点依然处于平衡状态。
结论1 已证明 X 的所有祖先节点的平衡因子不变,因此其所有祖先节点一定依然处于平衡状态。
这就证明了2。
由此得证。
证明过程有点啰嗦,其实可以“显然”的,????。
问题
命题1 的证明已说明了回溯代码的正确性,我们再来深入思考一些常见问题,看看是否可以继续优化。
图15:回溯更新高度
(1) AVL树插入一个节点,最坏情况下需要logn次的高度更新(需要回溯到根节点)。
如例1 所示,插入节点M。当根节点的左右子树高度相同,新插入节点的父节点是树中深度最大的节点之一,且插入节点后树中所有节点依然保持平衡性质。
这意味着其所有祖先节点的高度都需要加1,所以需要logn次的高度更新。
(2) AVL树删除一个节点,最坏情况下需要logn次的高度更新(需要回溯到根节点)。
如例1 所示,删除节点 M。当删除唯一深度最大的叶子节点,且删除节点后树中其它节点依然保持平衡性质。
这会导致其所有祖先节点的高度都需要减1,所以需要logn次的高度更新。
(3) AVL树插入一个节点,最多仅需一次旋转即可恢复其平衡性质(一次单旋转或一次双旋转)。
AVL树的失衡类型一共有6种,L 型和 R 型仅在删除节点时才会出现,因此我们只需考虑 LL、RR、LR 和 RL 这4种失衡类型。
插入一个节点最多使得新节点所在的子树的高度加1,而LL、RR、LR 和 RL 这4种类型触发的旋转总是会将新节点所在子树的高度减1。
因此,AVL树插入一个节点,最多仅需一次旋转即可恢复其平衡性质。
(4) AVL树删除一个节点,最坏情况下需要logn次旋转才能恢复平衡性质(需要回溯到根节点)。
插入节点是子树高度加1,旋转会将子树高度减1,因此一次旋转即可恢复平衡;
删除节点是子树高度减1,旋转可能会将高度再次减1,这可能会触发再次旋转。
图16:多次旋转1
如例 3 所示:
W 的初始平衡因子为 -1,U 的平衡因子为 +1;
当删除 V 之后,W 的平衡因子变为 -2,触发第1次旋转;
第 1 次旋转完成之后,U 的平衡因子变为 2,触发第2次旋转。
我们可以用一个比较抽象的方式来表示这个规律:
推荐阅读
-
二叉树04.深度分析AVL树的实现与优化
-
【2022新手指南】Java编程进阶之路 - 六、技术架构篇 ### MySQL索引底层解析与优化实战 - 你会讲解MySQL索引的数据结构吗?性能调优技巧知多少? - Redis深度揭秘:你知道多少?从基础到哨兵、主从复制全梳理 - Redis持久化及哨兵模式详解,还有集群搭建和Leader选举黑箱打开 - Zookeeper是个啥?特性和应用场景大公开 - ZooKeeper集群搭建攻略及 Leader选举、读写一致性、共享锁实现细节 - 探究ZooKeeper中的Leader选举机制及其在分布式环境中的作用 - Zab协议深入剖析:原理、功能与在Zookeeper中的核心地位 - RabbitMQ全方位解读:工作模式、消费限流、可靠投递与配置策略 - 设计者视角:RabbitMQ过期时间、死信队列与延时队列实践指南 - RocketMQ特性和应用场景揭示:理解其精髓与差异化优势 - Kafka详细介绍:特性及广泛应用于实时数据处理的场景解析 - ElasticSearch实力揭秘:特性概述与作为搜索引擎的广泛应用 - MongoDB认知升级:非关系型数据库的优势阐述,安装与使用实战教学 - BIO/NIO/AIO网络模型对比:掌握它们的区别与在网络编程中的实际应用 - Netty带你飞:理解其超快速度背后的秘密,包括线程模型分析 - 网络通信黑科技:Netty编解码原理与常用编解码器的应用,Protostuff实战演示 - 解密Netty粘包与拆包现象,怎样有效应对这一常见问题 - 自定义Netty心跳检测机制,轻松调整检测间隔时间的艺术 - Dubbo轻骑兵介绍:核心特性概览,服务降级实战与其实现益处 - Dubbo三大神器解读:本地存根与本地伪装的实战运用与优势呈现 ----------------------- 七、结语与回顾
-
算法与数据结构]深入分析二叉树 (II) 堆结构的实现
-
动态规划算法的两种经典解决方式:最优子结构和DP数组的使用解析-动态规划算法问题 什么叫作最优子结构? 和动态规划有什么关系? 为什么动态规划遍历DP数组的方式有正着遍历,有倒着遍历,有斜着遍历? 最优子结构 最优子结构是某些问题的一种特定的性质,并不是动态规划问题所特有的. 很多问题都具有最优子结构,但是其中大部分不具有重叠子问题,所以不会归为动态规划系列的问题 最优子结构: 可以从子问题的最优结果推导出更大规模问题的最优结果 子问题之间必须相互独立 通过改造问题来优化由于子问题之间不独立而导致的最优子结构失效的情况: 问题: 假设学校有10个班,已知每个班的最高分与最低分差值的最大分数差,需要计算全校学生中的最大分数差 分析: 这样的问题就无法通过这10个班的最大分数差来推导出来,因为这10个班的最大分数差不一定就包含全校学生的最大分数差.比如全校的最大分数差可能是由8班的最高分和6班的最低分的分数差而得.这样就导致子问题之间不是互相独立的 改造问题: 直接进行问题改造 int result = 0; for (Student a : school) { for (Student b : school) { if (a is b) { continue; } result = max(result, |a.score - b.score|) } } return result; 改造问题就是将问题等价转化: 最大分数差就等价于最高分数与最低分数的差 那么就是要求最高和最低分数 求最高分数是具备最优子结构的,求最低分数也是具有最优子结构的 这样就样一个不具备最优子结构的问题转化为具备最优子结构的子问题 借助最优子结构解决最值问题,再解决最大分数差问题 题目: 求一棵二叉树的最大值,假设节点中的值都为非负数 int maxVal(TreeNode root) { if (root == null) { return -1; } int left = maxVal(root.left); int right = maxVal(root.right); return max(root.val, left, right); }