一, 简介
本文将通过图解和代码详细讲解 AVL 平衡二叉树的性质及失衡和再平衡的内容. 在看本文之前希望大家具备二分搜索树的相关知识. 或移步《二分搜索树》了解二分搜索树.
二, 平衡二叉树
前面关于二分搜索树的文章, 最后分析了在极端情况下, 二分搜索树会退化为一个链表, 那为了避免这种情况的发生, AVL 平衡二叉树应运而生.
平衡二叉树的定义:
平衡二叉树是一颗二分搜索树, 及平衡二叉树满足二分搜索树的所有性质
平衡二叉树要求任意一个节点的左右子树的高度差不能超过 1
对于第一点应该挺容易理解的, 对于第二点, 我们要做一点解释. 对于高度差, 有一个专有名词平衡因子.
平衡因子: 左子树的高度减去右子树的高度, 及 B = B 左 - B 右. 由平衡二叉树的定义可知, 平衡因子的取值只可能为 0,1,-1.0: 左右子树等高. 1: 左子树比较高.-1: 右子树比较高. 如下图
高度: 一般的我们取叶子节点的高度值为 1, 任意一个节点的高度值取左右子树比较高的那个孩子节点的高度值然后加 1. 比如上图 1 中 20 这个节点的高度值, 显然左子树比较高, 所以 H20 = H10 + 1; 依次类推, H10 = H6(或者 H14) + 1 = 2; 所以 H20 = 3;
上图 1 的树的各个节点的高度, 如下图 1 所示. 各个节点的平衡因子如下图 2 红色数字所示. 所以根据定义, 各个节点的左右子树的高度差不能超过 1, 及任意一个节点的平衡因子应该为 -1, 0, 1; 所以下面的这棵树是一棵平衡二叉树.
三, AVL 的失衡及再平衡 -- 旋转
3.1,AVL 的失衡情况
前面我们介绍了 AVL 的高度和平衡因子问题, 接下来我们来看看有几种情况会导致 AVL 的失衡, 也就是什么情况下我们需要调整 AVL 树, 使其经过调整后能继续维持平衡状态.
如上图 1 所示, 当我们已经插入了 20,10 元素, 当我们再插入 6 这个元素的时候, 很显然 20 节点的平衡因子为 2, 及 B20 = 2> 1 此时该树已经不平衡了.
如上图 2 所示, 当我们已经插入了 20,10 元素, 当我们再插入 14 这个元素的时候, 很显然 20 节点的平衡因子为 2, 及 B20 = 2> 1 此时该树已经不平衡了.
如上图 3 所示, 当我们已经插入了 20,29 元素, 当我们再插入 33 这个元素的时候, 很显然 20 节点的平衡因子为 - 2, 及 B20 = -2 <-1 此时该树已经不平衡了.
如上图 4 所示, 当我们已经插入了 20,29 元素, 当我们再插入 25 这个元素的时候, 很显然 20 节点的平衡因子为 - 2, 及 B20 = -2 < -1 此时该树已经不平衡了.
对于 AVL, 需要进行再平衡操作的情况正如以上 4 个图所示. 那接下来我们需要讨论的问题就是如何调整了, 及旋转.
3.2,AVL 的再平衡 -- 旋转
如下图所示, 对于上一章我们说的四种失衡状态的调整. 然后我们加下来对照着下面的四张图片进行逐一介绍旋转的过程.
3.2.1,LL 旋转
LL, 及对于上图 1 的待旋转的树(中间那棵), 造成这棵树失衡的节点 6 在 20 节点的左孩子的左孩子处, left,left 简称为 LL. 这个时候我们需要进行的旋转一般称之为 LL 旋转. 对于这种情况, 我们考虑如何旋转, 始终要考虑如何通过旋转既达到再平衡的目的, 又能维持平衡二叉树的性质不变, 即左孩子 < 父节点 < 右孩子. 观察图一中插入节点 6 以后, 一个很显然的结果就是不管我们怎么旋转只有当 10 节点在中间的时候我们才能保证这棵树是平衡的. 我们知道了结果, 再看看这个旋转的过程, 为了保证平衡二叉树的性质, 根据左孩子 < 父节点 < 右孩子的性质, 我们看 20> 10, 也就是说, 我们可以将 20 节点下移, 放到 10 节点的右孩子处, 即得到图 1 中的结果.
为了更好地描述这个过程, 我们使用几个虚拟的节点.
- ///////////////////////////////////////////////////
- // LL T1<Z<T2<X <T3<Y<T4 //
- // y x //
- // / \ / \ //
- // x T4 向右旋转 (y) z y //
- // / \ - - - - - - - -> / \ / \ //
- // z T3 T1 T2 T3 T4 //
- // / \ //
- // T1 T2 //
- ///////////////////////////////////////////////////
如上所示, 我们真实的三个节点为 Y> X> Z. 然后我们为了方便描述, 增加几个虚拟的节点, 节点间的大小关系: T1<Z<T2<X <T3<Y<T4
对于 LL, 我们要右旋才能达到再平衡, 根据之前描述, 我们需要将 Y 节点顶替 T3 的位置, 问题来了, T3 放哪呢? 根据大小关系 X < T3 < Y. 我们可以将 T3 放到 Y 的左孩子节点的位置, 这样进行旋转后得到的结果如上所示. 我们发现这棵树不但达到了再平衡的目的, 节点间的大小关系, 依然维持了: T1<Z<T2< X <T3<Y<T4 的关系.
代码实现一下这个过程, 先假设我们的节点为 Node. 传入的参数应该是 Y 节点
- private Node rightRotate(Node y) {
- Node x = y.left;
- Node T3 = x.right;
- // 向右旋转过程
- x.right = y;
- y.left = T3;
- return x;
- }
对于以上代码, 结合上面我们分析的过程, 大家应该很容易就能理解.
3.2.2,RR 旋转
RR 对应上面的图 3,RR 及造成 AVL 失衡的节点 6 在 20 节点的右侧的右侧, 即 RR. 对于 RR 我们要进行左旋转才能实现再平衡. 同样的, 我们如果想通过旋转达到再平衡, AVL 树的性质依然是我们实现这个操作的根本. 如上图 3 所示, 如果我们将 20 节点移到 29 元素的左孩子节点处, 便可实现再平衡. 而且也能维持 AVL 树的基本性质.
同分析 LL 一样, 我们增加一些虚拟节点来描述这个过程.
- ////////////////////////////////////////////////
- // RR T1<Y<T2< X <T3<Z<T4 //
- // y x //
- // / \ / \ //
- // T1 x 向左旋转 (y) y z //
- // / \ - - - - - - - -> / \ / \ //
- // T2 z T1 T2 T3 T4 //
- // / \ //
- // T3 T4 //
- ////////////////////////////////////////////////
节点间的大小关系: T1<Y<T2<X <T3<Z<T4. 对于 RR 我们对 Y 节点进行左旋转. 即让 Y 节点顶替 T2, 然后根据大小关系: Y < X < T2 可知, 我们可以将 T2 放到 Y 的右孩子节点处即可. 对 Y 节点左旋完了如上图所示的结果. 通过比较, 节点间的大小关系, 依然为: T1<Y<T2< X <T3<Z<T4. 通过对 Y 节点的左旋转, 达到了 AVL 的再平衡, 并维持了 AVL 的性质不变.
代码实现就不解释了
- private Node leftRotate(Node y) {
- Node x = y.right;
- Node T2 = x.left;
- // 向左旋转过程
- x.left = y;
- y.right = T2;
- return x;
- }
- 3.2.3,LR
LR 对应上图 2, 即造成 AVL 失衡的节点 14 在节点 20 的左侧的右侧, 即 LR. 这种情况有点复杂, 而且有个很想当然的坑, 就是将根节点直接换成 10 不就完事了? 可是如果我们这么做, 发现, 10 的左节点为 14, 不满足: 左孩子 < 父节点 < 右孩子的大小关系了. 这种情况呢, 正确的做法是先将 10 节点左旋, 然后再将 14 节点右旋. 大家通过之前对 LL 和 RR 的分析, 在脑子中能不能想象到这个画面呢?
为了方便描述, 我们依然增加一些虚假的节点来描述这个过程.
- //////////////////////////////////////////////////////////////////////////////////////////
- // LR T1<X<T2< Z <T3<Y<T4 //
- // y y z //
- // / \ / \ / \ //
- // x t4 向左旋转(x) z T4 向右旋转(y) x y //
- // / \ ---------------> / \ ---------------> / \ / \ //
- // T1 z x T3 T1 T2 T3 T4 //
- // / \ / \ //
- // T2 T3 T1 T2 //
- //////////////////////////////////////////////////////////////////////////////////////////
对于原始的这棵树呢, 大小关系: T1<X<T2<Z <T3<Y<T4. 如果我们先不看 Y 节点, 看 X,Z,T3 节点, 是不是可以发现, 这正是我们上面描述的 RR 的情况啊. 对 RR, 我们上面已经进行了详细的分析, 通过贵 X 节点进行左旋, 得到中间那棵树. 这时又一个神奇的事情发生了, 这棵树的形状又变成了前面我们说的, LL 的情况. 那大家就清楚了, 对 Y 节点进行右旋转即可. 最终的结果如上第三棵树, 达到了 AVL 的再平衡并依然满足: T1<X<T2< Z <T3<Y<T4.
我们发现经过我们的分析, 将这种复杂的情况进行一步步的拆解即分解成了比较简单的情况. 不得不感叹一下: 计算机的世界太神奇了.
3.2.4,RL
呃呵, 自己看吧, 不解释, 不接受反驳. 皮一下, 很开心.
- //////////////////////////////////////////////////////////////////////////////////////////
- // RL: T1<Y<T2< Z <T3<X<T4 //
- // y y z //
- // / \ / \ / \ //
- // T1 x 向右旋转(x) T1 z 向左旋转(y) y x //
- // / \ - - - - - - -> / \ - - - - - - - - -> / \ / \ //
- // z T4 T2 x T1 T2 T3 T4 //
- // / \ / \ //
- // T2 T3 T3 T4 //
- //////////////////////////////////////////////////////////////////////////////////////////
相信大家看到这里, 被面试官虐千百遍的问题, 原来不过如此. 其实一切高大上的问题, 只要我们耐心的看下去就能有收获.
3.3, 再平衡的时机
首先需要明白, AVL 的失衡是由于节点的变动引起的, 也就是增和删操作才会导致节点的变动. 下面我们结合平衡因子和插入或者删除的过程, 分析 AVL 再平衡的时机.
增加操作再平衡时机:
对于 3.2 章节中的过程, 希望大家可以清楚, 我们是通过眼睛观察来判断 AVL 是不是失衡了, 但是计算机还没有达到这种能力. 所以我们想想前面介绍的平衡因子, 正是判断 AVL 是不是平衡的重要依据. 假如现在向一棵空的 AVL 树依次插入[20,10,6]; 三个节点. 当插入 6 节点后, 如下图所示, 各个节点的高度. 之前说过: B = H 左 - H 右. 我们看一下 20 这个节点的平衡因子, B20 = 2 - 0 = 2> 1; 所以, 这时 20 就是不平衡的节点, 需要对 20 这个节点进行旋转才能再平衡. 但是从元素插入操作看一下, 很显然当插入 6 这个元素的时候, 并不知道 20 这个节点的平衡因子已经不满足要求了. 需要沿着添加的元素向上回溯, 沿着该节点到根节点的路径, 一步步的重新计算其父节点, 爷爷节点, 祖父节点... 当我们发现其父节点, 爷爷节点... 等平衡因子不满足要求的时候, 就对该节点进行旋转.
删除操作再平衡的时机:
删除操作进行再平衡的时机类似增加操作, 需要在删除节点后沿着其父节点, 爷爷节点... 一直向上计算各个节点的平衡因子是否满足 AVL 的性质. 当发现某个节点的平衡因子不在 [-1, 1] 之间的时候, 然后判断其形状对应的进行左旋转或者右旋转使其完成再平衡.
四, 代码实现一棵 AVL
在前面的章节详细介绍了 AVL 的定义, 失衡, 再平衡即 LL,RR,LR,RL 等旋转. 接下来我们通过代码实现一棵 AVL 树. 对于我们要实现的 AVL 平衡二叉树, 我们期待具备的功能如下:
以 Node 作为链表的基础存储结构
使用泛型, 并要求该泛型必须实现 Comparable 接口
基本操作: 增删改查
4.1,AVL 的基础代码
- /**
- * 描述: AVL 平衡二叉树的实现
- *
- * @Author shf
- * @Date 2019/7/31 15:35
- * @Version V1.0
- **/
- public class AVL<K extends Comparable<K>, V> {
- private class Node{
- public K key;
- public V value;
- public Node left, right;
- public int height;// 记录节点的高度
- public Node(K key, V value){
- this.key = key;
- this.value = value;
- left = null;
- right = null;
- height = 1;
- }
- }
- private Node root;
- private int size;
- public AVL(){
- root = null;
- size = 0;
- }
- public int getSize(){
- return size;
- }
- public boolean isEmpty(){
- return size == 0;
- }
- }
在实现增删改查之前我们先设计两个辅助方法, 如下所示, getHeight 方法获取节点的高度值, getBalanceFactor 方法获取节点的平衡因子.
- /**
- * 获得节点 node 的高度
- * @param node
- * @return
- */
- private int getHeight(Node node){
- if(node == null)
- return 0;
- return node.height;
- }
- /**
- * 获得节点 node 的平衡因子
- * @param node
- * @return
- */
- private int getBalanceFactor(Node node){
- if(node == null)
- return 0;
- return getHeight(node.left) - getHeight(node.right);
- }
4.2, 增
在《二分搜索树》介绍了二分搜索树, 前面根据 AVL 的定义可知, AVL 是完全满足一个二分搜索树的所有性质的, 如果大家想搞明白 AVL, 还是建议去先去看一下二分搜索树. 对于二分搜索树的添加操作的代码实现, 如下所示:
- /**
- * 添加元素
- * @param e
- */
- public void add(E e){
- root = add(root, e);
- }
- /**
- * 添加元素 - 递归实现
- * 时间复杂度 O(log n)
- * @param node
- * @param e
- * @return 返回根节点
- */
- public Node add(Node node, E e){
- if(node == null){// 如果当前节点为空, 则将要添加的节点放到当前节点处
- size ++;
- return new Node(e);
- }
- if(e.compareTo(node.e) <0){// 如果小于当前节点, 递归左孩子
- node.left = add(node.left, e);
- } else if(e.compareTo(node.e)> 0){// 如果大于当前节点, 递归右孩子
- node.right = add(node.right, e);
- }
- return node;
- }
如果你还没法理解上面的代码, 请移步《二分搜索树》. 对于 AVL 的添加操作, 无非就是在 AVL 中需要考虑在二分搜索树失衡的时候, 如何通过旋转达到再平衡. 根据我们前面的介绍, 我们应该已经很明白旋转的思路了, 那我们直接上代码吧.
- /**
- * 向以 node 为根的二分搜索树中插入元素(key, value), 递归算法
- * 时间复杂度 O(log n)
- * @param node
- * @param key
- * @param value
- * @return 返回插入新节点后二分搜索树的根
- */
- private Node add(Node node, K key, V value){
- if(node == null){
- size ++;
- return new Node(key, value);
- }
- if(key.compareTo(node.key) <0)
- node.left = add(node.left, key, value);
- else if(key.compareTo(node.key)> 0)
- node.right = add(node.right, key, value);
- else // key.compareTo(node.key) == 0
- node.value = value;
- // 更新 height
- node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));
- // 计算平衡因子
- int balanceFactor = getBalanceFactor(node);
- // 平衡维护
- //////////////////////////////////////////////////////
- // LL T1<Z<T2<X <T3<Y<T4 //
- // y x //
- // / \ / \ //
- // x T4 向右旋转 (y) z y //
- // / \ - - - - - - - -> / \ / \ //
- // z T3 T1 T2 T3 T4 //
- // / \ //
- // T1 T2 //
- //////////////////////////////////////////////////////
- if (balanceFactor> 1 && getBalanceFactor(node.left)>= 0)
- return rightRotate(node);
- //////////////////////////////////////////////////////////////////////////////////////////
- // LR T1<X<T2<Z <T3<Y<T4 //
- // y y z //
- // / \ / \ / \ //
- // x t4 向左旋转(x) z T4 向右旋转(y) x y //
- // / \ ---------------> / \ ---------------> / \ / \ //
- // T1 z x T3 T1 T2 T3 T4 //
- // / \ / \ //
- // T2 T3 T1 T2 //
- //////////////////////////////////////////////////////////////////////////////////////////
- if (balanceFactor> 1 && getBalanceFactor(node.left) <0) {
- node.left = leftRotate(node.left);
- return rightRotate(node);
- }
- //////////////////////////////////////////////////
- // RR: T1<Y<T2< X <T3<Z<T4 //
- // y x //
- // / \ / \ //
- // T1 x 向左旋转 (y) y z //
- // / \ - - - - - - - -> / \ / \ //
- // T2 z T1 T2 T3 T4 //
- // / \ //
- // T3 T4 //
- //////////////////////////////////////////////////
- if (balanceFactor <-1 && getBalanceFactor(node.right) <= 0)
- return leftRotate(node);
- //////////////////////////////////////////////////////////////////////////////////////////
- // RL: T1<Y<T2< Z <T3<X<T4 //
- // y y z //
- // / \ / \ / \ //
- // T1 x 向右旋转(x) T1 z 向左旋转(y) y x //
- // / \ - - - - - - -> / \ - - - - - - - - -> / \ / \ //
- // z T4 T2 x T1 T2 T3 T4 //
- // / \ / \ //
- // T2 T3 T3 T4 //
- //////////////////////////////////////////////////////////////////////////////////////////
- if (balanceFactor <-1 && getBalanceFactor(node.right)> 0) {
- node.right = rightRotate(node.right);
- return leftRotate(node);
- }
- return node;
- }
看上面代码, 辅之旋转示意图和平衡因子, 相信大家能通过自己的分析, 根据当前节点和左右孩子的平衡因子能判断出来是 LL,LR,RR, 或者 RL 的情况.
4.3, 左旋和右旋
至于左右旋转, 我们前文给出了代码, 但当我们对节点进行旋转以后, 我们需要重新维护一下各个节点的高度值. 所以经过完善的左右旋转的代码如下:
- /**
- * 对节点 y 进行向右旋转操作, 返回旋转后新的根节点 x
- * @param y
- * @return
- */
- ///////////////////////////////////////////////////
- // LL T1<Z<T2<X <T3<Y<T4 //
- // y x //
- // / \ / \ //
- // x T4 向右旋转 (y) z y //
- // / \ - - - - - - - -> / \ / \ //
- // z T3 T1 T2 T3 T4 //
- // / \ //
- // T1 T2 //
- ///////////////////////////////////////////////////
- private Node rightRotate(Node y) {
- Node x = y.left;
- Node T3 = x.right;
- // 向右旋转过程
- x.right = y;
- y.left = T3;
- // 更新 height
- y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
- x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
- return x;
- }
- /**
- * 对节点 y 进行向左旋转操作, 返回旋转后新的根节点 x
- * @param y
- * @return
- */
- ////////////////////////////////////////////////
- // RR T1<Y<T2<X <T3<Z<T4 //
- // y x //
- // / \ / \ //
- // T1 x 向左旋转 (y) y z //
- // / \ - - - - - - - -> / \ / \ //
- // T2 z T1 T2 T3 T4 //
- // / \ //
- // T3 T4 //
- ////////////////////////////////////////////////
- private Node leftRotate(Node y) {
- Node x = y.right;
- Node T2 = x.left;
- // 向左旋转过程
- x.left = y;
- y.right = T2;
- // 更新 height
- y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
- x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
- return x;
- }
4.4, 删
对于删除, 稍微复杂一点, 但是基本思路和增加是一样的. 但是关于我觉得还是有必要给大家恶补一下二分搜索树的删除的思路, 当我们删除一个节点的时候, 待删除节点左右子树有一个为空, 我们只需要将其不为空的子树的根节点提到待删除元素的位置即可. 如果其左右子树都不为空, 则将其右子树最小的元素提到待删除节点处. 详细的讨论请参阅《二分搜索树》, 在二分搜索树删除操作的基础上, 我们只需要辅之再平衡操作即可.
- /**
- * 从二分搜索树中删除键为 key 的节点
- * @param key
- * @return
- */
- public V remove(K key){
- Node node = getNode(root, key);
- if(node != null){
- root = remove(root, key);
- return node.value;
- }
- return null;
- }
- /**
- * 删除指定的节点
- * @param node
- * @param key
- * @return
- */
- private Node remove(Node node, K key){
- if( node == null )
- return null;
- Node retNode;
- if( key.compareTo(node.key) <0 ){
- node.left = remove(node.left , key);
- // return node;
- retNode = node;
- }
- else if(key.compareTo(node.key)> 0 ){
- node.right = remove(node.right, key);
- // return node;
- retNode = node;
- }
- else{ // key.compareTo(node.key) == 0 找到待删除的节点 node
- // 待删除节点左子树为空, 直接将右孩子替代当前节点
- if(node.left == null){
- Node rightNode = node.right;
- node.right = null;
- size --;
- // return rightNode;
- retNode = rightNode;
- }
- // 待删除节点右子树为空, 直接将左孩子替代当前节点
- else if(node.right == null){
- Node leftNode = node.left;
- node.left = null;
- size --;
- // return leftNode;
- retNode = leftNode;
- }
- // 待删除节点左右子树均不为空的情况
- else{
- // 待删除节点左右子树均不为空
- // 找到右子树最小的元素, 替代待删除节点
- Node successor = minimum(node.right);
- //successor.right = removeMin(node.right);
- successor.right = remove(node.right, successor.key);
- successor.left = node.left;
- node.left = node.right = null;
- // return successor;
- retNode = successor;
- }
- }
- if(retNode == null)
- return null;
- // 更新 height
- retNode.height = 1 + Math.max(getHeight(retNode.left), getHeight(retNode.right));
- // 计算平衡因子
- int balanceFactor = getBalanceFactor(retNode);
- // 平衡维护
- // LL
- if (balanceFactor> 1 && getBalanceFactor(retNode.left)>= 0)
- return rightRotate(retNode);
- // RR
- if (balanceFactor <-1 && getBalanceFactor(retNode.right) <= 0)
- return leftRotate(retNode);
- // LR
- if (balanceFactor> 1 && getBalanceFactor(retNode.left) <0) {
- retNode.left = leftRotate(retNode.left);
- return rightRotate(retNode);
- }
- // RL
- if (balanceFactor < -1 && getBalanceFactor(retNode.right)> 0) {
- retNode.right = rightRotate(retNode.right);
- return leftRotate(retNode);
- }
- return retNode;
- }
- /**
- * 返回以 node 为根的二分搜索树的最小值所在的节点
- * @param node
- * @return
- */
- private Node minimum(Node node){
- if(node.left == null)
- return node;
- return minimum(node.left);
- }
4.5, 其他操作
- /**
- * 返回以 node 为根节点的二分搜索树中, key 所在的节点
- * @param node
- * @param key
- * @return
- */
- private Node getNode(Node node, K key){
- if(node == null)
- return null;
- if(key.equals(node.key))
- return node;
- else if(key.compareTo(node.key) <0)
- return getNode(node.left, key);
- else // if(key.compareTo(node.key)> 0)
- return getNode(node.right, key);
- }
- /**
- * 判断是否包含 key
- * @param key
- * @return
- */
- public boolean contains(K key){
- return getNode(root, key) != null;
- }
- /**
- * 获取指定 key 的 value
- * @param key
- * @return
- */
- public V get(K key){
- Node node = getNode(root, key);
- return node == null ? null : node.value;
- }
- /**
- * 设置 key 对应元素的值 value
- * @param key
- * @param newValue
- */
- public void set(K key, V newValue){
- Node node = getNode(root, key);
- if(node == null)
- throw new IllegalArgumentException(key + "doesn't exist!");
- node.value = newValue;
- }
五, 验证 AVL
前面我们实现了一棵 AVL 树, 我们如何验证这到底是不是一棵 AVL 树呢? 这个问题, 我们依然是从其定义来思考, 首先, AVL 是一棵二分搜索树, 其次每个节点的平衡因子能满足在 [-1, 1] 之间, 能满足这两点其实加之我们代码的逻辑即可判断其是不是一棵 AVL 树了.
二分搜索树有一个延伸出来的性质不知道大家还记不记得, 对于二分搜索树的中序遍历, 其实是对二分搜索树从小到大排序的过程. 那我们判断中序遍历的结果满不满足从小到大即可判定其是不是一棵二分搜索树.
- /**
- * 测试方法 - 判断该二叉树是否是一棵二分搜索树
- * @return
- */
- public boolean isBST(){
- ArrayList<K> keys = new ArrayList<>();
- inOrder(root, keys);
- for(int i = 1 ; i <keys.size() ; i ++)
- if(keys.get(i - 1).compareTo(keys.get(i))> 0)
- return false;
- return true;
- }
- /**
- * 中序遍历
- * @param node
- * @param keys
- */
- private void inOrder(Node node, ArrayList<K> keys){
- if(node == null)
- return;
- inOrder(node.left, keys);
- keys.add(node.key);
- inOrder(node.right, keys);
- }
- /**
- * 测试方法 - 判断该二叉树是否是一棵平衡二叉树
- * @return
- */
- public boolean isBalanced(){
- return isBalanced(root);
- }
- /**
- * 判断以 Node 为根的二叉树是否是一棵平衡二叉树, 递归算法
- * @param node
- * @return
- */
- private boolean isBalanced(Node node){
- if(node == null)
- return true;
- int balanceFactor = getBalanceFactor(node);
- if(Math.abs(balanceFactor)> 1)
- return false;
- return isBalanced(node.left) && isBalanced(node.right);
- }
我们写如下测试代码:
- public class Main {
- public static void main(String[] args) {
- AVL<Integer, Integer> avl = new AVL<>();
- for (int i=0; i< 10; i++){
- avl.add(i, i);
- }
- System.out.println(avl.isBST());
- System.out.println(avl.isBalanced());
- avl.remove(5);
- System.out.println(avl.isBST());
- System.out.println(avl.isBalanced());
- }
- }
- true
- true
- true
- true
到此, AVL 所有的内容我们已经介绍完了. 哎呦, 凌晨三点了, 心疼自己一秒钟. 我爱我的国.
参考文献:
《玩转数据结构 - 从入门到进阶 - 刘宇波》
《数据结构与算法分析 - Java 语言描述》
如有错误的地方还请留言指正.
来源: https://www.cnblogs.com/hello-shf/p/11352071.html