AVL树（Java）

目录

一、什么是AVL树

二、AVL树的实现

AVL树的节点

AVL树的插入

AVL树的旋转

右单旋

左单旋

左右双旋

右左双旋

AVL树的验证

三、AVL树的性能分析

一、什么是AVL树

在了解什么是AVL树之前，我们先回顾二叉搜索树的概念

二叉搜索树（二叉排序树），它或是一棵空树，或具有以下性质：

1. 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值

2. 若它的右子树不为空，则右子树上所有节点的值都大于根节点

3. 它的左右子树也分别是二叉搜索树

根据二叉搜索树的性质，我们可以发现：

1. 二叉搜索树中最左侧的节点是树中最小的节点，最右侧的节点是树中最大的节点

2. 若采用中序遍历二叉搜索树，则可得到一个有序的序列

二叉搜索树最主要的作用就是用于进行查询：

当二叉搜索树是一颗完全二叉树时：

其查询的平均查找次数为:

而当二叉搜索树是一颗单支树时：

其平均查找次数为：

由此可见二叉搜索树的平均查找次数与二叉搜索树的深度成正相关，即深度越深，比较查找的次数越多。而当其是单支树时，二叉搜索树的性能就降低了，此时，能否对其进行改进，使其无论怎样插入，都能够使二叉搜索树的性能最佳？

AVL树的出现解决了这个问题。

ALV树（也就是平衡二叉查找树，简称平衡二叉树）或是一颗空树，或具有以下性质：

1. 它的左右子树高度之差（简称平衡因子）的绝对值不超过1

2. 它的左右子树都是AVL树

由AVL树的性质，我们可以发现：

1. 每当向AVL树中插入新的节点时，都要保证每个节点的左右子树高度差（平衡因子）的绝对值不超过1（当超过时需要对树中的节点进行调整，即降低树的高度，从而减少平均搜索长度）

2. 若一颗AVL树有n个节点，它的高度能够保持在，因此，其搜索的时间复杂度为O()

二、AVL树的实现

AVL树的节点

在这里，我们通过一个内部类来实现AVL树节点的定义，通过维护节点的左孩子、右孩子和父亲节点来实现AVL树，同时定义一个平衡因子bf，通过平衡因子来判断是否需要调整树中节点。同时，我们需要定义根节点：

public class AVLTree {static class TreeNode{public int val;//节点的值public int bf;//平衡因子public TreeNode left;//左孩子public TreeNode right;//右孩子public TreeNode parent;//父亲节点public TreeNode(int val){this.val = val;}}public TreeNode root;//根节点}

当前节点的平衡因子 = 右子树的高度 – 左子树的高度

AVL树的插入

AVL树就是在二叉搜索树的基础上引入了平衡因子，因此，我们可以将AVL树的插入过程分为两步：

1. 插入新的节点

2. 调整节点的平衡因子

现在我们对新的节点进行插入：

1. 当AVL树为空时，插入的节点即为根节点

2. AVL树不为空，则寻找新节点的插入位置

如何寻找新节点的插入位置？

若新节点node的值val > 当前节点cur的值val，则在cur的右子树寻找插入位置；

若node.val < cur.val，则在cur的左子树寻找插入位置；

若node.val = cur.val，则AVL树中已有该节点，插入失败，直接返回false

在找到插入位置后，我们需要知道其父亲节点，从而进行插入，因此在查找过程中，我们可以定义当前节点cur的父亲节点parent，用于最后进行插入新节点：

//节点的插入public boolean insert(int val){TreeNode node = new TreeNode(val);//若根节点为空，则直接将插入为根节点if(root == null){root = node;return true;}//根节点不为空，查找其插入位置TreeNode parent = null;TreeNode cur = root;while (cur != null){if(cur.val  val){parent = cur;cur = cur.left;}else{return false;//若已有该节点，则插入失败，直接返回false}}//将节点插入node.parent = parent;cur = node;} 

AVL树的旋转

在插入新的节点之后，此时AVL树中某些节点的平衡因子会发生改变，因此我们需要对平衡因子进行修改，而在插入新节点后，节点的平衡因子的绝对值可能超过1，此时我们需要对节点进行调整

我们首先对平衡因子进行修改：

在插入新节点时，我们定义了其父亲节点parent，由于在这里平衡因子 = 右子树的高度 – 左子树的高度

因此，若新插入的节点在parent的左子树，则其平衡因子 -1；而若新插入的节点在parent的右子树，则平衡因子 +1

在修改完当前平衡因子后，我们需要对当前平衡因子进行检查，判断其是否符合条件：

1.若修改后的平衡因子 = 0，则表明未修改时parent的平衡因子bf = 1 或 -1，在插入后被调整成为0，此时子树parent已经平衡了，且其高度并未发生改变，不会影响上面节点的平衡因子，因此不用再继续向上判断

2. 若修改后的平衡因子 = 1 或 -1，则表明未修改时parent的平衡因子bf = 0，在插入之后被调整成 1 或 -1，此时子树parent的高度增加，上面节点的平衡因子也会被影响，因此需要继续向上更新平衡因子

3. 若修改后的平衡因子的绝对值 > 1，此时则需要对AVL树的节点进行调整，重新使其平衡

在这里，我们通过旋转来调整节点的平衡因子，AVL树的旋转分为四种情况：

右单旋

（1）新节点插入较高左子树的左侧->右单旋

当新节点插入较高左子树的左侧时：

此时 patent.bf = -2, cur.bf = -1，要想办法降低左子树的高度，因此对其进行调整：

将对于以parent 为根的子树：

将cur作为其根；parent作为cur的右子树；cur原右子树（若有的话）作为parent的左子树，

这样重新调整后，cur和parent的平衡因子都被调整为0，此时以cur为根的子树已经平衡

因此，我们调整的步骤为：

我们设parent的左孩子cur为subL，cur的右孩子为subLR（因为要考虑cur的右孩子不存在的情况）

1. 将parent的左孩子更新为subLR，将subLR的父亲节点更新为parent

注：此时要考虑subLR为空的情况，若subLR为空，则不需要更新

2. 将subL的右孩子更新为parent，将parent的父亲节点更新为subL

注：在更新parent的父亲节点时，我们首先要将parent的父亲节点pParent保存起来，因为我们需要将subL的父亲节点更新为parent的父亲节点

3. 更新subL的父亲节点，

若parent原为根节点，此时需要将根节点更新为subL，同时将subL的父亲节点更新为null；

若parent原不为根节点，则更新subL的父亲节点为pParent，同时需要更新pParent的孩子节点，此时需要判断parent为pParent的左孩子还是右孩子，并更新

右单旋代码：

//右单旋private void rotateRight(TreeNode parent){TreeNode subL = parent.left;TreeNode subLR = subL.right;parent.left = subLR;if(subLR != null){//只有当subLR不为空时，才能修改其父亲节点subLR.parent = parent;}subL.right = parent;//在修改parent的父亲节点时，必须先记录其父亲节点，以便修改subL的父亲节点TreeNode pParent = parent.parent;parent.parent = subL;//判断subL是否被修改为根节点if(parent == root){root = subL;root.parent = null;}else {subL.parent = pParent;//判断是左子树还是右子树if(pParent.left == parent){pParent.left = subL;}else {parent.right = subL;}}//修改平衡因子subL.bf = 0;parent.bf = 0;}

左单旋

新节点插入较高右子树的右侧->左单旋

左单旋与右单旋类似：

当新的节点插入到较高右子树的右侧时：

此时parent.bf = 2, cur.bf = 1，要想办法降低右子树的高度，对以parent为根的子树进行调整：

设parent的右孩子cur为subR，subR的左孩子为subRL（要考虑subR的左孩子为空的情况）

1. 将parent的右孩子更新为subRL，将subRL的父亲节点更新为parent（若subRL不为空）

2. 将subR的左孩子更新为parent，保存parent的父亲节点pParent，再更新parent的父亲节点为subR

3. 更新subR的父亲节点，若parent原为根节点，则更新根节点为subR，并将其父亲节点更新为null；若parent原不为根节点，则更新subR的父亲节点为pParent，判断parent原为pParent的左孩子还是右孩子，并将subR更新为pParent的孩子节点

左单旋代码：

//左单旋private void rotateLeft(TreeNode parent){TreeNode subR = parent.right;TreeNode subRL = subR.left;parent.right = subRL;if(subRL != null){//只有当subRL不为空时，才能修改其父亲节点subRL.parent = parent;}subR.left = parent;//在修改parent父亲节点前将其进行记录，以便后续修改subR的父亲节点TreeNode pParent = parent.parent;parent.parent = subR;//判断subR是否被修改为根节点if(parent == root){root = subR;root.parent = null;}else {//判断是其左子树还是右子树if(pParent.left == parent){pParent.left = subR;}else{pParent.right = subR;}subR.parent = pParent;}//修改平衡因子subR.bf = 0;parent.bf = 0;}

左右双旋

新节点插入较高左子树的右侧->左右双旋（先左单旋再右单旋）

当新的节点插入较高左子树的右侧时：

此时 parent.bf = -2, cur.bf = 1，此时对于以parent为根的子树，无论是进行右单旋，还是进行左单旋，都不能使其平衡。因此，此时不能只进行一次旋转，而需要进行两次旋转：
首先，我们需要对以cur为根的子树进行一次左单旋：

然后再对以parent为根的子树进行一次右单旋：

此时调整后的子树达到平衡状态，由于进行的左单旋和右单旋会更改其中节点的平衡因子，因此我们需要对被修改的平衡因子进行重新调整：

平衡因子被修改的节点有：parent、parent的左孩子subL、subL的右孩子subLR

它们的平衡因子都被修改为0，

然而经过两次旋转后，它们的平衡因子并不都为0

通过观察我们发现，当subLR的平衡因子原为-1时，经过调整后，parent的平衡更新为1

当subLR的平衡因子原为1时，经过调整后，subL的平衡因子被更新为-1：

当subLR的平衡因子原为0时，经过调整后，parent、subL和subLR的平衡因子都为0：

因此，我们根据subLR原平衡因子来调整旋转两次之后的平衡因子

为什么subLR的平衡因子不同，两次旋转后的平衡因子也不同呢？

当subLR的平衡因子为-1时，经过一次左单旋，subRL的左子树变为subR的右子树，由于subR的平衡因子为1，经过这次左旋后，其右子树的高度减一（少了subRL），此时subR的平衡因子变为0，且subRL变为subR的父亲节点。

当subLR变为subR的父亲节点时，其平衡因子变为 -2 ，这是因为subRL的原平衡因子为-1，经过一次左旋后，其左子树高度增加1（增加了subR），右子树高度不变，因此平衡因子变为 -2。

而parent的平衡因子不变，仍是 -2，这是因为在经过一次左单旋后，其右子树高度不变，虽其左孩子变为了subRL，但其高度未改变，因此parent的平衡因子不变

其过程更新过程如下图：

此时，我们假设subLR的左子树高度为m，由于其平衡因子为-2，则subLR的右子树高度为m-2，而parent的左子树高度为m+1，parent的右子树高度为m-1

当进行一次右旋后，由于subR的左右子树不变，因此其平衡因子仍为0

而parent变为subLR的右子树，且其左子树变为subLR的右子树，parent的右子树高度未改变，任为m – 1，而parent的左子树变为subLR的右子树，因此其高度变为m-2，则parent子树的高度为m-1，平衡因子变为 1

subLR的左子树为改变，高度任为m，而右子树变为以parent为根的子树，parent子树的高度为m-1，再加上parent，则为m，因此subLR的平衡因子变为0

当subLR的平衡因子为1和为0时也是同样的分析过程，大家可自行进行分析，这里就不再进行分析了

左右双旋代码：

//左右双旋private void rotateLR(TreeNode parent){TreeNode subL = parent.left;TreeNode subLR = subL.right;//记录subLR平衡因子int bf = subLR.bf;rotateLeft(parent.left);//先左旋rotateRight(parent);//再右旋//修改平衡因子if(bf == -1){parent.bf = 1;}else if(bf == 1){subL.bf = -1;}}

右左双旋

新节点插入较高右子树的左侧->右左双旋（先右单旋再左单旋）

右左双旋与左右双旋的情况类似

当新节点插入较高右子树的左侧时：

此时 parent.bf = 2, cur.bf = -1，仍要进行两次旋转，才能将以parent为根的子树调整为平衡的子树

此时要先对其进行右旋：

再对其进行左旋：

最后，我们再根据原subRL的平衡因子对平衡因子对其修改：

当subRL原平衡因子为1时，更新后的parent的平衡因子为-1

当subRL原平衡因子为-1时，更新后的subR的平衡因子为1

当subRL原平衡因子为0时，更新后parent、subR和subRL的平衡因子都为0

右左双旋的代码为：

//右左双旋private void rotateRL(TreeNode parent){TreeNode subR = parent.right;TreeNode subRL = subR.left;//记录subRL的平衡因子int bf = subRL.bf;rotateRight(subR);//先右旋rotateLeft(parent);//再左旋//修改平衡因子if(bf == 1){parent.bf = -1;}else if(bf == -1){subR.bf = 1;}}

由上述四种旋转过程可知：经过旋转后，都能使节点的平衡因子到达平衡，此时无需再向上调整，因此修改平衡因子的代码为：

//修改平衡因子//平衡因子 = 右子树高度 - 左子树高度while (parent != null){//判断cur是parent的左还是右，从而决定其平衡因子是++还是--if(cur == parent.right){parent.bf++;}else {parent.bf--;}//检查当前平衡因子 判断是否符合条件（-1 0 1）if(parent.bf == 0){//已经平衡break;}else if(parent.bf == 1 || parent.bf == -1){//需要继续向上判断是否需要修改平衡因子cur = parent;parent = cur.parent;}else {//不平衡，需要进行旋转，使其平衡if(parent.bf == 2){//右树高，需要左旋，从而降低右树高度if(cur.bf == 1){ //直接左旋rotateLeft(parent);}else {//右左双旋rotateRL(parent);}}else {//左树高，需要右旋，从而降低左树高度if(cur.bf == -1){//直接右旋rotateRight(parent);}else {//左右双旋rotateLR(parent);}}//旋转之后，平衡break;}}

AVL树的验证

在我们插入节点后，如何验证我们创建出的树是否是AVL树？

AVL树是高度平衡的二叉搜索树，其平衡因子的绝对值不超过1，能否通过节点的平衡因子来验证？

不能通过平衡因子来验证，因为平衡因子是我们通过计算得出的，若我们在计算时出现错误，那我们通过平衡因子验证的结果也是错误的（例如在左右双旋时，未在最后修改平衡因子，则此时计算的平衡因子不完全正确）

那么我们应该如何进行验证呢？

首先，AVL树也是二叉搜索树，二叉搜索树中序遍历的结果是有序的，因此我们可以通过中序遍历来验证

public void inorder(TreeNode root) {if(root == null) return;inorder(root.left);System.out.print(root.val+" ");inorder(root.right);}

其次，AVL树节点的平衡因子绝对值不超过1，即左右子树的高度差不超过1，我们可以通过计算左右子树的高度差来判断树是否是高度平衡的，同时，通过比较计算出的高度差和平衡因子，我们也可以验证当前节点的平衡因子是否正确

private int height(TreeNode root) {//计算子树高度if(root == null) return 0;int leftH = height(root.left);int rightH = height(root.right);return leftH > rightH " />

完整代码：

public class AVLTree {static class TreeNode{public int val;//节点的值public int bf;//平衡因子public TreeNode left;//左孩子public TreeNode right;//右孩子public TreeNode parent;//父亲节点public TreeNode(int val){this.val = val;}}public TreeNode root;//根节点//节点的插入public boolean insert(int val) {TreeNode node = new TreeNode(val);//若根节点为空，则直接将插入为根节点if (root == null) {root = node;return true;}//根节点不为空，查找其插入位置TreeNode parent = null;TreeNode cur = root;while (cur != null) {if (cur.val  val) {parent = cur;cur = cur.left;} else {return false;//若已有该节点，则插入失败，直接返回false}}//将节点插入node.parent = parent;cur = node;//修改平衡因子//平衡因子 = 右子树高度 - 左子树高度while (parent != null){//判断cur是parent的左还是右，从而决定其平衡因子是++还是--if(cur == parent.right){parent.bf++;}else {parent.bf--;}//检查当前平衡因子 判断是否符合条件（-1 0 1）if(parent.bf == 0){//已经平衡break;}else if(parent.bf == 1 || parent.bf == -1){//需要继续向上判断是否需要修改平衡因子cur = parent;parent = cur.parent;}else {//不平衡，需要进行旋转，使其平衡if(parent.bf == 2){//右树高，需要左旋，从而降低右树高度if(cur.bf == 1){ //直接左旋rotateLeft(parent);}else {//先右旋，再左旋rotateRL(parent);}}else {//左树高，需要右旋，从而降低左树高度if(cur.bf == -1){//直接右旋rotateRight(parent);}else {//先左选，再右旋rotateLR(parent);}}//经过旋转之后，就平衡break;}}return true;}//左单旋private void rotateLeft(TreeNode parent){TreeNode subR = parent.right;TreeNode subRL = subR.left;parent.right = subRL;if(subRL != null){//只有当subRL不为空时，才能修改其父亲节点subRL.parent = parent;}subR.left = parent;//在修改parent父亲节点前将其进行记录，以便后续修改subR的父亲节点TreeNode pParent = parent.parent;parent.parent = subR;//判断subR是否被修改为根节点if(parent == root){root = subR;root.parent = null;}else {//判断是其左子树还是右子树if(pParent.left == parent){pParent.left = subR;}else{pParent.right = subR;}subR.parent = pParent;}//修改平衡因子subR.bf = 0;parent.bf = 0;}//右单旋private void rotateRight(TreeNode parent){TreeNode subL = parent.left;TreeNode subLR = subL.right;parent.left = subLR;if(subLR != null){//只有当subLR不为空时，才能修改其父亲节点subLR.parent = parent;}subL.right = parent;//在修改parent的父亲节点时，必须先记录其父亲节点，以便修改subL的父亲节点TreeNode pParent = parent.parent;parent.parent = subL;//判断subL是否被修改为根节点if(parent == root){root = subL;root.parent = null;}else {subL.parent = pParent;//判断是左子树还是右子树if(pParent.left == parent){pParent.left = subL;}else {parent.right = subL;}}//修改平衡因子subL.bf = 0;parent.bf = 0;}//左右双旋private void rotateLR(TreeNode parent){TreeNode subL = parent.left;TreeNode subLR = subL.right;//记录subLR平衡因子int bf = subLR.bf;rotateLeft(parent.left);//先左旋rotateRight(parent);//再右旋//修改平衡因子if(bf == -1){parent.bf = 1;}else if(bf == 1){subL.bf = -1;}}//右左双旋private void rotateRL(TreeNode parent){TreeNode subR = parent.right;TreeNode subRL = subR.left;//记录subRL的平衡因子int bf = subRL.bf;rotateRight(subR);//先右旋rotateLeft(parent);//再左旋//修改平衡因子if(bf == 1){parent.bf = -1;}else if(bf == -1){subR.bf = 1;}}//验证public void inorder(TreeNode root) {//中序遍历if (root == null) return;inorder(root.left);System.out.print(root.val + " ");inorder(root.right);}private int height(TreeNode root) {//计算子树高度if(root == null) return 0;int leftH = height(root.left);int rightH = height(root.right);return leftH > rightH ? leftH+1 : rightH+1;}public boolean isBalanced(TreeNode root) {if(root == null) return true;int leftH = height(root.left);int rightH = height(root.right);//判断平衡因子是否正确if(rightH-leftH != root.bf) {System.out.println("节点："+root.val+" 平衡因子异常");return false;}//判断左右子树高度差绝对值是否不超过1return Math.abs(leftH-rightH) <= 1&& isBalanced(root.left)&& isBalanced(root.right);}}

三、AVL树的性能分析

AVL树是一颗绝对平衡的二叉搜索树，要求每个节点的左右子树高度差的绝对值都不超过1，这样能够保证查询时的高效，即查询的时间复杂度为O（）。但当对AVL树进行一些结构的修改操作时，性能就会比较低下（在插入时为了保持其绝对平衡，就需要进行旋转）。因此，若需要一种查询高效且有序的数据结构，且数据的个数为静态的（不改变），可以考虑使用AVL树，但若是其经常进行修改，就不太适合使用AVL树。