当前位置: 首页 > news >正文

平衡二叉树旋转机制

概念

        平衡二叉树的旋转机制是一种通过对树进行旋转操作来保持其平衡的方法。

分类

 平衡二叉树的旋转机制包括两种基本类型的旋转:左旋和右旋,以及它们的组合。

左旋

        左旋是将一个节点的右子节点旋转到它的位置上,同时将该节点移到其左侧,并重新连接其子节点。

 简单左旋步骤

  • 确定支点:从添加的节点开始,不断地往父节点找不平衡地节点
  • 以不平衡的点作为支点
  • 把支点左旋降级,变成左子节点
  • 晋升原来的右子节点

复杂左旋步骤

  • 确定支点:从添加的节点开始,不断地往父节点找不平衡地节点
  • 以不平衡的点作为支点
  • 将根节点的右侧往左拉
  • 原来的右子节点变为新的根节点,并把多余的左子节点拿出来,给已降级的根节点当右子节点

右旋 

        右旋是将一个节点的左子节点旋转到它的位置上,同时将该节点移到其右侧,并重新连接其子节点。

 简单右旋步骤

  • 确定支点:从添加的节点开始,不断地往父节点找不平衡地节点
  • 以不平衡的点作为支点
  • 把支点右旋降级,变成右子节点
  • 晋升原来的左子节点

 复杂右旋步骤

  • 确定支点:从添加的节点开始,不断地往父节点找不平衡地节点
  • 以不平衡的点作为支点
  • 将根节点的左侧往右拉
  • 原来的左子节点变为新的根节点,并把多余的右子节点拿出来,给已降级的根节点当左子节点

 平衡二叉树需要旋转的情况

  • 左左:根节点的左子树的左子树有节点插入,导致二叉树不平衡【一次旋转】
  • 左右:根节点的左子树的右子树有节点插入,导致二叉树不平衡【先局部左旋,在整体右旋】
  • 右右:根节点的右子树的右子树有节点插入,导致二叉树不平衡【一次旋转】
  • 右左:根节点的右子树的左子树有节点插入,导致二叉树不平衡【先局部右旋,在整体左旋】

相关文章:

平衡二叉树旋转机制

概念 平衡二叉树的旋转机制是一种通过对树进行旋转操作来保持其平衡的方法。 分类 平衡二叉树的旋转机制包括两种基本类型的旋转:左旋和右旋,以及它们的组合。 左旋 左旋是将一个节点的右子节点旋转到它的位置上,同时将该节点移到其左侧&…...

深入浅出C++ ——C++11

文章目录 一、C11简介二、列表初始化二、声明四、范围for循环五、STL中的变化六、右值引用和移动语义1. 什么是左值?什么是左值引用?2. 左值引用与右值引用比较3. 右值引用使用场景和意义4. 完美转发 新的类功能默认成员函数类成员变量初始化defaultdele…...

智能座舱3.0阶段,看全球巨头如何打造更具“价值”的第三空间

面向中国这一全球最大的汽车电动化与智能化单一市场,作为全球第七大汽车技术供应商的FORVIA佛瑞亚集团开始全面发力。 在2023年上海国际车展上,FORVIA佛瑞亚携旗下佛吉亚与海拉一系列突破性技术和互动体验亮相,展示了对电气化与能源管理、安…...

【Linux】入门介绍

🌱博客主页:大寄一场. 🌱系列专栏:Linux 😘博客制作不易欢迎各位👍点赞⭐收藏➕关注​ 目录 前言 Linux背景介绍 1.发展史 UNIX发展的历史 Linux发展历史 2. 开源 3. 官网 4. 企业应用现状 5. 发行版…...

【Python】序列类型②-元组

文章目录 1.元组简介2.元组的定义2.1定义只有一个元素的元组 3.元组的下标访问4.元组的常用方法5.使用in判断是否存在元素6.多元赋值操作 1.元组简介 元组和列表一样可以存放多个,不同数据类型的元素 与列表最大的不同就是:列表是可变的,而元组不可变 2.元组的定义 元组的定义:…...

循环的数字

循环的数字 题目描述 你曾经因为看见一样的东西一遍又一遍地重复、循环而对电视节目感到厌烦么?好吧,虽然我并不关心电视节目的好坏,不过有时却也很像那样不断循环的数字。 让我们假定两个不同的正整数 ( n , m ) (n, m) (n,m) 是循环的&…...

MySQL查询之聚合函数查询

0. 数据源 student.sql文件。 /*Navicat Premium Data TransferSource Server : localhost_3306Source Server Type : MySQLSource Server Version : 80016Source Host : localhost:3306Source Schema : testdbTarget Server Type : MySQLTa…...

普通2本,去过字节外包,到现在年薪25W+的测试开发,我的2年转行心酸经历...

个人简介 我是一个普通二本大学机械专业毕业,17年毕业,19年转行,目前做IT行业的软件测试已经有3年多,职位是高级测试工程师,坐标上海… 我想现在我也有一点资格谈论关于转行这个话题;希望你在决定转行之前…...

util.callbackify

util.callbackify(original) 将 async 异步函数(或者一个返回值为 Promise 的函数)转换成遵循异常优先的回调风格的函数,例如将 (err, value) > ... 回调作为最后一个参数。 在回调函数中,第一个参数为拒绝的原因(如…...

解决使用CLIP模型时TypeError: Cannot handle this data type: (1, 1, 224, 224), |u1

想提供Huggingface的transformer库实现多模态模型CLIP的推断,结果报错 (myenv) rootd27d1ff1836c:/home/model_test# python3 CLIP.py ftfy or spacy is not installed using BERT BasicTokenizer instead of ftfy. Traceback (most recent call last): File “/hom…...

Mysql第二章 多表查询的操作

这里写自定义目录标题 一 外连接与内连接的概念sql99语法实现 默认是内连接sql99语法实现左外连接,把没有部门的员工也查出来sql99语法实现右外连接,把没有人的部门查出来sql99语法实现满外连接,mysql不支持这样写mysql中如果要实现满外连接的…...

ESP32-CAM:TinyML 图像分类——水果与蔬菜

目录 故事 硬件参数: 在 Arduino IDE 上安装 ESP32-Cam 使用 BLINK 测试电路板 测试无线网络 运行您的 Web 服务器 水果与蔬菜-图像分类 下载数据集 使用 Edge Impulse Studio 训练模型...

如何防止订单重复支付

想必大家对在线支付都不陌生,今天和大家聊聊如何防止订单重复支付。 看看订单支付流程 我们来看看,电商订单支付的简要流程: 订单钱包支付流程 从下单/计算开始: 下单/结算:这一步虽然不是直接的支付起点,但…...

不是那么快乐的五一

大家好,我是记得诚。 五一假期结束了,明天开始上班了。 这个假期没休息好,也没出去玩。 放假前一天,接到通知让加班。 第一天就去公司加班了,属实很难受,我心想如果别人有了出远门的安排,还…...

Maven命令和配置详解

Maven命令和配置详解 1. pom基本结构2. build基本结构3. Maven命令详解3.1 打包命令3.2 常用命令3.3 批量修改版本-父子pom4. Maven配置详解4.1 settings.xml4.2 项目内的maven工程结构Maven POM构建生命周期工程实践1. pom基本结构 <?xml versi...

P3029 [USACO11NOV]Cow Lineup S 双指针 单调队列

“五一”小长假来了趟上海&#xff0c;在倒数第二天终于有时间做了一会儿题目&#xff0c;A了之后过来写一篇题解 【问题描述】 农民约翰雇一个专业摄影师给他的部分牛拍照。由于约翰的牛有好多品种&#xff0c;他喜欢他的照片包含每个品种的至少一头牛。 约翰的牛都站在一条沿…...

数据结构与算法之链表: Leetcode 83. 删除排序链表中的重复元素 (Typescript版)

删除排序链表中的重复元素 https://leetcode.cn/problems/remove-duplicates-from-sorted-list/ 描述 给定一个已排序的链表的头 head &#xff0c; 删除所有重复的元素&#xff0c;使每个元素只出现一次 。返回 已排序的链表 示例 1 输入&#xff1a;head [1,1,2] 输出&…...

ubuntu16.04升级到20.04后报错 By not providing “FindEigen.cmake“

编译问题&#xff1a; CMake Error at modules/perception/lidar/CMakeLists.txt:14 (find_package): By not providing "FindEigen.cmake" in CMAKE_MODULE_PATH this project has asked CMake to find a package configuration file provided by "Eigen&…...

设计模式——模板方法模式

是什么&#xff1f; 在我们的实际开发中尝尝会遇到这种问题&#xff1a;在设计一个系统时知道了算法所需要的关键步骤&#xff0c;而且确定了这些步骤的执行顺序&#xff0c;但是某些步骤的具体实现还不知道&#xff0c;或者说某些步骤的实现与具体的环境相关&#xff0c;例如每…...

15 | Qt的自定义信号

1 前提 Qt 5.14.2 2 具体操作 2.1 自定义信号 2.1.1 UI界面设置 2.1.1.1 widget.ui 2.1.1.2 setdialog.ui 2.1.2 headers 2.1.2.1 widget.h #ifndef WIDGET_H #define WIDGET_H#include <QWidget>QT_BEGIN_NAMESPACE namespace Ui {class Widget; } QT_END_NAMESP…...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

label-studio的使用教程(导入本地路径)

文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

模型参数、模型存储精度、参数与显存

模型参数量衡量单位 M&#xff1a;百万&#xff08;Million&#xff09; B&#xff1a;十亿&#xff08;Billion&#xff09; 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的&#xff0c;但是一个参数所表示多少字节不一定&#xff0c;需要看这个参数以什么…...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

UDP(Echoserver)

网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法&#xff1a;netstat [选项] 功能&#xff1a;查看网络状态 常用选项&#xff1a; n 拒绝显示别名&#…...

cf2117E

原题链接&#xff1a;https://codeforces.com/contest/2117/problem/E 题目背景&#xff1a; 给定两个数组a,b&#xff0c;可以执行多次以下操作&#xff1a;选择 i (1 < i < n - 1)&#xff0c;并设置 或&#xff0c;也可以在执行上述操作前执行一次删除任意 和 。求…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

【决胜公务员考试】求职OMG——见面课测验1

2025最新版&#xff01;&#xff01;&#xff01;6.8截至答题&#xff0c;大家注意呀&#xff01; 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:&#xff08; B &#xff09; A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

Matlab | matlab常用命令总结

常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...