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

AVL树讲解

AVL树

  • 1. 概念
  • 2. AVL节点的定义
  • 3. AVL树插入
    • 3.1 旋转
  • 4.AVL树的验证

1. 概念

  1. AVL树是一种自平衡二叉搜索树。它的每个节点的左子树和右子树的高度差(平衡因子,我们这里按右子树高度减左子树高度)的绝对值不超过1。
  2. AVL的左子树和右子树都是AVL树。
  3. 比起二叉搜索树AVL树可以很好的优化二叉搜索树最坏的情况,使查询的效率达到O(log2 N)。

2. AVL节点的定义

和搜索二叉树节点相比,AVL树节点多了一个父节点和平衡因子(不是必要)需要维护。

template<class T>
typedef struct AVLTreeNode
{AVLTreeNode(const T& data):_pLeft(nullptr),_pRight(nullptr),_pParent(nullptr),_data(data),_bf(0){};//左节点、右节点、父节点AVLTreeNode<T>* _pLeft;AVLTreeNode<T>* _pRight;AVLTreeNode<T>* _pParent;T _data;//平衡因子int bf;
};

3. AVL树插入

和搜索二叉树的插入操作相比较,AVL树的插入需要多维护父节点和平衡因子。维护父节点比较简单,我们需要学习的是维护平衡因子。

当我们按照搜索二叉树的逻辑插入一个节点后,在插入这个节点之前父节点的平衡因子可能是-1/0/1这三种,如果该节点插入到父节点的左边需要将平衡因子减1,插入到右边则加1。所以插入之后平衡因子有这几种情况±1/0/±2。如果是±1,那么需要继续判断上面节点的平衡因子、如果是0,那么不需要判断了、如果是±2,那么就需要进行旋转操作

3.1 旋转

我们先说结论:1、旋转之后节点所在子树的高度会回到插入之前。2、旋转不会对上面节点平衡因子产生影响。

  1. 右单旋
    初始情况:
    在这里插入图片描述
// 右单旋void RotateR(Node* pParent){Node* parent = pParent->_parent;//变成局部的根Node* pParentL = pParent->_left;Node* pParentR = pParentL->_right;if (pParent == _proot)_proot = pParentL;pParent->_left = pParentR;if (pParentR)pParentR->_parent = pParent;pParentL->_left = pParent;pParent->_parent = pParentL;pParentL->_parent = parent;//只需要修改pParent和pParentL的平衡因子pParent->_bf = 0;pParentL->_bf = 0;return;}

旋转之后情况
在这里插入图片描述

  1. 左单旋
    初始情况:
    在这里插入图片描述
// 左单旋void RotateL(Node* pParent){Node* parent = pParent->_parent;//变成局部的根Node* pParentR = pParent->_right;Node* pParentL = pParentR->_left;//如果pParnet为根,则要修改根if (pParent == _proot)_proot = pParentR;pParent->_right = pParentL;if (pParentL)pParentL->_parent = pParent;pParentR->_left = pParent;pParent->_parent = pParentR;pParentR->_parent = parent;//只需要修改pParent和pParentR的平衡因子pParent->_bf = 0;pParentR->_bf = 0;return;}

旋转之后的情况:
在这里插入图片描述

  1. 左右双旋
    初始情况(插入可以插入到左边或右边,情况不同平衡因子也会不同):
    在这里插入图片描述
// 左右双旋void RotateLR(Node* pParent){Node* pParentL = pParent->_left;Node* pParentLR = pParentL->_right;int bf = pParentLR->_bf;RotateL(pParentL);RotateR(pParent);if (bf == 0){pParent->_bf = 0;pParentL->_bf = 0;pParentLR->_bf = 0;}else if (bf == 1){pParentL->_bf = -1;pParentLR->_bf = 0;pParent->_bf = 0;}else if (bf == -1){pParentL->_bf = 0;pParent->_bf = 1;pParentLR->_bf = 0;}return;}

旋转之后的情况:
在这里插入图片描述

  1. 右左双旋转
    初始情况:
    在这里插入图片描述
// 右左双旋void RotateRL(Node* pParent){Node* pParnetR = pParent->_right;Node* pParentRL = pParnetR->_left;int bf = pParentRL->_bf;RotateR(pParnetR);RotateL(pParent);if (bf == 0){pParent->_bf = 0;pParnetR->_bf = 0;pParentRL->_bf = 0;}else if (bf == -1){pParent->_bf = 0;pParnetR->_bf = 1;pParentRL->_bf = 0;}else if (bf == 1){pParent->_bf = -1;pParnetR->_bf = 0;pParentRL->_bf = 0;}return;}

旋转之后的情况:
在这里插入图片描述

4.AVL树的验证

  1. 验证为二叉搜索树
    中序遍历得到有序的序列就可以证明为二叉搜索树。
  2. 验证为平衡树
    看平衡因子
bool _IsBalance(Node* root, int& height){if (root == nullptr){height = 0;return true;}int leftHeight = 0, rightHeight = 0;if (!_IsBalance(root->_left, leftHeight) || !_IsBalance(root->_right, rightHeight)){return false;}if (abs(rightHeight - leftHeight) >= 2){cout <<root->_kv.first<<"不平衡" << endl;return false;}if (rightHeight - leftHeight != root->_bf){cout << root->_kv.first <<"平衡因子异常" << endl;return false;}height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;return true;}

在这里插入图片描述

相关文章:

AVL树讲解

AVL树 1. 概念2. AVL节点的定义3. AVL树插入3.1 旋转 4.AVL树的验证 1. 概念 AVL树是一种自平衡二叉搜索树。它的每个节点的左子树和右子树的高度差&#xff08;平衡因子&#xff0c;我们这里按右子树高度减左子树高度&#xff09;的绝对值不超过1。AVL的左子树和右子树都是AV…...

20240308-1-校招前端面试常见问题CSS

校招前端面试常见问题【3】——CSS 1、盒模型 Q&#xff1a;请简述一下 CSS 盒模型&#xff1f; W3C 模式&#xff1a;盒子宽widthpaddingbordermargin 怪异模式&#xff1a;盒子宽widthmargin Q&#xff1a;inline、block、inline-block 元素的区别&#xff1f; inline&am…...

linux系统简述docker

简述docker docker理念docker三要素docker平台架构docker运行的基本流程 docker理念 一次镜像&#xff0c;处处运行 基于go语言实现的项目 解决了运行环境和配置问题的软件容器&#xff0c;方便做持续集成并有助于整体发布的容器虚拟化技术 能够使硬件、操作系统和应用程序三者…...

【论文阅读】Mamba:选择状态空间模型的线性时间序列建模(一)

文章目录 Mamba:选择状态空间模型的线性时间序列建模介绍状态序列模型选择性状态空间模型动机&#xff1a;选择作为一种压缩手段用选择性提升SSM 选择性SSM的高效实现先前模型的动机选择扫描总览&#xff1a;硬件感知状态扩展 Mamba论文 Mamba:选择状态空间模型的线性时间序列建…...

漏洞复现-蓝凌LandrayOA系列

蓝凌OA系列 &#x1f52a; 是否利用过 优先级从高到低 发现日期从近到远 公司团队名_产品名_大版本号_特定小版本号_接口文件名_漏洞类型发现日期.载荷格式LandrayOA_Custom_SSRF_JNDI漏洞 LandrayOA_sysSearchMain_Rce漏洞 LandrayOA_Custom_FileRead漏洞...

计算机网络 路由算法

路由选择协议的核心是路由算法&#xff0c;即需要何种算法来获得路由表中的各个项目。 路由算法的目的很明显&#xff0c;给定一组路由器以及连接路由器的链路&#xff0c;路由算法需要找到一条从源路由器到目的路由器的最佳路径&#xff0c;通常&#xff0c;最佳路径是由最低…...

【C++ 学习】构造函数详解!!!

1. 类的6个默认成员函数的引入 ① 如果一个类中什么成员都没有&#xff0c;简称为空类。 ② 空类中真的什么都没有吗&#xff1f;并不是&#xff0c;任何类在什么都不写时&#xff0c;编译器会自动生成以下6个默认成员函数。 ③ 默认成员函数&#xff1a;用户没有显式实现&…...

【LeetCode】72. 编辑距离(中等)——代码随想录算法训练营Day55

题目链接&#xff1a;72. 编辑距离 题目描述 给你两个单词 word1 和 word2&#xff0c; 请返回将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作&#xff1a; 插入一个字符删除一个字符替换一个字符 示例 1&#xff1a; 输入&#xff1a;w…...

关于手机是否支持h264的问题的解决方案

目录 现象 原理 修改内容 现象 开始以为是手机不支持h264的编码 。机器人chatgpt一通乱扯。 后来检查了下手机&#xff0c;明显是有h264嘛。 终于搞定&#xff0c;不枉凌晨三点起来思考 原理 WebRTC 默认使用的视频编码器是VP8和VP9&#xff0c;WebRTC内置了这两种编码器…...

借助Aspose.html控件,在 Java 中将 URL 转换为 PDF

如果您正在寻找一种将实时 URL 中的网页另存为 PDF文档的方法&#xff0c;那么您来对地方了。在这篇博文中&#xff0c;我们将学习如何使用 Java 将 URL 转换为 PDF。从实时 URL转换HTML网页可以像任何其他文档一样保存所需的网页以供离线访问。将网页保存为 PDF 格式可以轻松突…...

数据结构——堆的应用 堆排序详解

&#x1f49e;&#x1f49e; 前言 hello hello~ &#xff0c;这里是大耳朵土土垚~&#x1f496;&#x1f496; &#xff0c;欢迎大家点赞&#x1f973;&#x1f973;关注&#x1f4a5;&#x1f4a5;收藏&#x1f339;&#x1f339;&#x1f339; &#x1f4a5;个人主页&#x…...

Sftp服务器搭建(linux)

Sftp服务器搭建&#xff08;linux&#xff09; 一、基本工作原理 FTP的基本工作原理如下&#xff1a; 1&#xff09;建立连接&#xff1a;客户端与服务器之间通过TCP/IP建立连接。默认情况下&#xff0c;FTP使用端口号21作为控制连接的端口。​​​​​​​ 2&#xff09;身…...

Neo4j 新手教程 环境安装 基础增删改查 python链接 常用操作 纯新手向

Neo4j安装教程&#x1f680; 目前在学习知识图谱的相关内容&#xff0c;在图数据库中最有名的就是Neo4j,为了降低入门难度&#xff0c;不被网上很多华丽呼哨的Cypher命令吓退&#xff0c;故分享出该文档&#xff0c;为自己手动总结&#xff0c;包括安装环境&#xff0c;增删改查…...

PyTorch2.0 环境搭建详细步骤(Nvidia显卡)

Step 1 、查看显卡驱动版本 Step2、下载CUDA 11.7 或者11.8&#xff08;我自己用的这个&#xff09;也行,稍后我会贴出来版本匹配对应表 https://developer.nvidia.com/cuda-toolkit-archive Step3、下载CUDNN cuDNN 9.0.0 Downloads | NVIDIA Developer Step4、安装anconda&…...

Python逆向:pyc字节码转py文件

一、 工具准备 反编译工具&#xff1a;pycdc.exe 十六进制编辑器&#xff1a;010editor 二、字节码文件转换 在CTF中&#xff0c;有时候会得到一串十六进制文件&#xff0c;通过010editor使用查看后&#xff0c;怀疑可能是python的字节码文件。 三、逆向反编译 将010editor得到…...

提示词工程技术:类比、后退、动态少样本、自动生成CoT

类比提示 “类比提示”利用类比推理的概念&#xff0c;鼓励模型生成自己的例子和知识&#xff0c;从而实现更灵活和高效的解决问题。 后退提示 “后退提示”专注于抽象&#xff0c;引导模型推导出高级概念和原理&#xff0c;进而提高其推理能力。 使用一个基本的数学问题来…...

【深度学习笔记】6_5 RNN的pytorch实现

注&#xff1a;本文为《动手学深度学习》开源内容&#xff0c;部分标注了个人理解&#xff0c;仅为个人学习记录&#xff0c;无抄袭搬运意图 6.5 循环神经网络的简洁实现 本节将使用PyTorch来更简洁地实现基于循环神经网络的语言模型。首先&#xff0c;我们读取周杰伦专辑歌词…...

Linux at任务调度命令行编辑错误

错误&#xff1a; 在at任务调度命令行语句编辑错误时&#xff0c;按backspace进行删除无法进行。 解决方案&#xff1a; 请按Ctrlbackspace进行删除&#xff0c;即可解决。...

lua与C++粘合层框架

lua调用C++ 在lua中是以函数指针的形式调用函数, 并且所有的函数指针都必须满足如下此种类型: typedef int (*lua_CFunction) (lua_State *L);   也就是说, 偶们在C++中定义函数时必须以lua_State为参数, 以int为返回值才能被Lua所调用. 但是不要忘记了, 偶们的lua_State是支…...

POST 请求,Ajax 与 cookie

POST 请求则需要设置RequestHeader告诉后台传递内容的编码方式以及在 send 方法里传入对应的值 xhr.open("POST", url, true); xhr.setRequestHeader(("Content-Type": "application/x-www-form-urlencoded")); xhr.send("key1value1&…...

第四章 ROBOGUIDE核心操作与仿真实战

1. ROBOGUIDE入门&#xff1a;从零开始搭建仿真环境 第一次打开ROBOGUIDE时&#xff0c;满屏的英文界面和复杂工具栏确实容易让人发懵。记得我刚开始接触时&#xff0c;光是找"新建项目"按钮就花了十分钟。其实只要掌握几个关键区域&#xff0c;就能快速上手这个强大…...

OpCore Simplify黑苹果教程:10分钟搞定OpenCore EFI配置的终极方案

OpCore Simplify黑苹果教程&#xff1a;10分钟搞定OpenCore EFI配置的终极方案 【免费下载链接】OpCore-Simplify A tool designed to simplify the creation of OpenCore EFI 项目地址: https://gitcode.com/GitHub_Trending/op/OpCore-Simplify 还在为复杂的黑苹果配置…...

Gitleaks介绍(开源的Git仓库敏感信息扫描工具,用于检测代码中是否包含潜在secrets)密钥扫描、敏感信息扫描、自定义规则Regex、SARIF、质量门禁、Trivy、SAST

文章目录使用 Gitleaks 防止代码仓库泄露敏感信息一、什么是 Gitleaks&#xff1f;二、为什么需要 Gitleaks&#xff1f;1. Git 是“永久记录”2. 自动化开发带来的风险3. 安全合规要求三、Gitleaks 的核心能力1. 基于规则的检测&#xff08;Rule-based Detection&#xff09;2…...

HC32F460 SPI驱动ILI9341踩坑实录:从寄存器配置到屏幕闪烁的解决方案

HC32F460驱动ILI9341实战避坑指南&#xff1a;从SPI配置到显示优化的全流程解析 第一次点亮ILI9341屏幕时&#xff0c;那种期待与忐忑交织的感觉至今难忘——接好线、写完代码、上电测试&#xff0c;结果要么白屏要么花屏&#xff0c;甚至直接毫无反应。这种经历对于嵌入式开发…...

SSD-PyTorch训练自定义数据集避坑指南:从VOC格式准备到模型调参全流程

SSD-PyTorch实战&#xff1a;自定义数据集训练避坑与性能优化全解析 第一次用SSD训练自己的目标检测模型时&#xff0c;我盯着报错信息发呆了半小时——明明按照教程操作&#xff0c;却在数据加载环节卡住。后来才发现是PyTorch版本差异导致的API变更。这种"看似简单实则暗…...

从:smile:到:shipit::GitHub、Slack、Notion中那些程序员才懂的Emoji“黑话”与使用礼仪

从&#x1f60a;到&#x1f680;&#xff1a;解码开发者社群的Emoji密码与协作艺术 在GitHub的Pull Request评论区&#xff0c;一个简单的&#x1f680;符号可能让开发者会心一笑&#xff1b;Slack频道里突然出现的:shipit:表情往往预示着一次重要更新的发布。这些看似随意的图…...

Java的java.util.HexFormat双向支持

Java 16引入的java.util.HexFormat类为开发者提供了高效的十六进制与二进制数据双向转换能力&#xff0c;填补了Java标准库在十六进制处理领域的空白。这个工具类不仅支持基础格式转换&#xff0c;还能处理字节数组、字符序列等复杂场景&#xff0c;其线程安全特性更使其成为网…...

Windows Server上配置OpenSSH密钥登录的完整流程(含权限踩坑实录)

Windows Server上配置OpenSSH密钥登录的完整流程&#xff08;含权限踩坑实录&#xff09; 在Windows Server环境中配置安全的远程访问方案&#xff0c;OpenSSH已成为越来越多运维团队的首选。不同于Linux系统原生支持SSH协议&#xff0c;Windows平台上的OpenSSH实现有其独特的配…...

终极指南:如何使用dnSpy进行.NET程序集调试与BAML反编译

终极指南&#xff1a;如何使用dnSpy进行.NET程序集调试与BAML反编译 【免费下载链接】dnSpy Unofficial revival of the well known .NET debugger and assembly editor, dnSpy 项目地址: https://gitcode.com/gh_mirrors/dns/dnSpy dnSpyEx是一款功能强大的.NET调试器和…...

PCA降维实战:从数学推导到数据去量纲的完整指南

1. PCA降维的核心思想 主成分分析&#xff08;PCA&#xff09;就像给数据做"瘦身运动"。想象你有一堆杂乱无章的文档&#xff0c;PCA能帮你找出最重要的几页&#xff0c;用这几页就能说清楚整个文档80%的内容。我在处理电商用户行为数据时&#xff0c;原本有50多个特…...