当前位置：首页 > ai >正文

Java数据结构第二十四期：探秘 AVL 树，当二叉搜索树学会 “自我调节”

ai 2025/6/24 10:31:09

专栏：Java数据结构秘籍

个人主页：手握风云

一、二叉搜索树的回顾

二、AVL树

2.1. 概念

2.2. 节点的定义

2.3. AVL 树的插入

2.4. AVL树的旋转

2.5. AVL树的验证

2.6. AVL的性能分析

一、二叉搜索树的回顾

二叉搜索树又称二叉排序树。当这棵树不为空时，如果左子树不为空，则左子树上所有节点的值均小于它的根节点的值；如果右子树不为空，则右子树上所有节点的值均大于它的根节点的值。当二叉搜索树进行中序遍历时，得到一个有序数组。

对二叉搜索树进行查找和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。最优情况下，二叉搜索树为完全二叉树，其平均比较次数为： $logn$ ；最差情况下，二叉搜索树退化为单支树，相当于在顺序表中寻找元素，其平均比较次数为： $N/2$ 。

二、AVL树

2.1. 概念

当二叉搜索树里的元素接近有序时，查找和删除效率低下。在1962年，苏联科学家G.M. Adelson-Velsky和E.M. Landis提出一种自平衡的二叉搜索树，AVL树：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

AVL树不为空树时具有以下性质：1.具有二叉搜索树的性质；2.每个节点的左右子树高度差（平衡因子）的绝对值不超过1；3.AVL树的每个子树也必须是AVL树。

如果一棵AVL树有n个节点，其高度可保持在 $O(logn)$ ，搜索时间复杂度 $O(logn)$ 。

在AVL树中，平衡因子是每个节点的一个属性，用来衡量该节点的左右子树的高度差，定义为一个节点的左子树的高度减去它的右子树的高度。

2.2. 节点的定义

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;}}
}

不是每棵树都必须有平衡因子，这只是其中的一种实现方式。

2.3. AVL 树的插入

AVL树的插入先按照二叉搜索树的插入方式，然后再根据平衡因子来进行调整。如果说整棵树为空，那么新插进入的结点则定义为根结点。

        // 如果根节点为空，则创建一个新的节点作为根节点TreeNode node = new TreeNode(val);if (root == null) {root = node;return true;}

当我们要插入值为10结点时，先定义一个cur引用指向root，当cur.val>val时，让cur引用指向当前结点的右孩子结点；当cur.val=val时，返回false；当cur.val<val时，让cur引用指向当前结点的左孩子结点。我们还需要定义一个p引用用来保存cur的上一个引用。

        TreeNode parent = null;TreeNode cur = root;while (cur != null) {// 如果当前节点的值小于要插入的值，则向右子树遍历if (cur.val < val) {parent = cur;cur = cur.right;// 如果当前节点的值等于要插入的值，则返回false} else if (cur.val == val) {return false;// 如果当前节点的值大于要插入的值，则向左子树遍历} else {parent = cur;cur = cur.left;}}// 如果要插入的值大于父节点的值，则将新节点插入到父节点的右子树if (parent.val < val) {parent.right = node;// 如果要插入的值小于父节点的值，则将新节点插入到父节点的左子树} else {parent.left = node;}

完成插入之后，结果就会如下图所示，此时这棵树就不平衡了。接下来就需要调节平衡因子

2.4. AVL树的旋转

当我们像上图一样插入之后，就需要修改平衡因子。当插入到右子树时，该子树的父亲节点的平衡因子增加；当插入到左子树时，该子树的父亲节点的平衡因子减少。

        //调节平衡因子while () {if (cur == parent.right) {parent.bf++;} else {parent.bf--;}}

如果出现了下图这种情况，如果当前节点节点存在左孩子节点，当新节点插入到右子树时，此时父亲节点的平衡因子为0，当前树就平衡了，也不需要向上调整了。

如果出现了下图这种情况，整棵树本身是平衡的，但其中一个节点的平衡因子是-1或1，我们插入节点之后，修改了平衡因子为0，此时我们就不需要向上调节了。

            //说明已经平衡了if (parent.bf == 0) {break;//当前子树平衡，但整棵树不平衡，继续向上调整} else if (parent.bf == 1 || parent.bf == -1) {cur = parent;parent = cur.parent;} else {}

接下来又可以分两种情况：一种是当前父亲节点平衡因子为2，另一种是当前父亲节点平衡因子为-2，而孩子节点的平衡因子为1或者-1。

                if (parent.bf == 2) {//右树高，需要降低右子树的高度if (curt.bf == 1) {} else if (cur.bf == -1) {}} else if (parent.bf == -2) {//左树高，需要降低左子树的高度if (cur.bf == 1) {} else if (cur.bf == -1) {}

右单旋

我们先定义这棵树的左孩子节点subL，再定义subL节点的右孩子节点subLR。先将父亲节点的左孩子引用指向subLR，再将subL的右孩子引用指向父亲节点，这样就可以将30这个节点置为新的父亲节点，最后原来的父亲节点的父亲引用指向新的父亲引用。

    private void rotateRight(TreeNode parent) {TreeNode subL = parent.left;TreeNode subLR = subL.right;// 将parent节点的左子节点设置为subLRparent.left = subLR;// 将subL节点的右子节点设置为parentsubL.right = parent;// 将subLR节点的父节点设置为parentsubLR.parent = parent;// 将parent节点的父节点设置为subLparent.parent = subL;}

但在旋转的时候需要注意，这棵树的父亲节点有可能是根节点，也有可能是左子树或者右子树。如果父亲节点本身就是根节点，那么直接将subL设置为根节点。如果这棵树是一个子树，则将subL设置为parent父亲节点的孩子节点。

        // 如果parent节点是根节点，则将subL节点设置为根节点if (parent == root) {root = subL;root.parent = null;} else {// 如果parent节点是其父节点的左子节点，则将subL节点设置为parent节点的父节点的左子节点if (pParent.left == parent) {pParent.left = subL;// 如果parent节点是其父节点的右子节点，则将subL节点设置为parent节点的父节点的右子节点} else if (pParent.right == parent) {pParent.right = subL;}subL.parent = pParent;}

旋转完之后，还需要修改平衡因子。我们需要将subL节点和parent节点的平衡因子置为空，并且还需要判断subLR是否为空。

    /*** 右单旋* @param parent*/private void rotateRight(TreeNode parent) {TreeNode subL = parent.left;TreeNode subLR = subL.right;// 将parent节点的左子节点设置为subLRparent.left = subLR;// 将subL节点的右子节点设置为parentsubL.right = parent;//没有subLR节点if (subLR != null) {subLR.parent = parent;}// 将subLR节点的父节点设置为parent// 获取parent节点的父节点TreeNode pParent = parent.parent;// 将parent节点的父节点设置为subLparent.parent = subL;// 如果parent节点是根节点，则将subL节点设置为根节点if (parent == root) {root = subL;root.parent = null;} else {// 如果parent节点是其父节点的左子节点，则将subL节点设置为parent节点的父节点的左子节点if (pParent.left == parent) {pParent.left = subL;// 如果parent节点是其父节点的右子节点，则将subL节点设置为parent节点的父节点的右子节点} else if (pParent.right == parent) {pParent.right = subL;}subL.parent = pParent;}subL.bf = 0;parent.bf = 0;}

左单旋

左单旋与右单旋的思路一致，同样需要定义节点引用，修改指向，将其变为平衡树，并且也要修改平衡因子。

    /*** 左单旋* @param parent*/private void rotateLeft(TreeNode parent) {TreeNode subR = parent.right;TreeNode subRL = subR.left;parent.right = subRL;subR.left = parent;if (subRL != null) {subRL.parent = parent;}TreeNode pParent = parent.parent;parent.parent = subR;if (root == parent) {root = subR;root.parent = null;} else {if (pParent.left == parent) {pParent.left = subR;} else if (pParent.right == parent) {pParent.right = subR;}subR.parent = pParent;}subR.bf = 0;parent.bf = 0;}

旋转完之后，当不再遇到平衡因子为2或-2时，此时说明已经平衡了，与此同时parent节点也不为空。

左右双旋

我们发现前两个单旋的平衡因子都是同号的，但还有两种情况就是平衡因子出现异号的情况，如下图这种情况，我们无论是左旋还是右旋都无法达到我们想要的平衡效果。

我们先将30这个节点进行左旋，再将整棵树进行右旋，才能达到我们想要的效果。旋转完之后，记得修改平衡因子。

以上为subLR的平衡因子为-1时，还需注意当subLR的平衡因子为1时的平衡因子。

    /*** 左右双旋* @param parent*/private void rotateLR(TreeNode parent) {// 获取左子节点TreeNode subL = parent.left;// 获取左子节点的右子节点TreeNode subLR = subL.right;// 获取右子节点的平衡因子int bf = subLR.bf;// 左旋左子节点rotateLeft(parent.left);// 右旋父节点rotateRight(parent);// 如果右子节点的平衡因子为-1if (bf == -1) {subL.bf = 0;subLR.bf = 0;parent.bf = 1;// 如果右子节点的平衡因子为1} else if (bf == 1) {subL.bf = -1;subLR.bf = 0;parent.bf = 0;}}

右左双旋

    /*** 右左双旋* @param parent*/private void rotateRL(TreeNode parent) {TreeNode subR = parent.right;TreeNode subRL = subR.left;int bf = subRL.bf;// 右旋右子节点rotateRight(parent.right);// 左旋父节点rotateLeft(parent);// 如果右子节点的左子节点的平衡因子为1if (bf == 1) {subR.bf = 0;subRL.bf = 0;parent.bf = -1;// 如果右子节点的左子节点的平衡因子为-1} else if (bf == -1) {subR.bf = 0;subRL.bf = 1;parent.bf = 0;}}

2.5. AVL树的验证

要想验证当前树是否为AVL树：1. 该树是否为二叉搜索树；2. 高度差的绝对值不超过1。判断二叉搜索树，只需中序遍历的结果是否有序；求高度差，递归分别获取左右子树的高度。但下面的代码是有问题的，如果平衡因子本身就是错误的，我们无法判断出哪个平衡因子有问题。所以我们还需要加个判断，子树的高度差是否等于平衡因子。

    /*** 验证是否为二叉搜索树* @param root*/private void InOrder(TreeNode root) {if (root == null) {return;}InOrder(root.left);System.out.println(root.val + " ");InOrder(root.right);}/*** 计算二叉树高度* @param root* @return*/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;}/*** 验证是否为AVL树* @param root* @return*/private boolean isBalanced(TreeNode root) {if (root == null) {return true;}int leftH = Height(root.left);int rightH = Height(root.right);return Math.abs(leftH - rightH) <= 1&& isBalanced(root.left)&& isBalanced(root.right);}

修改后的代码：

    /*** 验证是否为二叉搜索树* @param root*/private void InOrder(TreeNode root) {if (root == null) {return;}InOrder(root.left);System.out.println(root.val + " ");InOrder(root.right);}/*** 计算二叉树高度* @param root* @return*/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;}/*** 验证是否为AVL树* @param root* @return*/private 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("平衡因子异常");return false;}return Math.abs(leftH - rightH) <= 1&& isBalanced(root.left)&& isBalanced(root.right);}

public class Test {public static void main(String[] args) {int[] array = new int[]{4, 2, 6, 1, 3, 5, 15, 7, 16, 14};AVLTree avlTree = new AVLTree();for (int i = 0; i < array.length; i++) {avlTree.insert(array[i]);}System.out.println(avlTree.isBalanced(avlTree.root));}
}