• 数据结构：平衡二叉树

    文章目录

    平衡二叉树

    一，概述

    平衡二叉树，也称为AVL树，是一种特殊的二叉排序树，它的每个节点的左子树和右子树的高度差不超过1。平衡二叉树的定义可以概括为以下两点：

    1. 左子树和右子树的高度差绝对值不超过1。
    2. 左子树和右子树都是平衡二叉树。

    平衡因子是平衡二叉树中的一个重要概念，它表示一个节点的左子树高度减去右子树的高度。根据平衡二叉树的定义，每个节点的平衡因子只能是-1、0或1。

    当在一个平衡二叉排序树上插入一个新节点时，有可能导致失衡，即出现平衡因子绝对值大于1的节点。为了恢复平衡，可能需要对树进行调整。常见的调整方法包括旋转和重新平衡。

    旋转分为四种类型：左旋、右旋、左右旋和右左旋。旋转操作是平衡二叉树调整中常用的方法，它的目的是通过改变节点的位置来满足平衡二叉树的定义。

    总体来说，平衡二叉树是一种重要的数据结构，具有很好的查找和插入性能。它通过保持树的平衡，提高了操作的效率。

    简介：

    • 平衡二叉树是一种自我平衡的二叉搜索树，它的左子树和右子树的高度差不超过1。
    • 平衡二叉树的基本操作包括插入、删除和查找，这些操作的时间复杂度均为O(log n)，其中n为树中节点的数量。
    • 平衡二叉树的主要应用场景包括计算机科学、数据结构和算法等领域。

    图示：

    以下是一个简单的平衡二叉树图示：

          50
     / \
    30  70
   / \  / \
  10 40 60 80

    • 1
    • 2
    • 3
    • 4
    • 5

    在这个平衡二叉树中，每个节点的左子树和右子树的高度差都不超过1。

    示例：

    以下是一个在Java中实现平衡二叉树的简单示例：

    public class AVLTree {
    class Node {
        int key;
        Node left, right;
        int height;

        public Node(int item) {
            key = item;
            left = right = null;
            height = 1;
        }
    }

    Node root;

    AVLTree(int key) {
        root = new Node(key);
    }

    AVLTree() {
        root = null;
    }

    int height(Node node) {
        if (node == null) return 0;
        return node.height;
    }

    Node insert(Node node, int key) {
        if (node == null) return new Node(key);
        if (key < node.key) {
            node.left = insert(node.left, key);
        } else if (key > node.key) {
            node.right = insert(node.right, key);
        } else { // Duplicate keys not allowed
            return node;
        }
        node.height = 1 + Math.max(height(node.left), height(node.right));
        return node;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41

    在这个示例中，定义了一个内部类Node来表示平衡二叉树的节点。每个节点都有一个键key和两个子节点left和right，以及一个表示节点高度的属性height。还定义了两个方法height和insert。height方法用于计算节点的高度，而insert方法则用于向平衡二叉树中插入一个新的节点。

    二，添加数据

    在Java中，平衡二叉树是一种常见的数据结构，它可以有效地组织和搜索数据。平衡二叉树是一种自我平衡的二叉搜索树，它的任何一个节点的左子树和右子树的高度差的绝对值不超过1。AVL树和红黑树是平衡二叉树的两种常见类型。

    下面是一个示例，展示如何在平衡二叉树中添加数据：

    首先，需要创建一个表示平衡二叉树节点的类：

    // 定义平衡二叉树的节点类
public class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

    // 构造方法
    public TreeNode(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    然后，可以创建一个表示平衡二叉树的类，并添加一个方法来添加数据：

    // 定义平衡二叉树类
public class AVLTree {
    TreeNode root;

    // 构造方法
    public AVLTree() {
        root = null;
    }

    // 添加数据的方法
    public void add(int value) {
        root = addRecursive(root, value);
    }

    // 递归添加数据的方法
    private TreeNode addRecursive(TreeNode current, int value) {
        if (current == null) {
            // 如果当前节点为空，则创建一个新节点作为根节点
            return new TreeNode(value);
        }

        // 根据值的大小决定添加到左子树还是右子树
        if (value < current.value) {
            current.left = addRecursive(current.left, value);
        } else if (value > current.value) {
            current.right = addRecursive(current.right, value);
        } else {
            // 如果值已经存在于树中，则不做任何操作
            return current;
        }

        // 更新当前节点的高度为左子树和右子树的最大高度+1
        current.height = 1 + Math.max(getHeight(current.left), getHeight(current.right));

        // 获取当前节点的平衡因子，检查是否失衡
        int balance = getBalance(current);

        // 如果当前节点失衡，则根据情况进行旋转操作
        if (balance > 1) {
            // 如果左子树的平衡因子大于1，则进行右旋操作
            return rightRotate(current);
        } else if (balance < -1) {
            // 如果右子树的平衡因子小于-1，则进行左旋操作
            return leftRotate(current);
        } else {
            // 如果平衡因子为0，则不做任何操作，返回当前节点指针
            return current;
        }
    }

    // 计算节点的高度的方法
    private int getHeight(TreeNode node) {
        if (node == null) {
            return 0;
        } else {
            return node.height;
        }
    }

    // 计算节点的平衡因子的方法（左子树高度-右子树高度）
    private int getBalance(TreeNode node) {
        if (node == null) {
            return 0;
        } else {
            return getHeight(node.left) - getHeight(node.right);
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68

    三，删除数据

    在Java中，平衡二叉树是一种常见的数据结构，它可以有效地组织和搜索数据。平衡二叉树是一种自我平衡的二叉搜索树，它的任何一个节点的左子树和右子树的高度差的绝对值不超过1。AVL树和红黑树是平衡二叉树的两种常见类型。

    下面是一个示例，展示如何在平衡二叉树中删除数据：

    首先，需要创建一个表示平衡二叉树节点的类：

    // 定义平衡二叉树的节点类
public class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

    // 构造方法
    public TreeNode(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    然后，可以创建一个表示平衡二叉树的类，并添加一个方法来删除数据：

    // 定义平衡二叉树类
public class AVLTree {
    TreeNode root;

    // 构造方法
    public AVLTree() {
        root = null;
    }

    // 删除数据的方法
    public void remove(int value) {
        root = removeRecursive(root, value);
    }

    // 递归删除数据的方法
    private TreeNode removeRecursive(TreeNode current, int value) {
        if (current == null) {
            // 如果当前节点为空，则不做任何操作，返回null
            return null;
        }

        // 根据值的大小决定从左子树还是右子树中删除数据
        if (value < current.value) {
            current.left = removeRecursive(current.left, value);
        } else if (value > current.value) {
            current.right = removeRecursive(current.right, value);
        } else {
            // 如果值等于当前节点的值，则根据子节点的情况进行处理
            if (current.left == null && current.right == null) {
                // 如果当前节点没有子节点，则直接删除当前节点，返回null
                return null;
            } else if (current.left == null) {
                // 如果当前节点只有右子节点，则直接删除当前节点，并返回右子节点作为新的节点
                return current.right;
            } else if (current.right == null) {
                // 如果当前节点只有左子节点，则直接删除当前节点，并返回左子节点作为新的节点
                return current.left;
            } else {
                // 如果当前节点有两个子节点，则找到右子树中的最小节点作为新的节点，并删除该最小节点
                TreeNode minNode = findMinNode(current.right);
                current.value = minNode.value;
                current.right = removeRecursive(current.right, minNode.value);
            }
        }

        // 更新当前节点的高度为左子树和右子树的最大高度+1
        current.height = 1 + Math.max(getHeight(current.left), getHeight(current.right));

        // 获取当前节点的平衡因子，检查是否失衡
        int balance = getBalance(current);

        // 如果当前节点失衡，则根据情况进行旋转操作
        if (balance > 1) {
            // 如果左子树的平衡因子大于1，则进行右旋操作
            return rightRotate(current);
        } else if (balance < -1) {
            // 如果右子树的平衡因子小于-1，则进行左旋操作
            return leftRotate(current);
        } else {
            // 如果平衡因子为0，则不做任何操作，返回当前节点指针
            return current;
        }
    }

    // 计算节点的高度的方法
    private int getHeight(TreeNode node) {
        if (node == null) {
            return 0;
        } else {
            return node.height;
        }
    }

    // 计算节点的平衡因子的方法（左子树高度-右子树高度）
    private int getBalance(TreeNode node) {
        if (node == null) {
            return 0;
        } else {
            return getHeight(node.left) - getHeight(node.right);
        }
    }
    // 找到右子树中的最小节点的方法（递归）
    private TreeNode findMinNode(TreeNode node) {
        if (node == null) {
            return null;
        } else if (node.left == null) {
            return node;
        } else {
            return findMinNode(node.left);
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
  • 相关阅读:
    Android中如何知道我使用的是 AndroidX 库还是 Support Library
    SpringCloud--链路追踪之Sleuth的简单使用
    Aocoda-RC F405V2 FC(STM32F405RGT6 v.s. AT32F435RGT7) IO Definitions
    Android-IO底层原理看序列化
    Docker 镜像的创建
    java毕业设计广告投放mybatis+源码+调试部署+系统+数据库+lw
    “蔚来杯“2022牛客暑期多校训练营2
    java lombok框架
    Vue 重要内置关系：VueComponent.prototype.__proto__ === Vue.prototype及原型链图解
    xss漏洞及排查
  • 原文地址：https://blog.csdn.net/m0_62617719/article/details/132926700