【数据结构与算法】平衡二叉树（AVL树）

平衡二叉树（AVL树）

给你一个数列{1,2,3,4,5,6}，要求创建二叉排序树（BST），并分析问题所在。

BST 存在的问题分析：

1. 左子树全部为空，从形式上看，更像一个单链表。
2. 插入速度没有影响。
3. 查询速度明显降低（因为需要依次比较），不能发挥 BST 的优势，因为每次还需要比较左子树，其查询速度比单链表还慢。
4. 解决方案：平衡二叉树（AVL）

基本介绍

1. 平衡二叉树也叫平衡二叉搜索树（Self - balancing binary search tree）又被称为 AVL 树，可以保证查询速率较高。
2. 具有一下特点：它是一棵空树或它的左右两个子树的高度差的绝对值不能超过 1，并且左右两个子树都是一棵平衡二叉树，平衡二叉树的常用实现方法有：红黑树、AVL、替罪羊树、Treap、伸展树等。

应用案例 - 左旋转

给你一个数列{4,3,6,5,7,8}，构建成一棵平衡二叉树。

问题：

当插入 8 时，rightHeight() - leftHight() > 1 成立，此时，不再是一棵 AVL 树了。

思路 - 左旋转：

1. 创建一个新的节点 newNode（以 4 这个值创建），值等于当前根节点的值；
2. 把新节点的左子树设置为当前节点的左子树；
3. 把新节点的右子树设置为当前节点右子树的左子树；
4. 把当前节点的值换为右子节点的值；
5. 把当前节点的右子树设置为右子树的右子树；
6. 把当前节点的左子树设置为新节点。
   

代码实现：文章来源地址https://www.toymoban.com/news/detail-635082.html

public class AVLTreeDemo {
    public static void main(String[] args) {
        int[] arr = {4, 3, 6, 5, 7, 8};
        // 创建一个 AVLTree
        AVLTree avlTree = new AVLTree();
        // 添加节点
        for (int i = 0; i < arr.length; i++) {
            avlTree.add(new Node(arr[i]));
        }

        // 遍历
        System.out.println("中序遍历");
        avlTree.infixOrder();
        System.out.println("左子树：" + avlTree.getRoot().leftHeight());
        System.out.println("右子树：" + avlTree.getRoot().rightHeight());
        System.out.println("树：" + avlTree.getRoot().height());
    }
}

// 创建 AVLTree
class AVLTree {
    private Node root;

    /**
     * 查找要删除的节点
     *
     * @param value 要删除的节点的值
     * @return 如果找到，返回节点，否则，返回 null
     */
    public Node search(int value) {
        if (root == null) {
            return null;
        } else {
            return root.search(value);
        }
    }

    /**
     * 得到以 node 为节点的最小节点的值，并删除该值
     *
     * @param node 传入的节点
     * @return 返回的是以 node 为根节点的二叉排序树的最小节点的值
     */
    public int delRightTreeMin(Node node) {
        Node target = node;
        // 循环查找左节点，就会找到最小值
        while (target.left != null) {
            target = target.left;
        }
        // 这时 target 就指向了最小节点
        // 删除最小节点
        delNode(target.value);
        return target.value;
    }

    /**
     * 得到以 node 为节点的最大节点的值，并删除该值
     *
     * @param node 传入的节点
     * @return 返回的是以 node 为根节点的二叉排序树的最大节点的值
     */
    public int delLiftTreeMax(Node node) {
        Node target = node;
        // 循环查找右节点，就会找到最小值
        while (target.right != null) {
            target = target.right;
        }
        // 这时 target 就指向了最大节点
        // 删除最大节点
        delNode(target.value);
        return target.value;
    }

    /**
     * 删除节点
     *
     * @param value 要删除节点的值
     */
    public void delNode(int value) {
        if (root == null) {
            return;
        } else {
            // 1. 需要先去找到要删除的节点
            Node targetNode = search(value);
            // 如果没有找到要删除的节点
            if (targetNode == null) {
                return;
            }
            // 如果我们发现当前这棵二叉排序树只有一个节点
            if (root.left == null && root.right == null) {
                root = null;
                return;
            }
            // 去找到 targetNode 的父节点
            Node parent = searchParent(value);
            // 第一种情况
            // 如果要删除节点是叶子结点
            if (targetNode.left == null && targetNode.right == null) {
                // 判断 targetNode 是父节点的左子节点还是右子节点
                if (parent.left != null && parent.left.value == value) { // 是左子节点
                    parent.left = null;
                } else if (parent.right != null && parent.right.value == value) { // 是右子节点
                    parent.right = null;
                }
            } else if (targetNode.left != null && targetNode.right != null) {
                // 第三种情况
                // 如果要删除的节点是有两棵子树的节点
                // 向右子树找最小值
//                targetNode.value = delRightTreeMin(targetNode.right);
                // 向左子树找最大值
                targetNode.value = delLiftTreeMax(targetNode.left);
            } else {
                // 第二种情况
                // 如果要删除的节点是只有一棵子树的的节点
                // 如果要删除的节点有左子节点
                if (targetNode.left != null) {
                    if (parent != null) {
                        // 如果 targetNode 是 parent 的左子节点
                        if (parent.left.value == value) {
                            parent.left = targetNode.left;
                        } else { // 如果 targetNode 是 parent 的右子节点
                            parent.right = targetNode.left;
                        }
                    } else {
                        root = targetNode.left;
                    }
                } else { // 如果要删除的节点有右子节点
                    if (parent != null) {
                        // 如果 targetNode 是 parent 的左子节点
                        if (parent.left.value == value) {
                            parent.left = targetNode.right;
                        } else { // 如果 targetNode 是 parent 的右子节点
                            parent.right = targetNode.right;
                        }
                    } else {
                        root = targetNode.right;
                    }
                }
            }
        }
    }

    /**
     * 查找要删除节点的父节点
     *
     * @param value 要删除节点的值
     * @return 如果找到，放回父节点，否则，返回 null
     */
    public Node searchParent(int value) {
        if (root == null) {
            return null;
        } else {
            return root.searchParent(value);
        }
    }

    /**
     * 添加节点的方法
     *
     * @param node 需要添加的节点
     */
    public void add(Node node) {
        // 如果 root 为空，则直接让 root 指向 node
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }

    /**
     * 中序遍历
     */
    public void infixOrder() {
        if (root != null) {
            root.infixOrder();
        } else {
            System.out.println("二叉排序树为空，不能遍历");
        }
    }

    public Node getRoot() {
        return root;
    }

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

// 创建 Node 节点
class Node {
    int value;
    Node left;
    Node right;

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

    /**
     * 左子树的高度
     *
     * @return 返回左子树的高度
     */
    public int leftHeight() {
        return left == null ? 0 : left.height();
    }

    /**
     * 右子树的高度
     *
     * @return 返回右子树的高度
     */
    public int rightHeight() {
        return right == null ? 0 : right.height();
    }

    /**
     * 得到以当前节点为根节点的树的高度
     *
     * @return 返回当前节点的高度
     */
    public int height() {
        return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
    }

    /**
     * 左旋转
     */
    private void leftRotate() {
        // 1. 创建一个新的节点 newNode（以 4 这个值创建），值等于当前根节点的值；
        Node newNode = new Node(value);
        // 2. 把新节点的左子树设置为当前节点的左子树；
        newNode.left = left;
        // 3. 把新节点的右子树设置为当前节点右子树的左子树；
        newNode.right = right.left;
        // 4. 把当前节点的值换为右子节点的值；
        value = right.value;
        // 5. 把当前节点的右子树设置为右子树的右子树；
        right = right.right;
        // 6. 把当前节点的左子树设置为新节点。
        left = newNode;
    }

    /**
     * 查找要删除的节点
     *
     * @param value 希望删除的节点的值
     * @return 如果找到返回该节点，否则，返回 null
     */
    public Node search(int value) {
        if (value == this.value) { // 找到该节点
            return this;
        } else if (value < this.value) { // 如果查找的节点小于当前节点，向左子树递归查找
            if (this.left == null) {
                return null;
            }
            return this.left.search(value);
        } else { // 如果查找的节点大于或等于当前节点，向右子树递归查找
            if (this.right == null) {
                return null;
            }
            return this.right.search(value);
        }
    }

    /**
     * 查找要删除节点的父节点
     *
     * @param value 要找到的节点的值
     * @return 返回的是要删除节点的父节点，如果没有就返回 null
     */
    public Node searchParent(int value) {
        if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
            return this;
        } else {
            // 如果查找的这个值小于当前节点的值，并且当前节点的左子节点不为空
            if (value < this.value && this.left != null) {
                return this.left.searchParent(value); // 向左子树递归查找
            } else if (value >= this.value && this.right != null) { // 如果查找的这个值大于等于当前节点的值，并且当前节点的右子节点不为空
                return this.right.searchParent(value); // 向右子树递归查找
            } else {
                return null;
            }
        }
    }

    /**
     * 添加节点的方法
     * 通过递归的方式添加节点，注意需要满足二叉排序树的要求
     *
     * @param node 需要添加的节点
     */
    public void add(Node node) {
        if (node == null) {
            return;
        }
        // 判断出入节点的值和当前子树的根节点的关系
        if (node.value < this.value) {
            // 如果当前节点的左子节点为 null
            if (this.left == null) {
                this.left = node;
            } else {
                // 递归向左子树添加
                this.left.add(node);
            }
        } else {
            // 如果当前节点的右子节点为 null
            if (this.right == null) {
                this.right = node;
            } else {
                // 递归向右子树添加
                this.right.add(node);
            }
        }
        // 当添加完一个节点后，如果 右子树的高度 - 左子树的高度 > 1，左旋转
        if (rightHeight() - leftHeight() > 1) {
            leftRotate(); // 左旋转
        }
    }

    /**
     * 中序遍历
     */
    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }

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

应用案例 - 右旋转

给你一个数列{10,12,8,9,7,6}，构建成一棵平衡二叉树。

问题：

当插入 6 时，leftHight() - rightHeight() > 1 成立，此时，不再是一棵 AVL 树了。

思路 - 左旋转：

1. 创建一个新的节点 newNode（以 10 这个值创建），值等于当前根节点的值；
2. 把新节点的右子树设置为当前节点的右子树；
3. 把新节点的左子树设置为当前节点左子树的右子树；
4. 把当前节点的值换为左子节点的值；
5. 把当前节点的左子树设置为左子树的左子树；
6. 把当前节点的右子树设置为新节点。

代码实现：

/**
 * 右旋转
 */
private void rightRotate() {
    // 1. 创建一个新的节点 newNode（以 10 这个值创建），值等于当前根节点的值；
    Node newNode = new Node(value);
    // 2. 把新节点的右子树设置为当前节点的右子树；
    newNode.right = right;
    // 3. 把新节点的左子树设置为当前节点左子树的右子树；
    newNode.left = left.right;
    // 4. 把当前节点的值换为左子节点的值；
    value = left.value;
    // 5. 把当前节点的左子树设置为左子树的左子树；
    left = left.left;
    // 6. 把当前节点的右子树设置为新节点。
    right = newNode;
}

应用案例 - 双旋转

给你一个数列{10,11,7,6,8,9}，构建成一棵平衡二叉树。

问题：

当插入 9 时，leftHight() - rightHeight() > 1 成立，此时，不再是一棵 AVL 树了。但是，当进行了右旋转后发现，它依旧不是一棵 AVL 树。

思路：

1. 当符合右旋转条件时
2. 如果它的左子树的右子树高度大于它的左子树的左子树的高度
3. 先对当前这个节点的左节点进行左旋转
4. 再对当前节点进行右旋转的操作即可

代码实现：

/**
 * 添加节点的方法
 * 通过递归的方式添加节点，注意需要满足二叉排序树的要求
 *
 * @param node 需要添加的节点
 */
public void add(Node node) {
    if (node == null) {
        return;
    }
    // 判断出入节点的值和当前子树的根节点的关系
    if (node.value < this.value) {
        // 如果当前节点的左子节点为 null
        if (this.left == null) {
            this.left = node;
        } else {
            // 递归向左子树添加
            this.left.add(node);
        }
    } else {
        // 如果当前节点的右子节点为 null
        if (this.right == null) {
            this.right = node;
        } else {
            // 递归向右子树添加
            this.right.add(node);
        }
    }
    // 当添加完一个节点后，如果 右子树的高度 - 左子树的高度 > 1，左旋转
    if (rightHeight() - leftHeight() > 1) {
        // 如果它的右子树的左子树高度大于它的右子树的右子树的高度
        if (right != null && right.leftHeight() > right.rightHeight()) {
            // 先对当前这个节点的右节点进行右旋转
            right.rightRotate();
            // 再对当前节点进行左旋转的操作即可
            leftRotate();
        } else {
            // 直接进行左旋转
            leftRotate();
        }
        return;
    }
    // 当添加完一个节点后，如果 左子树的高度 - 右子树的高度 > 1，右旋转
    if (leftHeight() - rightHeight() > 1) {
        // 如果它的左子树的右子树高度大于它的左子树的左子树的高度
        if (left != null && left.rightHeight() > left.leftHeight()) {
            // 先对当前这个节点的左节点进行左旋转
            left.leftRotate();
            // 再对当前节点进行右旋转的操作即可
            rightRotate();
        } else {
            // 直接进行右旋转
            rightRotate();
        }
    }
}

到了这里，关于【数据结构与算法】平衡二叉树（AVL树）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！