二叉平衡树（左单旋，右单旋，左右双旋、右左双旋）

一、AVL树（二叉平衡树：高度平衡的二叉搜索树）

0、二叉平衡树

左右子树高度差不超过1的二叉搜索树。

public class AVLTree{
    static class AVLTreeNode {
        public TreeNode left = null; // 节点的左孩子
        public TreeNode right = null; // 节点的右孩子
        public TreeNode parent = null; // 节点的双亲
        public int val = 0;
        public int bf = 0; // 当前节点的平衡因子=右子树高度-左子树的高度
        
        public TreeNode(int val) {
            this.val = val;
        }
    }
    public TreeNode root;

    //插入函数等....
    
}
// 将AVLTreeNode定义为AVLTree的静态内部类

1、查找

二叉平衡树的查找和二叉搜索树的方法是一样的，因为它们具有相同的结构特点——右孩子val值小于根节点val，根节点val小于左孩子val。

2、插入

二叉搜索树的插入一定是插入到叶子节点的位置。
二叉平衡树将节点插入到叶子节点之后，要维护左右子树的平衡因此可能还要进行旋转操作。

  1. 先将数据插入到AVL树当中（和二叉搜索数一样）
  2. 插入进去后，根据平衡因子来进行对树的调整

3、插入后无需旋转的情况：

注意各节点bf值得变化

image.png

4、右单旋&左单旋:

对parent进行右单旋就是把parent.left提拔成根节点
注意各节点bf值得变化
image.png
对parent进行左单旋就是把parent.right提拔成根节点
注意各节点bf值得变化
image.png

补充：相对与根节点各个节点的名称，后续得图会用到这些名称

image.png

image.png
image.png

树parent是pParent(parent.parent)的一棵子树，对parent进行旋转后需要将新的根节点的parent指针指向pParent.

image.png
image.png

//检查 当前是不是就是根节点
if(parent == root) {
    root = subL;
    // subL.parent等于parent，subL提拔成了根节点，所以要将subL.parent设置为null,
    subL.parent = null;
}else {
    //不是根节点，判断这棵子树是左子树还是右子树
    if(pParent.left == parent) {
        pParent.left = subL;
    }else {
        pParent.right = subL;
    }
    subL.parent = pParent;
}

5、左右双旋 &右左双旋

  1. 注意指针指向
  2. 注意维护bf

右左双旋过程图：

image.png
image.png

左右双旋过程图：

image.png
image.png

下面这两幅图介绍了左右双旋时如何维护个节点的bf值（右左双选的不想画了，太累了）

image.png
image.png

/**
 * 左右双旋
 * @param parent
 */
private void rotateLR(TreeNode parent) {
    TreeNode subL = parent.left;
    TreeNode subLR = subL.right;
    int bf = subLR.bf;

    rotateLeft(parent.left);
    rotateRight(parent);

    // 这个规律很重要，中间状态的bf值不重要，根据初始状态的bf值来修改平衡状态的bf值
    if(bf == -1) {
        parent.bf = 1;
        subL.bf = 0;
        subLR.bf = 0;
    }else if(bf == 1){
        parent.bf = 0;
        subL.bf = -1;
        subLR.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);

    // 这个规律很重要，中间状态的bf值不重要，根据初始状态的bf值来修改平衡状态的bf值
    if(bf == 1) {
        parent.bf = -1;
        subR.bf = 0;
        subRL.bf = 0;
    }else if(bf == -1){
        parent.bf = 0;
        subR.bf = 1;
        subRL.bf = 0;
    }
}

6、总代码

package org.example;

/**
 * @Author 12629
 * @Description：
 */
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;
        }
    }

    public TreeNode root;//根节点

    public boolean insert(int val) {
        TreeNode node = new TreeNode(val);
        if(root == null) {
            root = node;
            return true;
        }

        TreeNode parent = null;
        TreeNode cur = root;
        while (cur != null) {
            if(cur.val < val) {
                parent = cur;
                cur = cur.right;
            }else if(cur.val == val) {
                return false;
            }else {
                parent = cur;
                cur = cur.left;
            }
        }
        //cur == null
        if(parent.val < val) {
            parent.right = node;
        }else {
            parent.left = node;
        }
        //
        node.parent = parent;
        cur = node;
        // 平衡因子 的修改
        while (parent != null) {
            //先看cur是parent的左还是右  决定平衡因子是++还是--
            if(cur == parent.right) {
                //如果是右树，那么右树高度增加 平衡因子++
                parent.bf++;
            }else {
                //如果是左树，那么左树高度增加 平衡因子--
                parent.bf--;
            }

            //检查当前的平衡因子 是不是绝对值 1  0  -1
            if(parent.bf == 0) {
                //说明已经平衡了
                break;
            }else if(parent.bf == 1 || parent.bf == -1) {
                //继续向上去修改平衡因子
                cur = parent;
                parent = cur.parent;
            }else {
                //右树高-》需要降低右树的高度
                if(parent.bf == 2) {
                    if(cur.bf == 1) {
                        //左旋
                        rotateLeft(parent);
                    }else {
                        //cur.bf == -1
                        rotateRL(parent);
                    }
                }else {
                    //parent.bf == -2 左树高-》需要降低左树的高度
                    if(cur.bf == -1) {
                        //右旋
                        rotateRight(parent);
                    }else {
                        //cur.bf == 1
                        rotateLR(parent);
                    }
                }
                //上述代码走完就平衡了
                break;
            }
        }
        return true;
    }

    private void rotateRL(TreeNode parent) {
        TreeNode subR = parent.right;
        TreeNode subRL = subR.left;
        int bf = subRL.bf;

        rotateRight(parent.right);
        rotateLeft(parent);

        if(bf == 1) {
            parent.bf = -1;
            subR.bf = 0;
            subRL.bf = 0;
        }else if(bf == -1){
            parent.bf = 0;
            subR.bf = 1;
            subRL.bf = 0;
        }
    }

    /**
     * 左右双旋
     * @param parent
     */
    private void rotateLR(TreeNode parent) {
        TreeNode subL = parent.left;
        TreeNode subLR = subL.right;
        int bf = subLR.bf;

        rotateLeft(parent.left);
        rotateRight(parent);

        if(bf == -1) {
            parent.bf = 1;
            subL.bf = 0;
            subLR.bf = 0;
        }else if(bf == 1){
            parent.bf = 0;
            subL.bf = -1;
            subLR.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 {
                pParent.right = subR;
            }
            subR.parent = pParent;
        }
        subR.bf = parent.bf = 0;
    }

    /**
     * 右单旋
     * @param parent
     */
    private void rotateRight(TreeNode parent) {
        TreeNode subL = parent.left;
        TreeNode subLR = subL.right;
        parent.left = subLR;
        subL.right = parent;
        //没有subLR
        if(subLR != null) {
            subLR.parent = parent;
        }
        //必须先记录
        TreeNode pParent = parent.parent;
        parent.parent = subL;
        //检查 当前是不是就是根节点
        if(parent == root) {
            root = subL;
            // subL.parent等于parent，subL提拔成了根节点，所以要将subL.parent设置为null.
            subL.parent = null;
        }else {
            //不是根节点，判断这棵子树是左子树还是右子树
            if(pParent.left == parent) {
                pParent.left = subL;
            }else {
                pParent.right = subL;
            }
            subL.parent = pParent;
        }
        subL.bf = 0;
        parent.bf = 0;
    }
    //中序遍历的结果是有序的 就能说明当前树 一定是AVL树吗？  不一定的
    private boolean inorder(TreeNode root){
        return inorderHelper(root,Long.MIN_VALUE);
    }
    private boolean inorderHelper(TreeNode root,long pre) {
        if(root == null) {
            return true;
        }
        if(!inorderHelper(root.left,pre)) {
            return false;
        }
        if(pre < root.val){
            pre = root.val;
            if(!inorderHelper(root.right,pre)){
                return false;
            }
            return true;
        }
        return false;
    }

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

    public 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("这个节点："+root.val+" 平衡因子异常");
            return false;
        }

        return Math.abs(leftH-rightH) <= 1
                && isBalanced(root.left)
                && isBalanced(root.right)
                &&inorder(root);// 不仅要左右平衡，还要排序
    }
}

二叉平衡树的适用和不适用场景如下:
适用场景:

  1. 动态数据集合:
    • 当需要频繁地对数据集合进行插入、删除和查找操作时,二叉平衡树是一个很好的选择。它能够保持O(log n)的时间复杂度,避免了普通二叉搜索树在极端情况下退化为链表的问题。
  2. 需要保持数据有序性:
    • 二叉平衡树能够维护数据的有序性,同时也具有较高的查找效率。这在需要保持数据有序性并进行快速查找的场景中非常适用,例如索引数据库、缓存系统等。
  3. 需要高效的范围查询:
    • 由于二叉平衡树能够维护数据的有序性,因此可以很高效地进行范围查询,例如查找某个区间内的所有元素。这在一些需要范围查询的应用中很有用,如地理信息系统、网络路由表管理等。

不适用场景:

  1. 数据集合变化较小:
    • 如果数据集合的变化(插入、删除)很少,使用普通的二叉搜索树可能更加简单高效,因为不需要维护平衡性。
  2. 内存使用要求苛刻:
    • 二叉平衡树需要存储额外的平衡信息(如高度、平衡因子),会占用更多的内存。如果内存使用非常受限,可能需要选择其他更简单的数据结构。
  3. 对写操作要求极高:
    • 由于需要进行平衡操作,二叉平衡树的写操作(插入和删除)会稍微慢于普通的二叉搜索树。如果对写操作的性能要求极高,可能需要考虑其他数据结构。

总的来说,二叉平衡树是一种非常实用的数据结构,在需要高效管理动态有序数据集合的场景中表现优秀。但在某些特定的应用需求中,可能需要根据具体情况来权衡选择适合的数据结构。

** 画图不易，求赞。有不理解的地方可以私信我，必回复！ **

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

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

相关文章

【Unity2D 2022：NPC】制作NPC

【Unity2D 2022：NPC】制作NPC

一、创建NPC角色 1. 创建JambiNPC并同时创建Jambi站立动画 &#xff08;1&#xff09;点击第一张图片&#xff0c;按住shift不松&#xff0c;再选中后两张图片&#xff0c;拖到层级面板中 &#xff08;2&#xff09;将动画资源文件保存到Animation Clips文件夹中 &#xff08;…
阅读更多...
三维引擎实践 - OSG渲染线程创建过程（未完待续）

三维引擎实践 - OSG渲染线程创建过程（未完待续）

一&#xff1a;概述 一个3D应用程序&#xff0c;在创建好图形窗口之后&#xff0c;就要使用该窗口的OpenGL上下文进行渲染相关工作了&#xff0c;本节分析下OSG源码中渲染线程的建立过程。 二&#xff1a;OSG渲染线程用到了哪些类&#xff1f; 1. GraphicsThread 类&#xff0c…
阅读更多...
政安晨：【Keras机器学习示例演绎】（五十二）—— 使用门控残差和变量选择网络进行分类

政安晨：【Keras机器学习示例演绎】（五十二）—— 使用门控残差和变量选择网络进行分类

目录 简介 数据集 安装准备 数据准备 定义数据集元数据 创建用于训练和评估的 tf.data.Dataset 创建模型输入 对输入特征进行编码 实施门控线性单元 实施门控余留网络 实施变量选择网络 创建门控残差和变量选择网络模型 编译、训练和评估模型 政安晨的个人主页&am…
阅读更多...
怎么判断自己是否适合学习PMP？

怎么判断自己是否适合学习PMP？

判断自己是否适合学习PMP项目管理专业人士认证&#xff0c;可以从以下几个方面进行考量&#xff1a; 1、职业发展需求&#xff1a; 如果您在项目管理领域工作&#xff0c;或计划未来从事相关工作&#xff0c;PMP认证能显著提升您的竞争力。 对于项目经理、产品经理、技术领导…
阅读更多...
什么是边缘计算？创造一个更快、更智慧、更互联的世界

什么是边缘计算？创造一个更快、更智慧、更互联的世界

前言 如今&#xff0c;数十亿物联网传感器广泛部署在零售商店、城市街道、仓库和医院等各种场所&#xff0c;正在生成大量数据。从这些数据中更快地获得洞察&#xff0c;意味着可以改善服务、简化运营&#xff0c;甚至挽救生命。但要做到这一点&#xff0c;企业需要实时做出决策…
阅读更多...
【ESP32】打造全网最强esp-idf基础教程——16.SmartConfig一键配网

【ESP32】打造全网最强esp-idf基础教程——16.SmartConfig一键配网

SmartConfig一键配网 一、SmartConfig知识扫盲 在讲STA课程的时候&#xff0c;我们用的是代码里面固定的SSID和密码去连接热点&#xff0c;但实际应用中不可能这么弄&#xff0c;我们得有办法把家里的WiFi SSID和密码输入到设备里面去&#xff0c;对于带屏带输入设备还…
阅读更多...
15.x86游戏实战-汇编指令jmp call ret

15.x86游戏实战-汇编指令jmp call ret

免责声明&#xff1a;内容仅供学习参考&#xff0c;请合法利用知识&#xff0c;禁止进行违法犯罪活动&#xff01; 本次游戏没法给 内容参考于&#xff1a;微尘网络安全 工具下载&#xff1a; 链接&#xff1a;https://pan.baidu.com/s/1rEEJnt85npn7N38Ai0_F2Q?pwd6tw3 提…
阅读更多...
【服务器】在Linux查看运行的Python程序，并找到特定的Python程序

【服务器】在Linux查看运行的Python程序，并找到特定的Python程序

在Linux查看运行的Python程序并找到特定的Python程序 写在最前面1. 使用ps命令查看所有Python进程查看详细信息 2. 使用pgrep命令查找Python进程ID 3. 使用top或htop命令使用top命令使用htop命令 4. 使用lsof命令查找Python进程打开的文件 5. 使用nvidia-smi命令查看GPU使用情况…
阅读更多...
Cancer Cell | 卞修武院士/时雨/平轶芳团队揭示胶质瘤巨噬细胞研究全新视角

Cancer Cell | 卞修武院士/时雨/平轶芳团队揭示胶质瘤巨噬细胞研究全新视角

胶质母细胞瘤&#xff08;glioblastoma&#xff0c;GBM&#xff09;作为最常见的恶性脑肿瘤之一&#xff0c;其肿瘤微环境高度复杂且侵袭性极强。肿瘤相关巨噬细胞&#xff08;TAMs&#xff09;在胶质瘤发展和免疫抑制中扮演着关键角色&#xff0c;尽管靶向TAMs的治疗策略已经取…
阅读更多...
68.SAP FICO - 记账码学习

68.SAP FICO - 记账码学习

目录 定义 用途 配置步骤 定义记账码 - OB41 配置会计科目类型 在会计中&#xff0c;“借”和“贷”是记账符号&#xff0c;代表了记账的方向。而在SAP中却没有大家熟知的记账符号“借”和“贷”&#xff0c;那SAP中如何录入凭证呢&#xff1f;其实&#xff0c;SA…
阅读更多...
MT3054 搭积木

MT3054 搭积木

1.思路&#xff1a; 把二维矩阵转化成一维编号&#xff0c;之后将编号使用并查集&#xff0c;看最后是否在同一个集合中即可。 2.代码&#xff1a; #include <bits/stdc.h> using namespace std; const int N 1e3 10; int n, m, cnt, root; int fa[N * N]; int dx[…
阅读更多...
09.C2W4.Word Embeddings with Neural Networks

09.C2W4.Word Embeddings with Neural Networks

往期文章请点这里 目录 OverviewBasic Word RepresentationsIntegersOne-hot vectors Word EmbeddingsMeaning as vectorsWord embedding vectors Word embedding processWord Embedding MethodsBasic word embedding methodsAdvanced word embedding methods Continuous Bag-…
阅读更多...
网络编程：各协议头（数据报格式）

网络编程：各协议头（数据报格式）

一、mac头 二、ip头 protocol——tcp/udp &#xff08;7&#xff09;TTL——生存时间 三、tcp头 四、udp头
阅读更多...
昇思大模型——MindFormers的使用----从零开始安装配置环境

昇思大模型——MindFormers的使用----从零开始安装配置环境

MindSpore Transformers套件的目标是构建一个大模型训练、微调、评估、推理、部署的全流程开发套件&#xff0c;提供业内主流的Transformer类预训练模型和SOTA下游任务应用&#xff0c;涵盖丰富的并行特性。期望帮助用户轻松的实现大模型训练和创新研发。 MindSpore Transform…
阅读更多...
centos更换yum源、安装Docker和换源

centos更换yum源、安装Docker和换源

所有操作都是在root权限下做的&#xff0c;切换root用户 命令&#xff1a;su root 使用ls /etc/yum*查看所有的关于yum的文件的路径 先安装wget 命令&#xff1a;yum install wget -y 命令&#xff1a;cd /etc/yum.repos.d进去&#xff0c;以便于操作 我们需要配置的是Cen…
阅读更多...
DNS 杂谈

DNS 杂谈

一、定义 DNS&#xff08;Domain Name System&#xff09;&#xff0c;域名系统&#xff0c;该系统记录域名和Ip地址的相互映射关系。用户访问互联网时&#xff0c;通过域名地址得到对应的IP地址&#xff0c;这个过程称为域名解析。DNS运行于UDP协议之上&#xff0c;使用的端口…
阅读更多...
react-类组件1

react-类组件1

类组件&#xff1a; import { Component } from "react";class App extends Component {constructor() {super();this.state {message: "xxxxx",};}render() {return (<div><div>{this.state.message}</div></div>);} }export d…
阅读更多...
Animate软件基础：重命名图层或文件夹

Animate软件基础：重命名图层或文件夹

默认情况下&#xff0c;Animate 会按照创建顺序向新图层分配名称&#xff1a;图层 1、图层 2&#xff0c;依此类推。为了更好地反映图层的内容&#xff0c;可以对图层进行重命名。 如果需要对图层或图层文件夹进行重命名&#xff0c;请执行下列操作之一&#xff1a; 双击时间轴…
阅读更多...
第三课网关作用

第三课网关作用

实验拓扑图&#xff1a; 基础配置&#xff1a; PC1的基础配置 PC2的基础配置&#xff1a; PC4的基础配置 AR1添加PC4网段: 并且添加pc1,pc2的网段。 并且添加pc1,pc2的网段。 原理&#xff1a;PC4先把数据交给100.100.100.1&#xff0c;交给了路由器&#xff0c;路由器再把数…
阅读更多...
图文讲解IDEA如何导入JDBC驱动包

图文讲解IDEA如何导入JDBC驱动包

前言 学习JDBC编程,势必要学会如何导入驱动包,这里笔者用图文的方式来介绍 视频版本在这里 50秒教你怎么导入驱动包然后进行JDBC编程的学习_哔哩哔哩_bilibili 忘记录音频了,大伙凑合着看 下载驱动包 https://mvnrepository.com/artifact/mysql/mysql-connector-java 去中…
阅读更多...
最新文章

Copyright @ 2022~2023