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

C++ - AVL树实现(下篇)- 调试小技巧

前言

本博客是 AVL树的下篇,上篇请看:C++ - AVL 树 介绍 和 实现 (上篇)_chihiro1122的博客-CSDN博客 

 上篇当中写插入操作,和其中涉及的 旋转等等细节,还有AVL树的大体框架。

 调试小技巧

 条件断点

 在大项目当中,如果发生了程序的错误,崩溃的异常情况,那么因为项目过大,很多时候我们不能一步步去调试,这样非常的麻烦而且不现实。

在VS studio 当中,除了支持逐语句调试之外,还支持 条件调试,就是在某一个断点处,写上一句条件判别式,也就是表达式,可以设置当中这个 表达式为 false 或者 true 的时候,在此处语句停下来:

当我们右键做左边一列的(断点列),就会出现下图当中的 内容:

此时我们可以选择插入条件断点:

此时就会出现上述内容,上述内容就是 条件断点当中的条件设置,你可以在 最右边(在示例:x== 5 ) 这个位置处,写上你需要的条件表达式,然后还可以设置这个表达式为 true 或者为 false的时候停止执行。注意:是程序执行到 该断点处,才会进行判断表达式真假,才会进行停止或者继续执行的操作。

当然,此处不仅可以加条件表达式判断,还可以加一些 其他 判断方式:

 可以自己下去研究。

其实还有一个方法和上述方法类似,我们可以在我们想要打断的地方,自己写一个 if()判断语句,然后在其中随便写上一段代码,打上断点,也可以实现和上述一眼的操作;注意:一定要在if()当中写上一行代码,空行是不能打断点的,会直接跳过:

 如上所示,当 e 遍历的到 数组的 15 的时候,到达 if()就会停止。

这样,按下 f5 就会 执行到 e 遍历到 数组 15 这个元素之后停止,就不用再 手动调试到 15 这个元素位置了。

 如果 这颗数非常大的话,那么上述方式还是非常好用的,加入在 15之前有 200 个需要插入的元素,手动一步步调试到 15 肯定是不现实的。

调用堆栈

 可以在调试->窗口当中找到 调用堆栈这个窗口,当我们逐语句查看代码执行过程的时候,其中可能会调用多个函数,而每一个函数都有对应的函数栈帧,如果单独使用 f10  f11 来走的话,不好回溯;这时候我们可以在 调用堆栈这个窗口当中看到 从开始到现在,所调用函数的函数堆栈:

 此时我们只需要点击一下其中某一个函数堆栈,就可以直接回溯到 这个函数当中进行执行。

 写一些小程序来帮助我们判别一些规律性问题

 比如在自己实现 AVL 树当中,我们不太可能一步就直接写到位,出错是大概率的事情,而且像AVL树这种规则复杂的数据结构,在调试起非常的麻烦,此时我们为了更好的调试,写一个小程序来帮助我们判断,每插入一个结点之后,这颗树还是不是一颗 AVL树。

AVL树

 判断一颗AVL树是不是 平衡的
 

private:int Height(Node* root){if (root == nullptr)return 0;int HeightLeft = Height(root->_left);int HeightRight = Height(root->_right);return HeightLeft > HeightRight ? HeightLeft + 1 : HeightRight + 1;}// 判断是否是 平衡的bool isBalance(Node* root){if (root == nullptr)return;// 记录左右子树的高度int HeightLeft = Height(root->_left);int HeightRight = Height(root->_right);// 判断计算出来的 平衡因子是否和 该结点当中存储的是一样的if ((HeightLeft - HeightRight) != root->_bf){cout << "平衡因子出错: " << root->_kv.first << "->" << root->_bf << endl;}// 递归判断左右子树当中的结点return abs(HeightLeft - HeightRight) < 2 && isBalance(root->_left)&& isBalance(root->_right);}

在外部函数当中调用不了 其中的成员,也就是调用不了 根结点指针,所以我们还是写一个接口:
 

public:int Height(){return Height(_root);}bool isBalance(){return isBalance(_root);}

删除结点

 AVL树的删除操作比 插入还要困难一些,但是大体上也是三个步骤:

  • 按照搜索树的规则查找结点删除
  • 更新平衡因子
  • 判断平衡因子是否符合规则,不符合就要旋转

 如下述例子:
 

 假设现在要删除结点 3 ,在删除之前  2 的平衡因子是 0 ,3 是 2 的右孩子,当删除3 之后, 2 的平衡因子要 --。2 的平衡因子从 0 减到 -1 ,那么 2 的平衡因子 更新到 -1 ,在插入当中是需要网上更新父亲的平衡因子的,但是在上述例子的删除当中就不需要望山更新,因为 4 的左子树高度 在删除 3 之后,没有变化。

 而相反,如果在删除之后,删除结点的父亲的平衡因子 更新到 0 ,在插入当中是不需要网上更新的,但是在插入当中,如果一个结点的平衡因子 更新到0 ,说明该结点的某一个子树肯定发生了高度变化,比如删除上述例子的 14 这个结点,那么 7 结点的平衡因子 就会从 -1 更新到 0。此时就需要往上沿着父亲更新结点。在往上更新过程当中,只要是更新为0 了,都要继续网上更新。

而如果对结点的平衡因子进行更新,和插入当中类似,判断是从 父亲结点左右孩子的那一边更新上来的,从那边上来,就代表有那边的 高度发生了变化,对应的进行修改就好了。

其实上述在查找删除,更新平衡因子都还好,主要是在判断是否需要旋转的条件才是麻烦的。

不能再像 插入当中判断 是否需要旋转一样 ,沿着更新父亲结点的平衡因子路径上,判断更新之后父亲结点的平衡因子是否合法。

因为在删除结点之后,不是在删除路径的一边子树当中去判断旋转,因为此时多出来的高度的子树来,某一个平衡因子不合法的结点的另一边子树当中。找到平衡因子不合法的结点还不够,还需要找到使得这个结点为根结点的子树不平衡的子树。当然,这种情况是双旋的情况,如果是单旋就还好,不过双旋的问题可能是要解决的。

 关于删除细节在 《算法导论》或《数据结构-用面向对象方法与C++描述》殷人昆版。这两本书当中就有详细的介绍。

 AVL树的性能

AVL树是一棵绝对平衡的二叉搜索树,其要求每个节点的左右子树高度差的绝对值都不超过1,这
样可以保证查询时高效的时间复杂度,即O(log N)。

但是如果要对AVL树做一些结构修改的操作,非常麻烦,比如:插入时要维护其绝对平衡,旋转的次数比较多,更差的是在删除时,有可能一直要让旋转持续到根的位置。

但是,AVL树本来就为了方便我们快速查找数据的,当插入好了之后,AVL树构建好了,我们在查找数据的时候会非诚的方便。

所以,AVL树一般用于静态的存储数据,比如你在一开始就把数据以AVL树的结果构建好,那么之后尽量少更改数据,建议不更改其中的数据,那么AVL树在只是查找数据方便还是非常方便的。

而且,AVL虽然在旋转上看似很复杂,其实性能上没有太大消耗,在旋转当中,没有旋转,只是单纯的修改链接指针和 修改平衡因子,这些都是常数级别的 时间复杂度。

所以,AVL树只是看似复杂,但是实际在使用过程当中的效率还是挺高的,比如下述程序:
 

void text2()
{AVLTree<int, int> AVLT;vector<int> v;int N = 10000;v.reserve(10000);srand(time(0));// 开始计时int start = clock();for (int i = 0; i < N; i++){v.push_back(rand());}for (const auto& e : v){AVLT.insert(make_pair(e, e));//cout << "insert():" << e << "->" << AVLT.isBalance() << endl;}cout << AVLT.isBalance() << endl;int end = clock();cout << "用时: " << (double)(end - start)/ CLOCKS_PER_SEC << "s" << endl;
}

如上述程序,使用clock ()函数来计算整个程序的执行时间。

我们随机插入了 10000 个数据,而且还是用了 isBalance()这个效率不太好的递归函数去判断这个 树是不是 AVL树,输出:
 

1
用时: 0.006s

可以看到,耗时 0.006 s。

相关文章:

C++ - AVL树实现(下篇)- 调试小技巧

前言 本博客是 AVL树的下篇&#xff0c;上篇请看&#xff1a;C - AVL 树 介绍 和 实现 &#xff08;上篇&#xff09;_chihiro1122的博客-CSDN博客 上篇当中写插入操作&#xff0c;和其中涉及的 旋转等等细节&#xff0c;还有AVL树的大体框架。 调试小技巧 条件断点 在大项目…...

Mybatis懒加载

懒加载是什么&#xff1f; 按需加载所需内容&#xff0c;当调用到关联的数据时才与数据库交互否则不交互&#xff0c;能大大提高数据库性能&#xff0c;并不是所有场景下使用懒加载都能提高效率。 Mybatis懒加载&#xff1a;resultMap里面的association、collection有延迟加载功…...

DSOX3012A是德科技keysight DSOX3012A示波器

181/2461/8938是德科技DSOX3012A(安捷伦)示波器 是德科技DSOX3012A(安捷伦)是InfiniiVision 3000 X系列中的双通道型号。这款可升级示波器采用突破性技术设计&#xff0c;提供卓越的性能和功能。其独特的5仪器合一设计为相同的预算提供了更大的范围。 是德科技DSOX3012A示波器…...

基于网络表示学习的 新闻推荐算法研究与系统实现

摘要 第1章绪论 新闻推荐通常是利用用户的阅读行为和习惯、阅读选择和爱好等信息,为 用户推荐新闻内容。新闻推荐能够减少用户在数量庞大数据信息中获取信息的 时间消耗,从而能够缓解“信息过载[7]”的难题。以文本为内容的新闻,和商品、 电影、短视频等推荐系统相比,新闻推…...

<Altium Designer> 将.DSN文件导入并转换成SchDoc文件

目录 01 使用向导方式导入.DSN 02 消除Unique Identifiers Errors 03 文章总结 大家好&#xff0c;这里是程序员杰克。一名平平无奇的嵌入式软件工程师。 本文主要是总结和分享将OrCAD Capture画的原理图文件(.DSN)导入到Altium Designer&#xff0c;转换成对应的原理图文件…...

视频定格合璧,批量剪辑轻松插入图片

大家好&#xff01;想要将视频与图片完美融合吗&#xff1f;现在&#xff0c;我们为您推出一款强大的批量剪辑工具&#xff0c;让您能够轻松在图片中插入视频&#xff0c;让您的创作更加精彩动人&#xff01; 首先&#xff0c;第一步我们要进入媒体梦工厂主页面&#xff0c;并…...

【Tensorflow 2.12 电影推荐项目搭建】

Tensorflow 2.12 电影推荐项目搭建 学习笔记工具、环境创建项目项目配置安装相关python包召回模型实现排序模型实现实现电影推荐导入模块设置要推荐的用户召回推荐排序推荐推荐结果结尾学习笔记 Tensorflow 2.12 电影推荐项目搭建记录~ Tensorflow是谷歌开源的机器学习框架,可…...

python+opencv特征匹配算法

pythonopencv特征匹配算法 1.安装 pip install opencv-python pip install numpy2.算法明细 import cv2 import numpy as np# 读取两张图像 img1 cv2.imread(image1.jpg,0) # queryImage img2 cv2.imread(image2.jpg,0) # trainImage# 初始化SIFT对象 sift cv2.xfeatur…...

android Compose 实现 webView

在Compose中&#xff0c;目前还没有原生的WebView组件。但是&#xff0c;您可以使用Android Jetpack组件中的AndroidView来将传统的WebView集成到Compose中。下面是一个示例代码&#xff1a; Composable fun WebViewScreen(url: String) {AndroidView(factory { context ->…...

算法基础-数学知识-欧拉函数、快速幂、扩展欧几里德、中国剩余定理

算法基础-数学知识-欧拉函数、快速幂、扩展欧几里德、中国剩余定理 欧拉函数AcWing 874. 筛法求欧拉函数 快速幂AcWing 875. 快速幂AcWing 876. 快速幂求逆元 扩展欧几里德&#xff08;裴蜀定理&#xff09;AcWing 877. 扩展欧几里得算法AcWing 878. 线性同余方程 中国剩余定理…...

ElasticSearch系列-索引原理与数据读写流程详解

索引原理 倒排索引 倒排索引&#xff08;Inverted Index&#xff09;也叫反向索引&#xff0c;有反向索引必有正向索引。通俗地来讲&#xff0c;正向索引是通过key找value&#xff0c;反向索引则是通过value找key。ES底层在检索时底层使用的就是倒排索引。 索引模型 现有索…...

【码银送书第七期】七本考研书籍

八九月的朋友圈刮起了一股晒通知书潮&#xff0c;频频有大佬晒出“研究生入学通知书”&#xff0c;看着让人既羡慕又焦虑。果然应了那句老话——比你优秀的人&#xff0c;还比你努力。 心里痒痒&#xff0c;想考研的技术人儿~别再犹豫了。小编咨询了一大波上岸的大佬&#xff…...

docker容器的设置本地时间(/etc/localtime)和本地时区(/etc/timezone)

本地时区的修改 一般情况下&#xff0c;我们启动docker容器时指定了环境变量&#xff1a; -e TZ:Asia/Ho_Chi_Minh &#xff0c;容器内的时区就会变成东八区&#xff0c;某些软件则会读取该环境变量作为其使用的时区&#xff0c;该环境变量相当于"残缺版"的命令&…...

侯捷老师C++课程:内存管理

内存管理 第一讲&#xff1a;primitives c应用程序 c内存的基本工具 测试程序&#xff1a; #include <iostream> using namespace std; #include <complex> #include <ext/pool_allocator.h>int main() {// 三种使用方法void* p1 malloc(512); // 512 b…...

A股风格因子看板 (2023.09 第05期)

该因子看板跟踪A股风格因子&#xff0c;该因子主要解释沪深两市的市场收益、刻画市场风格趋势的系列风格因子&#xff0c;用以分析市场风格切换、组合风格暴露等。 今日为该因子跟踪第05期&#xff0c;指数组合数据截止日2023-08-31&#xff0c;要点如下 近1年A股风格因子检验统…...

修炼离线:(二)sqoop插入hbase 脚本(增量)

一&#xff1a;mysql创建表&#xff0c;插入数据。 二&#xff1a;hbase创建表。 habse shell create aa(表名),cf(列族)三&#xff1a;mysql_hbase脚本。 #!/bin/shmysqlHost$1 mysqlUserName$2 mysqlUserPass$3 mysqlDbName$4 myqlTbName$5 hbaseTbName$6 hbaseTbRowkey$7…...

跨平台编程开发工具Xojo 2023 Release mac中文版功能介绍

Xojo mac是一款跨平台的软件开发工具&#xff0c;它允许开发人员使用一种编程语言来创建应用程序&#xff0c;然后可以在多个操作系统上运行。Xojo 2023是Xojo开发工具的最新版本&#xff0c;它提供了许多功能和改进&#xff0c;以帮助开发人员更轻松地构建高质量的应用程序。 …...

OpenCV Series : Target Box Outline Border

角点 P1 [0] (255, 000, 000) P2 [1] (000, 255, 000) P3 [2] (000, 000, 255) P4 [3] (000, 000, 000)垂直矩形框 rect cv2.minAreaRect(cnt)targetColor roi_colortargetThickness 1targetColor (255, 255, 255)if lineVerbose:if …...

【AD】【规则设置】设置四层板

设置四层板 一般 4层板&#xff0c;都会把 地 和 VCC放在内层。1、使用快捷键D-K 进入层叠管理器&#xff0c;添加负片层添加完后&#xff0c;修改层名&#xff0c;方便辨识修改格式&#xff1a;属性层号 2、进入相应layer 设置网络设置GND层设置VCC层特点&#xff1a;在层内可…...

Linux安装JDK1.8并配置环境变量

Linux安装JDK并配置环境变量Linux安装JDK并配置环境变量Linux安装JDK并配置环境变量 一、查询已有JAVA环境版本信息 java -version 二、下载Oracle JDK安装包 https://www.oracle.com/java/technologies/downloads/archive/ 三、安装 配置JDK 以下方式适用于安装各版本JDK&…...

面向面试知识--MySQL数据库与索引

面向面试知识–MySQL数据库与索引 优化难点与面试点 什么是MySQL索引&#xff1f; 索引的MySQL官方定义&#xff1a;索引是帮助MySQL快速获取数据的数据结构。 动力节点原文&#xff1a; MysQL官方对于索引的定义:索引是帮助MySQL高效获取数据的数据结构。 MysQL在存储数据之…...

portainer + portainer/agent

参考链接 https://docs.portainer.io/ portainer 免费版 portainer-ce 免费版 portainer-ee 企业版 portainer-agent docker本机代理 agent 下载地址 https://download.csdn.net/download/a309450028a/87451332 portainer 下载地址 https://download.csdn…...

C# 截取字符串

在 C# 中&#xff0c;可以使用 Substring 方法来截取字符串的一部分。该方法有两个参数&#xff1a;起始索引和要截取的字符数。 以下是使用 Substring 方法截取字符串的示例&#xff1a; string str "Hello World"; string result str.Substring(6); // 从索引为…...

FOXBORO FBM233 P0926GX控制脉冲模块

FOXBORO FBM233 P0926GX 是一种控制脉冲模块&#xff0c;通常用于工业自动化和控制系统中。这个模块的主要功能是生成和控制脉冲信号&#xff0c;以用于执行特定的操作或控制过程。以下是可能适用于 FOXBORO FBM233 P0926GX 控制脉冲模块的一些常见特点&#xff1a; 脉冲生成&a…...

MySQL性能优化——MYSQL执行流程

MySQL 执行流程1-5如下图。 MySQL 的架构共分为两层&#xff1a;Server 层和存储引擎层&#xff0c; Server 层负责建立连接、分析和执行 SQL。MySQL 大多数的核心功能模块都在这实现&#xff0c;主要包括连接器&#xff0c;查询缓存、解析器、预处理器、优化器、执行器等。…...

Django:四、Djiango如何连接使用MySQL数据库

一、安装数据库第三方插件 安装下载mysql第三方插件 pip install mysqlclient 二、创建MySQL数据库 ORM可以帮助我们做两件事&#xff1a; 创建、修改、删除数据库中的表&#xff08;不用写SQL语句&#xff09;&#xff0c;但无法创建数据库操作表中的数据&#xff08;不用…...

LeetCode 热题 100(八):贪心。121. 买卖股票的最佳时机、45. 跳跃游戏 II

题目一&#xff1a; 121. 买卖股票的最佳时机https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/ 思路&#xff1a;因为时间复杂度O&#xff08;n&#xff09;&#xff0c;所以使用贪心来做。类似双指针&#xff0c;一个指针记录到当前循环时最小的股票价格&…...

第N个数字

给你一个整数 n &#xff0c;请你在无限的整数序列 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, …] 中找出并返回第 n 位上的数字。 我觉得这题是哪以理解的 看这个题解 func findNthDigit(n int) int {digit : 1start : 1count : 9for n > count {n - countdigitstart start …...

【适用于电力系统和音频系统】计算信号的总谐波失真 (THD)(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

kubernetes(k8s)PVC

概念 PVC 的全称是&#xff1a;PersistentVolumeClaim&#xff08;持久化卷声明&#xff09;&#xff0c;PVC 是用户存储的一种声明&#xff0c;PVC 和 Pod 比较类似&#xff0c;Pod 消耗的是节点&#xff0c;PVC 消耗的是 PV 资源&#xff0c;Pod 可以请求 CPU 和内存&#x…...

中国公路建设招标网站/江苏网站seo

由于获取Calendar实例&#xff0c;是根据当前时间戳来获取的&#xff0c;故在获取特定的日期的开始时间时&#xff0c;毫秒数一般不为0&#xff0c;这时候可以手动设置为0。可以参见这位仁兄的代码&#xff1a; https://blog.csdn.net/nihaoa50/article/details/70768091...

万户网络网站管理系统/宁波网站推广公司价格

WordPress模板制作中&#xff0c;function.php是一个特殊的文件&#xff0c;可以用来自定义模板中需要用到的函数&#xff0c;添加钩子函数等。为了为不同的模板添加不同的钩子函数&#xff0c;需要使用WordPress的条件标签(Conditional Tag)。WordPress常用条件标签如下&#…...

wordpress+park主题/快速排名提升

Linux下载工具Wget常用参数 ◆-b&#xff1a;后台下载&#xff0c;Wget默认的是把文件下载到当前目录。 ◆-O&#xff1a;将文件下载到指定的目录中。 ◆-P&#xff1a;保存文件之前先创建指定名称的目录。 ◆-t&#xff1a;尝试连接次数&#xff0c;当Wget无法与服务器建立连接…...

淘宝网站是谁做的好/搜索引擎优化的各种方法

Pytorch框架学习记录9——非线性激活 1. ReLU函数介绍 torch.nn.ReLU(inplaceFalse) 参数 inplace- 可以选择就地执行操作。默认&#xff1a;False 形状&#xff1a; 输入&#xff1a;( * )&#xff0c; 在哪里**表示任意数量的维度。输出&#xff1a;( * )&#xff0c;与输入…...

石家庄做外贸的网站建设/网推是什么

最近项目中涉及很多文件上传的地方&#xff0c;然后文件上传又有很多限制。比如文件大小限制&#xff0c;文件个数限制&#xff0c;文件类型限制&#xff0c;文件上传后的列表样式自定义&#xff0c;包括上传进度条等问题。下面是我对element-ui的上传组件的一些改造&#xff0…...

iis 网站访问权限设置/nba最新消息交易

在说明位运算前&#xff0c;先说明下逻辑运算。逻辑运算符有以下几个&#xff1a; 逻辑运算符&#xff08;按运算符优先顺序排列&#xff09; 结合方向逻辑运算符名 称例 子 非结合!逻辑非! $A左&&逻辑与$A && $B左||逻辑或$A || $B左AND逻辑与$A and $B左XOR逻…...