平衡二叉树AVL

1. BST存在的问题——引入平衡二叉树

• 上图中的BST左子树为空，从形式上来看更像是一条单链表；
• 虽然插入的速度并没有受到影响，但查询的速度明显降低；
• 这是由于每次查询进行比较时，还需要比较左子树，其查询速度比单链表还慢，无法发挥BST的优势；
• 提出解决方案，一种新的数据结构——平衡二叉树（AVL树）

2. AVL树的基本介绍

• 平衡二叉树又称平衡二叉排序树（Self-Balancing Binary Tree），也称AVL树，其可以保证较高的查询效率；
• 平衡二叉树具有以下特点：
  • 其可以是一棵空树，或者左右两棵子树的高度差的绝对值不超过1（即 Math.abs(左子树height - 右子树height) <= 1）；
  • 左右两棵子树必须都是平衡二叉树；
  • 常见的实现：红黑树、AVL算法、替罪羊树、Treap、伸展树等。
• 平衡二叉树是一种特殊的BST，也可以说是二叉排序树的一种扩展；
  • 简单来说，就是在构建二叉排序树的过程中，每当添加一个新的节点时，先检查是否由于插入节点二破坏了该树的“平衡性”；
  • 若插入节点后发现破坏了“平衡性”，即不满足Math.abs(左子树height - 右子树height) <= 1；
  • 此时就需要在保持BST特性的前提下，对树结构进行调整，进行相应的“旋转”操作，使其成为新的平衡子树。
  • 注意：检查是否破坏“平衡性”以及相应的旋转操作是每一次添加新的节点后都立即进行的。

3. AVL树的旋转

3.1 计算AVL树的高度

3.1.1 思路

以当前节点为子树的根节点，递归计算其左子树与右子树的高度，并取左右子树高度的较大值，然后将该较大值+1（加上根节点所在的1层）即可。即当前节点为根节点的子树的高度为：height = Math.max(左子树height，右子树height) + 1。

3.1.2 代码实现

// 为了后续方便调用，对计算当前节点的左子树和右子树的高度的方法分别进行单独封装
public int getLeftHeight(AVLTreeNode root) {
    if (root.getLeft() == null) {
        return 0;
    }
    int leftHeight = getHeight(root.getLeft());
    return leftHeight;
}

public int getRightHeight(AVLTreeNode root) {
    if (root.getRight() == null) {
        return 0;
    }
    int rightHeight = getHeight(root.getRight());
    return rightHeight;
}

// 返回以当前节点root为根节点的子树的高度
public int getHeight(AVLTreeNode root) {
    // 求树的高度时取其左右子树高度的较大值，并注意要加上根节点所在的一层
    int height = Math.max(root.getLeft() == null ? 0 : getHeight(root.getLeft()), root.getRight() == null ? 0 : getHeight(root.getRight())) + 1;
    return height;
}

3.2 AVL树左旋转

3.2.1 思路

• 如上图所示，当插入节点8时，rightHeight - leftHeight > 1成立，此时不是一棵AVL树，因此需要做左旋转操作；
• 创建一个新节点newNode(4)，新节点的value等于当前节点root的value；
• newNode的左子节点置为当前节点的左子节点，即newNode.setLeft = root.getLeft；
• newNode的右子节点置为当前节点的右子节点的左子节点，即newNode.setRight = root.getRight.getLeft；
• 用当前节点的右子节点的值替换掉当前节点的值，即root.setValue = root.getRight.getValue；
• 当前节点的左子节点置为newNode，即root.setLeft = newNode；
• 当前节点的右子节点置为当前节点的右子节点的右子节点（当前节点的右子节点因无任何引用被垃圾回收），即root.setRight = root.getRight.getRight。

3.2.2 代码实现

// 左旋转
public void leftRotate(AVLTreeNode root) {
    // 创建新节点
    AVLTreeNode newNode = new AVLTreeNode(root.getValue());
    // 新节点左子节点为当前节点的左子节点
    newNode.setLeft(root.getLeft());
    // 右子节点为当前节点的右子节点的左子节点
    newNode.setRight(root.getRight().getLeft());
    // 替换当前节点的value
    root.setValue(root.getRight().getValue());
    // 当前节点左子节点为新节点
    root.setLeft(newNode);
    // 当前节点右子节点为当前节点的右子节点的右子节点
    root.setRight(root.getRight().getRight());
}

3.3 AVL树右旋转

3.3.1 思路

• 如上图所示，当插入节点6时，leftHeight - rightHeight > 1成立，此时不是一棵AVL树，因此需要做右旋转操作；
• 创建一个新节点newNode(10)，新节点的value等于当前节点root的value；
• newNode的右子节点置为当前节点的右子节点，即newNode.setRight = root.getRight；
• newNode的左子节点置为当前节点的左子节点的右子节点，即newNode.setLeft = root.getLeft.getRight；
• 用当前节点的左子节点的值替换掉当前节点的值，即root.setValue = root.getLeft.getValue；
• 当前节点的右子节点置为newNode，即root.setRight = newNode；
• 当前节点的左子节点置为当前节点的左子节点的左子节点（当前节点的左子节点因无任何引用被垃圾回收），即root.setLeft = root.getLeft.getLeft。

3.3.2 代码实现

// 右旋转
public void rightRotate(AVLTreeNode root) {
    // 创建新节点
    AVLTreeNode newNode = new AVLTreeNode(root.getValue());
    // 新节点右子节点为当前节点的右子节点
    newNode.setRight(root.getRight());
    // 左子节点为当前节点的左子节点的右子节点
    newNode.setLeft(root.getLeft().getRight());
    // 替换当前节点的value
    root.setValue(root.getLeft().getValue());
    // 当前节点右子节点为新节点
    root.setRight(newNode);
    // 当前节点左子节点为当前节点的左子节点的左子节点
    root.setLeft(root.getLeft().getLeft());
}

3.4 AVL树的双旋转

3.4.1 思路

• 如上面两图所示，当插入节点9和节点3时，Math.abs(leftHeight - rightHeight) > 1成立，但发现仅通过单旋转并不能在上面这些情况下完成平衡二叉树的转换，此时就需要进行双旋转操作，如下图所示；

• 上面两图分别对应了两种情况：

  • 情况1：如果root.getLeftHeight - root.getRightHeight > 1

    • 情况1.1：若在此情况下还满足当前节点的左子节点的右子树高度 > 其左子树高度，

      （注意此时判断条件是右子树高度 > 左子树高度，而不是子树高度差 > 1）

      即root.getLeft != null && root.getLeft.getRightHeight > root.getLeft.getLeftHeight

    • 则先对以当前节点的左子节点为根节点的子树，先进行左旋转。即leftRotate(root.getLeft)

      • 然后在对当前节点root做右旋转，即rightRotate(root)

    • 情况1.2：否则就是前面单旋转的情况，直接对root进行右旋转，即rightRotate(root)

  • 情况2：如果root.getRightHeight - root.getLeftHeight > 1

    • 情况2.1：若在此情况下还满足当前节点的右子节点的左子树高度 > 其右子树高度，

      （注意此时判断条件是左子树高度 > 右子树高度，而不是子树高度差 > 1）

    即root.getRight != null && root.getRight.getLeftHeight > root.getRight.getRightHeight

    • 则先对以当前节点的右子节点为根节点的子树，先进行右旋转。rightRotate(root.getRight)

      • 然后在对当前节点root做左旋转，即leftRotate(root)

    • 情况2.2：否则就是前面单旋转的情况，直接对root进行左旋转，即leftRotate(root)

3.4.2 代码实现

注：该部分代码应写在添加节点（构建AVL树）的add方法中，每添加一个节点都要立即检查“平衡性”，并做相应的旋转操作。

// -----------------------双旋转处理-----------------------------------------

// LR旋转
if (getLeftHeight(root) - getRightHeight(root) > 1) {
    // 若当前节点的左子节点的右子树高度 > 其左子树高度
    if (root.getLeft() != null && getRightHeight(root.getLeft()) > getLeftHeight(root.getLeft())) {
        // 则先对当前节点的左子节点进行左旋转
        leftRotate(root.getLeft());
        // 再对当前节点进行右旋转
        rightRotate(root);
    } else {
        // 否则就是单旋转操作，直接右旋转即可（R旋转）
        rightRotate(root);
    }
// RL旋转
} else if (getRightHeight(root) - getLeftHeight(root) > 1){
    // 若当前节点的右子节点的左子树高度 > 其右子树高度
    if (root.getRight() != null && getLeftHeight(root.getRight()) > getRightHeight(root.getRight())) {
        // 则先对当前节点的右子节点进行右旋转
        rightRotate(root.getRight());
        // 再对当前节点进行左旋转
        leftRotate(root);
    } else {
        // 否则就是单旋转操作，直接左旋转即可（L旋转）
        leftRotate(root);
    }
}

4. 完整代码

package com.datastructure;

import java.util.*;

/**
 * @author SnkrGao
 * @create 2023-05-19 18:28
 */
public class AVLTreeDemo {
    public static void main(String[] args) {
//        int[] arr = {4, 3, 6, 5, 7, 8}; // 测试L旋转的序列
//        int[] arr = {10, 12, 8, 9, 7, 6}; // 测试R旋转的序列
        int[] arr = {10, 11, 7, 6, 8, 9}; // 测试LR旋转的序列
//        int[] arr = {2, 1, 6, 5, 7, 3}; // 测试RL旋转的序列

        AVLTree avlTree = new AVLTree();
        for (int i = 0; i < arr.length; i++) {
            avlTree.add(avlTree.getRoot(), new AVLTreeNode(arr[i]));
        }

        List<Integer> resList = new ArrayList<>();
        List<List<Integer>> resList2 = new ArrayList<>();

        System.out.println("调整前树高" + avlTree.getHeight(avlTree.getRoot()) + ";左子树高" + avlTree.getLeftHeight(avlTree.getRoot()) + ";右子树高" + avlTree.getRightHeight(avlTree.getRoot()));

        System.out.println("调整前中序遍历：");
        resList = avlTree.inorderTraversal(avlTree.getRoot());
        System.out.println(resList);
        System.out.println("调整前层序遍历：");
        resList2 = avlTree.levelorderTraversal(avlTree.getRoot());
        System.out.println(resList2);

        System.out.println("---------------------------------------------------------");

        // 测试左旋转（add方法中只有添加节点操作）
        avlTree.leftRotate(avlTree.getRoot());

        // 测试右旋转（add方法中只有添加节点操作）
//        avlTree.rightRotate(avlTree.getRoot());

        System.out.println("调整后树高" + avlTree.getHeight(avlTree.getRoot()) + ";左子树高" + avlTree.getLeftHeight(avlTree.getRoot()) + ";右子树高" + avlTree.getRightHeight(avlTree.getRoot()));

        System.out.println("调整后中序遍历：");
        resList = avlTree.inorderTraversal(avlTree.getRoot());
        System.out.println(resList);
        System.out.println("调整后层序遍历：");
        resList2 = avlTree.levelorderTraversal(avlTree.getRoot());
        System.out.println(resList2);
    }
}

class AVLTree {
    private AVLTreeNode root;

    public AVLTreeNode getRoot() {
        return root;
    }

    public void setRoot(AVLTreeNode root) {
        this.root = root;
    }

    // 添加节点，构建AVL树
    public void add(AVLTreeNode root, AVLTreeNode node) {
        if (this.root == null) {
            this.setRoot(node);
            return;
        }
        if (node.getValue() < root.getValue()) {
            if (root.getLeft() == null) {
                root.setLeft(node);
            } else {
                add(root.getLeft(), node);
            }
        } else {
            if (root.getRight() == null) {
                root.setRight(node);
            } else {
                add(root.getRight(), node);
            }
        }

        // -----------------------双旋转处理-----------------------------------------

        // LR旋转
        if (getLeftHeight(root) - getRightHeight(root) > 1) {
            // 若当前节点的左子节点的右子树高度 > 其左子树高度
            if (root.getLeft() != null && getRightHeight(root.getLeft()) > getLeftHeight(root.getLeft())) {
                // 则先对当前节点的左子节点进行左旋转
                leftRotate(root.getLeft());
                // 再对当前节点进行右旋转
                rightRotate(root);
            } else {
                // 否则就是单旋转操作，直接右旋转即可（R旋转）
                rightRotate(root);
            }
        // RL旋转
        } else if (getRightHeight(root) - getLeftHeight(root) > 1){
            // 若当前节点的右子节点的左子树高度 > 其右子树高度
            if (root.getRight() != null && getLeftHeight(root.getRight()) > getRightHeight(root.getRight())) {
                // 则先对当前节点的右子节点进行右旋转
                rightRotate(root.getRight());
                // 再对当前节点进行左旋转
                leftRotate(root);
            } else {
                // 否则就是单旋转操作，直接左旋转即可（L旋转）
                leftRotate(root);
            }
        }
    }

    public List<Integer> inorderTraversal(AVLTreeNode root) {
        if (root == null) {
            System.out.println("AVL树为空，无法中序遍历！");
            return new ArrayList<>();
        }

        List<Integer> resList = new ArrayList<>();
        Deque<AVLTreeNode> stack = new ArrayDeque<>();
        AVLTreeNode curNode = root;

        while (curNode != null || !stack.isEmpty()) {
            while (curNode != null) {
                stack.push(curNode);
                curNode = curNode.getLeft();
            }
            if (!stack.isEmpty()) {
                AVLTreeNode tmpNode = stack.pop();
                resList.add(tmpNode.getValue());
                curNode = tmpNode.getRight();
            }
        }

        return resList;
    }

    public List<List<Integer>> levelorderTraversal(AVLTreeNode root) {
        if (root == null) {
            System.out.println("AVL树为空，无法层序遍历！");
            return new ArrayList<>();
        }

        List<List<Integer>> resList = new ArrayList<>();
        Queue<AVLTreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int queueSize = queue.size();
            List<Integer> levelList = new ArrayList<>();

            for (int i = 0; i < queueSize; i++) {
                AVLTreeNode tmpNode = queue.poll();
                levelList.add(tmpNode.getValue());
                if (tmpNode.getLeft() != null) {
                    queue.offer(tmpNode.getLeft());
                }
                if (tmpNode.getRight() != null) {
                    queue.offer(tmpNode.getRight());
                }
            }

            resList.add(levelList);
        }
        return resList;
    }

    // 为了后续方便调用，对计算当前节点的左子树和右子树的高度的方法分别进行单独封装
    public int getLeftHeight(AVLTreeNode root) {
        if (root.getLeft() == null) {
            return 0;
        }
        int leftHeight = getHeight(root.getLeft());
        return leftHeight;
    }

    public int getRightHeight(AVLTreeNode root) {
        if (root.getRight() == null) {
            return 0;
        }
        int rightHeight = getHeight(root.getRight());
        return rightHeight;
    }

    // 返回以当前节点root为根节点的子树的高度
    public int getHeight(AVLTreeNode root) {
        int height = Math.max(root.getLeft() == null ? 0 : getHeight(root.getLeft()), root.getRight() == null ? 0 : getHeight(root.getRight())) + 1;
        return height;
    }

    // 左旋转
    public void leftRotate(AVLTreeNode root) {
        // 创建新节点
        AVLTreeNode newNode = new AVLTreeNode(root.getValue());
        // 新节点左子节点为当前节点的左子节点
        newNode.setLeft(root.getLeft());
        // 右子节点为当前节点的右子节点的左子节点
        newNode.setRight(root.getRight().getLeft());
        // 替换当前节点的value
        root.setValue(root.getRight().getValue());
        // 当前节点左子节点为新节点
        root.setLeft(newNode);
        // 当前节点右子节点为当前节点的右子节点的右子节点
        root.setRight(root.getRight().getRight());
    }

    // 右旋转
    public void rightRotate(AVLTreeNode root) {
        // 创建新节点
        AVLTreeNode newNode = new AVLTreeNode(root.getValue());
        // 新节点右子节点为当前节点的右子节点
        newNode.setRight(root.getRight());
        // 左子节点为当前节点的左子节点的右子节点
        newNode.setLeft(root.getLeft().getRight());
        // 替换当前节点的value
        root.setValue(root.getLeft().getValue());
        // 当前节点右子节点为新节点
        root.setRight(newNode);
        // 当前节点左子节点为当前节点的左子节点的左子节点
        root.setLeft(root.getLeft().getLeft());
    }
}

class AVLTreeNode {
    private int value;
    private AVLTreeNode left;
    private AVLTreeNode right;

    public AVLTreeNode(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "AVLTreeNode{" +
                "value=" + value +
                '}';
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public AVLTreeNode getLeft() {
        return left;
    }

    public void setLeft(AVLTreeNode left) {
        this.left = left;
    }

    public AVLTreeNode getRight() {
        return right;
    }

    public void setRight(AVLTreeNode right) {
        this.right = right;
    }
}

本栏目推荐文章
• 第十二节：红黑树性质、相对平衡的原理、与AVL树的区别
• 第十一节：平衡树、AVL树、红黑树详解
• 二叉树 - AVL树
• AVL树和红黑树的Python代码实现
• 【JavaSE】数据结构（树：二叉查找树、平衡二叉树、AVL树、红黑树）
• 第8章. AVL树
• AVL选择屏幕 常用参数
• AVL添加和删除结点
• 平衡二叉树AVL
• 【数据结构】7.平衡搜索树（AVL树和红黑树）

AVL算法avl 结点avl bst avl rbt 性质 原理avl 1066 root tree avl multimap map avl 数据结构 结构 数据avl 2023 avl 03 25 代码python avl 屏幕 常用 参数avl