JavaDS —— AVL树

前言

本文章将介绍 AVL 树的概念，重点介绍AVL 树的插入代码是如何实现的，如果大家对 AVL 树的删除（还是和二叉搜索树一样使用的是替换删除法，然后需要判断是否进行旋转调整）感兴趣的话，可以自行去翻阅其他资料~~

概念

回顾二叉搜索树

之前我们就了解到二叉搜索树中序遍历的时候数据是有序的，这是由于二分搜索树具有以下性质：
若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
它的左右子树也分别为二叉搜索树

最好的搜索时间复杂度为 O(logN)，但是如果插入的数据是有序或者逆序的时候，二叉搜索树就会变成一颗单分支的二叉树，搜索的时间复杂度也最差，为 O(N)

那么能不能让二叉搜索树在插入结点的时候就能始终保持平衡，也就是保持一颗饱满的二叉树形态呢？

这就是我们要学习的 AVL 树

AVL 树

两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年 发明了一种解决上述二叉搜索树存在的问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

一棵AVL树具有以下性质：
AVL 树同时具有二叉搜索树的性质
它的左右子树都是AVL树
左右子树高度之差(简称平衡因子)的绝对值不超过 1 (-1、0、1)，即始终保持高度平衡

如果一棵二叉搜索树是高度平衡的，它就是AVL树。

平衡因子

平衡因子就是左右子树高度之差

这里我定义平衡因子等于右子树高度减去左子树的高度

以下图为例：

A 结点右子树高度等于左子树高度，平衡因子为0
B 结点右子树高度减左子树高度等于 -1，平衡因子为 -1
C 结点右子树高度减左子树高度等于 1，平衡因子为 1
D 结点右子树高度等于左子树高度，平衡因子为0
E 结点右子树高度等于左子树高度，平衡因子为0

结点定义

和普通的树结点一样，具有左引用，右引用，数据val，以及构造方法
但是 AVL 树还要再加一个平衡因子（Balance Factor）简写为 bf
还有一个双亲结点的引用（和平衡因子一样，插入的时候要用到）

public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode parent;int bf; //平衡因子 右子树高度减去左子树高度public TreeNode(int val) {this.val = val;}
}

插入实现

首先完成结点的插入工作，这里的插入和之前我们在二叉搜索树已经学习过，这里就直接上代码，如果不了解的可以点开这个连接：JavaDS —— 二叉搜索树、哈希表、Map 与 Set

    public boolean insert(int val) {TreeNode node = new TreeNode(val);//如果根节点本身为空就直接赋值if(root == null) {root = node;return true;}TreeNode prev = null;TreeNode cur = root;//找到新结点的位置while(cur != null) {if(cur.val == val) {//相同的数据无法再次插入return false;} else if(cur.val < val) {prev = cur;cur = cur.right;} else {prev = cur;cur = cur.left;}}//插入结点if(prev.val > val) {prev.left = node;} else {prev.right = node;}node.parent = prev;}

---

现在就是调整平衡因子（这里我设定为右子树高度减左子树高度），如果你是插入到左子树的话，那平衡因子就要自减，如果是插入到右子树的话，那平衡因子就要自增。

首先就要先拿到 node 的位置，将cur 重置为 node

cur = node;

			//左子树-- 右子树++if(prev.left == cur) {prev.bf--;} else {prev.bf++;}

---

调节完平衡因子之后，此时调节过的平衡因子有五种情况：0 、1 、-1 、2 、-2

如下图所示：红色的结点为新插入的结点，灰色的结点则是已经存在的

---

如果调节过后，平衡因子依旧为 0 ，则说明该树本身就已经平衡了，不需要进行旋转调整.

如果调节过后的平衡因子为 1 或者 -1，说明该结点的兄弟结点为空，这个结点的插入可能会导致不平衡，需要我们继续向上调整平衡因子，这时候我们会使用 parent 引用，让prev 和 cur 一起向上移动，大家就会想到使用循环来调整平衡因子。

循环的部分代码如下：

        cur = node;//调整平衡因子与AVL树while(prev != null) {//左子树-- 右子树++if(prev.left == cur) {prev.bf--;} else {prev.bf++;}//检查是否需要旋转if(prev.bf == 0) {//平衡因子为0，说明树已经平衡，不用调整break;} else if(prev.bf == -1 || prev.bf == 1) {//如果出现 -1 或者 1 则说明树的平衡性已经被新结点影响到，需要继续调整cur = prev;prev = prev.parent;}}

如果调节过后的平衡因子为 2 或者 -2，说明该树出现不平衡，需要进行旋转调整

大家可以记一下旋转的口诀，旋转内容会在下面继续讲解：

左左型：右单旋
右右型：左单旋
左右型：左右双旋
右左型：右左双选

 		else {//此时怕平衡因子有两种情况2 或者 -2，需要旋转重新建立平衡树if(prev.bf == 2) {//说明右子树过高if(cur.bf == 1) {//右右型 左单旋rotateLeft(prev);} else if(cur.bf == -1) {//右左型 右左双旋rotateRL(prev);}} else {//此时 prev.bf == -2 说明左子树过高if(cur.bf == 1) {//左右型，左右双旋rotateLR(prev);} else if(cur.bf == -1) {//左左型， 右单旋rotateRight(prev);}}//旋转完成后，树已经平衡，直接退出循环break;}

经过旋转过后，树就会平衡，就无需继续调整平衡因子，直接跳出循环即可。

旋转实现

下面所有的实例图绿色的数字表示经过旋转后平衡因子变为多少

左单旋

当新插入的结点插在某个结点的右孩子的右子树时（这个简称为右右型），那么这个某个结点采用左单旋：

简单情况：

我们需要让 prev 成为 cur 的左孩子，这时候我们需要修改 prev 的 parent 引用， cur 的左孩子引用以及parent 引用，并且cur 结点的 parent 引用需要改成原来 prev 的parent引用（记为 pParent），所以我们事先就要保存好pParent，最后我们要将pParent 的左引用或者右引用 来连接cur （这里需要判断一下），最后的最后这两个结点的平衡因子置为 0

特殊情况：如果prev 本身就是 根节点的话，那么根节点的引用要变成 cur 的。

如果 cur 的左孩子本身就存在呢？

那么我们需要将 cur 左孩子结点先保存起来，让 prev.right = cur 的左孩子结点，并且左孩子结点的 parent 的引用要修改为 prev，所以这里引申出我们需要判断 cur 的左孩子结点存不存在，如果不存在则不需要修改其 parent 引用，避免发生空指针异常

    //左单旋private void rotateLeft(TreeNode prev) {TreeNode pParent = prev.parent;TreeNode cur = prev.right;TreeNode curL = cur.left;prev.right = curL;if(curL != null) {curL.parent = prev;}cur.left = prev;prev.parent = cur;cur.parent = pParent;if(prev == root) {root = cur;} else if(pParent.left == prev) {pParent.left = cur;} else {pParent.right = cur;}//调整平衡因子cur.bf = prev.bf = 0;}

右单旋

当新插入的结点插在某个结点的左孩子的左子树时（这个简称为左左型），那么这个某个结点采用右单旋：

简单情况：

这个和左单旋很相似，大家可以类比左单旋。

特殊情况：如果 prev 本身就是根节点的话就要修改根结点的引用。

还有，如果 cur 自身就有右孩子：让 prev.left = cur 的右孩子结点，并且判断右孩子结点是否为空，不为空的话将 parent 的引用要修改为 prev，

    //右单旋private void rotateRight(TreeNode prev) {TreeNode pParent = prev.parent;TreeNode cur = prev.left;TreeNode curR = cur.right;prev.left = curR;if(curR != null) {curR.parent = prev;}cur.right = prev;prev.parent = cur;cur.parent = pParent;if(prev == root) {root = cur;} else if(pParent.left == prev) {pParent.left = cur;} else {pParent.right = cur;}//调整平衡因子cur.bf = prev.bf = 0;}

左右双旋

当新插入的结点插在某个结点的左孩子的右子树时（这个简称为左右型），那么这个某个结点采用左右双旋：

简单情况：

左右双旋是指先进行左单旋，再进行右单旋，当然你也可以一步到位，我这里采用分步
所以左右双旋需要先对 cur 调用左单旋，再对 prev 调用右单旋

特殊情况：由于在单旋代码中我们已经处理好根节点和prev 的parent 结点了，但是这三个结点的平衡因子最后一定是 0 吗？？？
这次我们讨论的是如果是下面两种复杂的情况时，我们就需要修改一下某些结点的平衡因子：


进行完两个单旋转后，最后这三个结点的平衡因子都为0，但是看到上面的情况之后，其实并不是都为0，所以我们在进行旋转的时候就要先保存好cur 的右孩子的平衡因子，等到旋转结束后，就要调整平衡因子。

当 cur.right.bf = -1 时，prev.bf = 1；
当 cur.right.bf = 1 时，cur.bf = -1

    //左右双旋private void rotateLR(TreeNode prev) {TreeNode cur = prev.left;TreeNode curR = cur.right;int bf = curR.bf;rotateLeft(cur);rotateRight(prev);//调整平衡因子if(bf == 1) {cur.bf = -1;} else if(bf == -1) {prev.bf = 1;}//bf 为 0 的时候，不需要调整}

右左双旋

当新插入的结点插在某个结点的右孩子的左子树时（这个简称为右左型），那么这个某个结点采用右左双旋：

和左右双旋是类似的，这里就给出三种情况的图片给大家参考：
简单情况：

特殊情况：
当 cur.left.bf = -1 时，cur.bf = 1；

---

当 cur.left.bf = 1 时，prev.bf = -1；

    //右左双旋private void rotateRL(TreeNode prev) {TreeNode cur = prev.right;TreeNode curL = cur.left;int bf = curL.bf;rotateRight(cur);rotateLeft(prev);//调整平衡因子if(bf == 1) {prev.bf = -1;} else if(bf == -1) {cur.bf = 1;}//bf 为 0 的时候，不需要调整}

测试

写好AVL 树，记得测试自己的代码有没有错误，这里要测试两个东西，第一个是中序遍历的时候是否有序（检测是否为二叉搜索树），第二个东西就是平衡因子有没有错误以及是否是一个高度平衡的二叉树（因为都与高度有关，所以可以放在同一个方法里去写测试代码）。

性能分析

AVL 树始终都能保持高度的平衡（即左右子树的高度差<= 1），所以在搜索数据的时候，时间复杂度为O(log N)，举个例子：加上有10亿个数据，需要在其中找到一个数据，如果使用 AVL 树，2的30次方等于1,073,741,824，所以最多只需要查找30次就能找到目标值，可见AVL 树在查找中的优秀表现。

由于AVL树在插入和删除的时候，会进行旋转调整，这也就意味着大量时间和资源的消耗，所以AVL 树比较适合静态数据的查找，如果数据涉及大量的删除或者插入就会导致AVL 树的效率下降，这也就是为什么现在AVL 树应用范围比较小。

最终代码

public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode parent;int bf; //平衡因子 右子树高度减去左子树高度public TreeNode(int val) {this.val = val;}
}public class AVLTree {public TreeNode root;public boolean insert(int val) {TreeNode node = new TreeNode(val);//如果根节点本身为空就直接赋值if(root == null) {root = node;return true;}TreeNode prev = null;TreeNode cur = root;//找到新结点的位置while(cur != null) {if(cur.val == val) {//相同的数据无法再次插入return false;} else if(cur.val < val) {prev = cur;cur = cur.right;} else {prev = cur;cur = cur.left;}}//插入结点if(prev.val > val) {prev.left = node;} else {prev.right = node;}node.parent = prev;cur = node;//调整平衡因子与AVL树while(prev != null) {//左子树-- 右子树++if(prev.left == cur) {prev.bf--;} else {prev.bf++;}//检查是否需要旋转if(prev.bf == 0) {//平衡因子为0，说明树已经平衡，不用调整break;} else if(prev.bf == -1 || prev.bf == 1) {//如果出现 -1 或者 1 则说明树的平衡性已经被新结点影响到，需要继续调整cur = prev;prev = prev.parent;} else {//此时怕平衡因子有两种情况2 或者 -2，需要旋转重新建立平衡树if(prev.bf == 2) {//说明右子树过高if(cur.bf == 1) {//右右型 左单旋rotateLeft(prev);} else if(cur.bf == -1) {//右左型 右左双旋rotateRL(prev);}} else {//此时 prev.bf == -2 说明左子树过高if(cur.bf == 1) {//左右型，左右双旋rotateLR(prev);} else if(cur.bf == -1) {//左左型， 右单旋rotateRight(prev);}}//旋转完成后，树已经平衡，直接退出循环break;}}return true;}//左右双旋private void rotateLR(TreeNode prev) {TreeNode cur = prev.left;TreeNode curR = cur.right;int bf = curR.bf;rotateLeft(cur);rotateRight(prev);//调整平衡因子if(bf == 1) {cur.bf = -1;} else if(bf == -1) {prev.bf = 1;}//bf 为 0 的时候，不需要调整}//右左双旋private void rotateRL(TreeNode prev) {TreeNode cur = prev.right;TreeNode curL = cur.left;int bf = curL.bf;rotateRight(cur);rotateLeft(prev);//调整平衡因子if(bf == 1) {prev.bf = -1;} else if(bf == -1) {cur.bf = 1;}//bf 为 0 的时候，不需要调整}//右单旋private void rotateRight(TreeNode prev) {TreeNode pParent = prev.parent;TreeNode cur = prev.left;TreeNode curR = cur.right;prev.left = curR;if(curR != null) {curR.parent = prev;}cur.right = prev;prev.parent = cur;cur.parent = pParent;if(prev == root) {root = cur;} else if(pParent.left == prev) {pParent.left = cur;} else {pParent.right = cur;}//调整平衡因子cur.bf = prev.bf = 0;}//左单旋private void rotateLeft(TreeNode prev) {TreeNode pParent = prev.parent;TreeNode cur = prev.right;TreeNode curL = cur.left;prev.right = curL;if(curL != null) {curL.parent = prev;}cur.left = prev;prev.parent = cur;cur.parent = pParent;if(prev == root) {root = cur;} else if(pParent.left == prev) {pParent.left = cur;} else {pParent.right = cur;}//调整平衡因子cur.bf = prev.bf = 0;}
}