【数据结构与算法】平衡二叉树（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. 把当前节点的左子树设置为新节点。
    在这里插入图片描述

代码实现：

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

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/65302.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Softing工业获得自动化产品安全开发流程认证

Softing工业获得自动化产品安全开发流程认证

Softing工业获得了TV Sd颁发的IEC 62443-4-1产品安全开发流程认证。 &#xff08;IEC 62443-4-1认证确保网络安全&#xff09; 截至2023年6月&#xff0c;位于德国哈尔和纽伦堡的工厂以及罗马尼亚克卢日的Softing工业研发部门已获得IEC 62443-4-1:2018标准的认证。该认证流程由…
阅读更多...
Webpack5新手入门简单配置

Webpack5新手入门简单配置

1.初始化项目 yarn init -y 2.安装依赖 yarn add -D webpack5.75.0 webpack-cli5.0.0 3.新建index.js 说明&#xff1a;写入下面的一句话 console.log("hello webpack"); 4.执行命令 说明&#xff1a;如果没有安装webpack脚手架就不能执行yarn webpack&#xff08…
阅读更多...
k8sday02

k8sday02

第四章 实战入门 本章节将介绍如何在kubernetes集群中部署一个nginx服务&#xff0c;并且能够对其进行访问。 Namespace ​ Namespace是kubernetes系统中的一种非常重要资源&#xff0c;它的主要作用是用来实现多套环境的资源隔离或者多租户的资源隔离。 ​ 默认情况下&…
阅读更多...
linux手动安装 golangci-lint-1.53.3-linux-386.rpm

linux手动安装 golangci-lint-1.53.3-linux-386.rpm

首先还是 去下载对应的 rpm 包 https://github.com/golangci/golangci-lint/releases 然后上传到 服务器/usr/local 目录下 执行安装命令 sudo rpm -ivh golangci-lint-1.53.3-linux-386.rpm 查看版本 golangci-lint --version
阅读更多...
Nginx与docker配置安装

Nginx与docker配置安装

目录&#xff1a; Nginx的安装配置&#xff1a; 1、安装依赖包&#xff1a; 2、下载Nginx安装包&#xff1a; 3、解压Nginx压缩包&#xff1a; 4、配置Nginx编译环境&#xff1a; 5、编译并安装Nginx&#xff1a; 6、安装完Nginx后&#xff0c;可以切换到Nginx的安装目录…
阅读更多...
使用MIT Kerberos Ticket Manager在windows下浏览器访问hadoop页面

使用MIT Kerberos Ticket Manager在windows下浏览器访问hadoop页面

Author : Spinach | GHB Link : http://blog.csdn.net/bocai8058文章目录 前言准备配置说明安装Firefox浏览器安装MIT Kerberos Ticket Manager客户端配置krb5.ini文件配置MIT Kerberos Ticket Manager客户端配置Firefox浏览器代理参数 访问WebUI 前言 kerberos是一种计算机…
阅读更多...
vite项目中使用@代表根路径

vite项目中使用@代表根路径

1.配置vite.config.ts import { defineConfig } from vite import vue from vitejs/plugin-vue import path from pathexport default defineConfig({plugins: [vue()],resolve: {alias:{: path.resolve(__dirname, src) }} })2.报错path和__dirname 找不到模块“path”或其相…
阅读更多...
实力认证！TDengine 入选 Gartner 中国数据分析与人工智能技术成熟度曲线

实力认证！TDengine 入选 Gartner 中国数据分析与人工智能技术成熟度曲线

近日&#xff0c;国际权威研究机构 Gartner 发布了《2023 年中国数据分析及人工智能技术成熟度曲线》&#xff08;即《Hype Cycle for Data, Analytics and AI in China, 2023》&#xff09;报告&#xff0c;TDengine 成功入选实时数据管理领域代表产品。 作为评估全球新技术成…
阅读更多...
MySQL— 基础语法大全及操作演示！！

MySQL— 基础语法大全及操作演示！！

MySQL—— 基础 一、MySQL概述1.1 、数据库相关概念1.2 、MySQL 客户端连接1.3 、数据模型 二、SQL2.1、SQL通用语法2.2、SQL分类2.3、DDL2.4、DML2.5、DQL2.6、DCL 三、函数四、约束五、多表查询六、事务 一、MySQL概述 1.1 、数据库相关概念 数据库、数据库管理系统、SQL&a…
阅读更多...
STM32自带的DSP库的滤波初体验（一）

STM32自带的DSP库的滤波初体验（一）

最近在弄STM32自带的DSP库里的滤波&#xff0c;记录一下&#xff1a; arm_fir_instance_q15 instance_q15_S; #define NUM_TAPS 16 //滤波系数的个数 #define BLOCK_SIZE 32 q15_t firStateF32[BLOCK_SIZE NUM_TAPS]; q15_t Fir_Coeff[NUM_TAPS] {-79, -136, 312, 6…
阅读更多...
Docker mysql+nacos单机部署

Docker mysql+nacos单机部署

docker 网络创建 由于nacos需要访问mysql的数据&#xff0c;因此mysql容器和nacos容器之间需要进行通信。容器间通信有很多方式&#xff0c;在这里采用同一网络下的方式进行实现。因此需要创建网络。创建网络的命令如下&#xff1a; docker network create --driver bridge n…
阅读更多...
【el-image图片查看时 样式穿透表格问题】

【el-image图片查看时 样式穿透表格问题】

element-ui el-image图片查看 样式混乱 解决方式 ::v-deep(.el-table__cell) {position: static !important; // 解决el-image 和 el-table冲突层级冲突问题 }加个样式即可
阅读更多...
Qt5.14.2+QtCreator+PDB 查看源码

Qt5.14.2+QtCreator+PDB 查看源码

1. 在Creator添加源码 2. 安装PDB文件 Qt下载时没有整合最新的PDB文件下载&#xff0c;如果没有安装PDB文件&#xff0c;即使安装了src也无法调试。 双击MaintenanceTool.exe->设置->资料档案库->临时资料档案库->添加按钮&#xff0c;添加如下下载源&#xff1a…
阅读更多...
MongoDB：Unrecognized option: storage

MongoDB：Unrecognized option: storage

MongoDB一直显示 Unrecognized option: storage try ‘mongod --help’ for more information 意思是我们配置的config文件出了问题。 说明&#xff1a;MongoDB采用的是YAML格式&#xff0c;所以我们只需要稍微改改就好。 在storage前面&#xff1a;没有空格 下面两行最前面…
阅读更多...
机加工行业如何做好生产管理？

机加工行业如何做好生产管理？

导 读 ( 文/ 2715 ) 机加工行业是制造业中的一个重要领域&#xff0c;它涉及将原材料通过机械设备进行切削、加工和加工成形的过程。 机械加工通常从原料开始&#xff0c;通过不断的切削或去除材料的过程&#xff0c;逐步将工件加工成所需的形状和尺寸。这个过程中&#xff0…
阅读更多...
PHP实现保质期计算器

PHP实现保质期计算器

1.php实现保质期计算&#xff0c; 保质期日期可选&#xff0c;天 、月、年 2. laravel示例 /*** 保质期计算器* return void*/public function expirationDateCal(){$produce_date $this->request(produce_date); // 生产日期$warranty_date $this->reques…
阅读更多...
TCP三次握手、四次握手过程，以及原因分析

TCP三次握手、四次握手过程，以及原因分析

TCP的三次握手和四次挥手实质就是TCP通信的连接和断开。 三次握手&#xff1a;为了对每次发送的数据量进行跟踪与协商&#xff0c;确保数据段的发送和接收同步&#xff0c;根据所接收到的数据量而确认数据发送、接收完毕后何时撤消联系&#xff0c;并建立虚连接。 四次挥手&…
阅读更多...
机械厂工厂360全景展示拍摄制作，以便随时随地进行展示和更新

机械厂工厂360全景展示拍摄制作，以便随时随地进行展示和更新

随着5G互联网技术的不断发展&#xff0c;线上全景虚拟展示已经成为了一种重要的展示方式。在工业领域中&#xff0c;厂区线上全景虚拟展示的应用也越来越广泛。 厂区线上vr全景虚拟展示是VR全景制作公司公司借助VR全景和web3d开发技术把企业的环境、研发、生产、产品、质检、仓…
阅读更多...
解决Vue+Element UI使用el-dropdown(下拉菜单)国际化时菜单label信息没有刷新的情况

解决Vue+Element UI使用el-dropdown(下拉菜单)国际化时菜单label信息没有刷新的情况

说明&#xff1a;该篇博客是博主一字一码编写的&#xff0c;实属不易&#xff0c;请尊重原创&#xff0c;谢谢大家&#xff01; 问题描述 在默认中文时&#xff0c;点击布局大小下拉菜单正常显示中文&#xff0c;此时切换至英文时&#xff0c;再次点击下拉菜单&#xff0c;还…
阅读更多...
Llama 2：开放基础和微调聊天模型

Llama 2：开放基础和微调聊天模型

介绍 大型语言模型(llm)作为高能力的人工智能助手，在复杂的推理任务中表现出色，这些任务需要广泛领域的专家知识，包括编程和创意写作等专业领域。它们可以通过直观的聊天界面与人类进行交互，这在公众中得到了迅速而广泛的采用。 法学硕士的能力是显著的考虑到训练的表面上…
阅读更多...
最新文章

Copyright @ 2022~2023