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

【C++模拟实现】手撕AVL树

【C++模拟实现】手撕AVL树

目录

  • 【C++模拟实现】手撕AVL树
      • AVL树的介绍(百度百科)
      • AVL树insert函数的实现代码
      • 验证是否为AVL树
      • AVL树模拟实现的要点
        • 易忘点
        • AVL树的旋转思路

作者:爱写代码的刚子

时间:2023.9.10

前言:本篇博客将会介绍AVL树的模拟实现(模拟AVL树的插入),以及如何去验证是否为AVL树

AVL树的介绍(百度百科)

AVL树本质上还是一棵二叉搜索树,它的特点是:

  1. 本身首先是一棵二叉搜索树。

  2. 带有平衡条件:每个结点的左右子树的高度之差的绝对值(平衡因子)最多为1。

也就是说,AVL树,本质上是带了平衡功能的二叉查找树(二叉排序树,二叉搜索树)。

AVL树insert函数的实现代码

template<class K,class V>
class AVLTreeNode
{
public:AVLTreeNode(const pair<K,V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_bf(0){}AVLTreeNode* _left;AVLTreeNode* _right;AVLTreeNode* _parent;//需要设立父节点指针pair<K,V> _kv;int _bf;
};template<class K,class V>
class AVLTree
{typedef AVLTreeNode<K,V> Node;
public:AVLTree():_root(nullptr){}bool insert(const pair<K,V>& kv){if(_root==nullptr){_root=new Node(kv);return true;}else{Node* cur=_root;Node* parent=nullptr;//设计parent指针是必要的while(cur){if(cur->_kv.first>kv.first){parent=cur;cur=cur->_left;}else if(cur->_kv.first<kv.first){parent=cur;cur=cur->_right;}else{return false;}}cur=new Node(kv);//判断新加入的节点是父节点的左子树还是右子树if(parent->_kv.first>kv.first){parent->_left=cur;}else{parent->_right=cur;}cur->_parent=parent;while(parent){//及时调整父节点的平衡因子if(parent->_left==cur){--parent->_bf;}else{++parent->_bf;}if(parent->_bf==0)//当父节点的平衡因子为0时停止调整{break;}else if(parent->_bf==-1||parent->_bf==1){cur=parent;parent=parent->_parent;}else if(parent->_bf==2||parent->_bf==-2)//处理异常情况{//出现问题的情况if(parent->_bf==-2&&cur->_bf==-1){_RotateR(parent);//右单旋}else if(parent->_bf==2&&cur->_bf==1){_RotateL(parent);//左单旋}else if(parent->_bf==-2&&cur->_bf==1){   _RotateLR(parent);//左右双旋}else if(parent->_bf==2&&cur->_bf==-1){_RotateRL(parent);//右左双旋}else{assert(false);}break;}else{assert(false);}}}return true;} void _RotateR(Node* parent)//右单旋的实现{Node*cur=parent->_left;Node*curRight=cur->_right;Node*ppnode=parent->_parent;cur->_right=parent;parent->_left=curRight;if(curRight)//curRight可能是nullptr{curRight->_parent=parent;}parent->_parent=cur;//处理ppnodeif(parent==_root)//parent为头节点时需要单独处理{_root=cur;cur->_parent=nullptr;}else{if(ppnode->_left==parent){ppnode->_left=cur;}else{ppnode->_right=cur;}cur->_parent=ppnode;}parent->_bf=cur->_bf=0;}void _RotateL(Node* parent){Node* cur=parent->_right;Node* curLeft=cur->_left;Node* ppnode=parent->_parent;cur->_left=parent;parent->_right=curLeft;if(curLeft){curLeft->_parent=cur;}parent->_parent=cur;if(parent==_root){_root=cur;cur->_parent=nullptr;}else{if(ppnode->_left==parent){ppnode->_left=cur;}else{ppnode->_right=cur;}cur->_parent=ppnode;}parent->_bf=cur->_bf=0;}void _RotateLR(Node* parent){Node* cur=parent->_left;Node* curRight=cur->_right;int bf=curRight->_bf;_RotateL(cur);_RotateR(parent);//最好再处理一下平衡因子,减少耦合度if(bf==0)//单链情况下{parent->_bf=0;cur->_bf=0;curRight->_bf=0;}else if(bf==-1){parent->_bf=1;curRight->_bf=0;cur->_bf=0;}else if(bf==1){parent->_bf=-1;curRight->_bf=0;cur->_bf=0;}else{assert(false);}}void _RotateRL(Node* parent){Node* cur=parent->_right;Node* curLeft=cur->_left;int bf=curLeft->_bf;_RotateR(cur);_RotateL(parent);if(bf==0){parent->_bf=0;curLeft->_bf=0;cur->_bf=0;}else if(bf==1){parent->_bf=0;curLeft->_bf=-1;cur->_bf=0;}else if(bf==-1){parent->_bf=0;curLeft->_bf=1;cur->_bf=0;}else{assert(false);}}private:Node* _root;
};

验证是否为AVL树

int _Height(Node* root){if(root==nullptr){return 0;}int leftHeight=_Height(root->_left);int rightHeight=_Height(root->_right);return leftHeight>rightHeight?leftHeight+1:rightHeight+1;}bool _Isbalance(){return _Isbalance(_root);}bool _Isbalance(Node* root){if(root==nullptr){return true;}int right=_Height(root->_right);int left=_Height(root->_left);if(root->_bf!=right-left){cout<<"平衡因子异常"<<root->_bf<<" "<<right<<" "<<left<<endl;return false;}return abs(right-left)<2&&_Isbalance(root->_left)&&_Isbalance(root->_right);}
  • 根据AVL树的特性引入两个成员函数_Height函数用于计算二叉树的高度

  • 以下为验证结果:
    在这里插入图片描述

AVL树模拟实现的要点

易忘点

一定要时刻注意_parent指针的修改!尤其旋转函数中需要判断旋转后的二叉树的根节点是否还有父亲节点,如果有,需要在旋转前先保存,之后再链接上。

AVL树的旋转思路

  1. 新增在左,parent平衡因子减减
  2. 新增在右,parent平衡因子加加
  3. 更新后parent平衡因子 == 0,说明parent所在的子树的高度不变,不会再影响祖先,不用再继续沿着到eot的路径往上更新
  4. 更新后parent平衡因子 == 1 0r -1,说明parent所在的子树的高度变化,会再影响祖先,需要继续沿着到root的路径往上更新更新后
  5. 更新后parent平衡因子 == 2 or -2,说明parent所在的子树的高度变化且不平衡,对parent所在子树进行旋转,让他平衡
  6. 更到根节点,插入结束

由于AVL树画图较为麻烦,作者先不画了,可以看看其他大佬的博客,一些需要注意的地方已经写在代码注释里了,AVL树的删除之后有机会可以模拟实现一下。
AVL树的调试较为麻烦,模拟实现可以提高自己的调试能力。

相关文章:

【C++模拟实现】手撕AVL树

【C模拟实现】手撕AVL树 目录 【C模拟实现】手撕AVL树AVL树的介绍&#xff08;百度百科&#xff09;AVL树insert函数的实现代码验证是否为AVL树AVL树模拟实现的要点易忘点AVL树的旋转思路 作者&#xff1a;爱写代码的刚子 时间&#xff1a;2023.9.10 前言&#xff1a;本篇博客将…...

如何重置 docker中的mariadb的root

停止 Mariadb 容器&#xff1a;运行以下命令停止正在运行的 Mariadb 容器&#xff1a; docker stop <container_name>将 <container_name> 替换为你的 Mariadb 容器的名称或容器ID。 删除 Mariadb 容器&#xff1a;运行以下命令删除已停止的 Mariadb 容器&#x…...

设计模式系列-原型模式

一、上篇回顾 上篇创建者模式中&#xff0c;我们主要讲述了创建者的几类实现方案&#xff0c;和创建者模式的应用的场景和特点&#xff0c;创建者模式适合创建复杂的对象&#xff0c;并且这些对象的每 个组成部分的详细创建步骤可以是动态的变化的&#xff0c;但是每个对象的组…...

家用电脑可以用做服务器吗

家用电脑的结构与服务器的结构是相同的&#xff0c;家用电脑是可以用来搭建服务器使用。但使用家用电脑做服务器在稳定性会比服务器差很多 1.家用电脑没有公网IP&#xff0c;网络运营商分配的IP重启路由之后是会变化&#xff0c;不固定。服务器运行是需要有固定IP让人连接访问。…...

CRM软件管理系统的基本功能

CRM管理系统是企业运营的重要工具&#xff0c;它可以帮助企业管理客户关系&#xff0c;提升销售效率&#xff0c;大幅提高客户转化率&#xff0c;实现业绩增长。那么&#xff0c;CRM管理系统一般包含哪些功能呢&#xff1f;下面我们就来说说。 1、销售自动化 销售自动化顾名思…...

手机喊话应用实现思路

手机要是动一下&#xff0c;就喊话“摇摇零线&#xff0c;摇摇零线”&#xff0c;是不是比较酷&#xff0c; 这里实现一下手机翻转一下&#xff0c;播放声音的效果&#xff0c; 通过sensor识别到手机的运动状况&#xff0c;然后播放音频&#xff0c; public class MainActivi…...

【ARM CoreLink 系列 3 -- CCI-550 控制器介绍 】

文章目录 CCI FamilyCCI-550 简介CCI-550 功能CCI-550 Interfaces Snoop filter 使用背景CCI-550 Snoop filter 上篇文章&#xff1a;ARM CoreLink 系列 2 – CCI-400 控制器简介 CCI Family CCI-550 简介 Arm CoreLink CCI-550 Cache Coherent Interconnect 扩展了 CoreLink…...

最长递增子序列 -- 动规

300. 最长递增子序列 注意「⼦序列」和「⼦串」的区别&#xff0c;⼦串⼀定是连续的&#xff0c;⽽⼦序列不⼀定是连续的。 class LengthOfLIS:"""300. 最长递增子序列https://leetcode.cn/problems/longest-increasing-subsequence/description/""&q…...

linux 进程管理命令

进程管理命令 查看进程命令 ps命令 显示系统上运行的进程列表 # 查看系统中所有正在运行的系统ps aux# 获取占用内存资源最多的10个进程&#xff0c;可以使用如下命令组合&#xff1a;ps aux|head -1;ps aux|grep -v PID|sort -rn -k 4|head# 获取占用CPU资源最多的10个进程&am…...

第一章:计算机网络和因特网

什么是因特网 具体构成描述 互联网是一个世界范围的计算机网络&#xff0c;即一个互联了遍及世界数十亿计算机设备的网络&#xff0c;这些被连接的设备被称为主机或者端系统。端系统通过通信链路&#xff08;communication link&#xff09;和分组交换机&#xff08;packet s…...

Android后退堆栈

修改代码 现在的ItemClick使得用户单击其中一个项目时就会跳转&#xff0c;现在要修改其使得在一个小屏幕设备上才会这样做&#xff0c;在一个大屏幕设备上运行用户选择一个训练项目时在右边的片段显示响应的信息。 希望片段处理后退的方式&#xff1a;假设用户在手机上运行这…...

网络原理(一)网络基础,包括IP ,网络相关的定义

网络基础&#xff0c;包括IP &#xff0c;网络相关的定义 网络基础冲突域广播域DNSNATNAPT 网络基础 以下图片是书上的网图。 什么是IP地址&#xff1f; IP地址&#xff08;Internet Protocol Address&#xff09;是指互联网协议地址&#xff0c;又译为网际协议地址。P地址是…...

Python语义分割与街景识别(2):环境搭建

前言 本文主要用于记录我在使用python做图像识别语义分割训练集的过程&#xff0c;由于在这一过程中踩坑排除BUG过多&#xff0c;因此也希望想做这部分内容的同学们可以少走些弯路。 本文是python语义分割与街景识别的第二篇&#xff0c;关于环境搭建的内容。这个部分是整个流…...

stm32(GD32,apm32),开优化后需要特别注意的地方

提到优化就不得不提及 volatile 使用场景 1&#xff1a;中断服务程序中修改的供其它程序检测的变量&#xff0c;需要加volatile&#xff1b; : 2&#xff1a;多任务环境下各任务间共享的标志&#xff0c;应该加volatile&#xff1b; 3&#xff1a;并行设备的硬件寄存器&#x…...

LLVM 与代码混淆技术

项目源码 什么是 LLVM LLVM 计划启动于2000年&#xff0c;开始由美国 UIUC 大学的 Chris Lattner 博士主持开展&#xff0c;后来 Apple 也加入其中。最初的目的是开发一套提供中间代码和编译基础设施的虚拟系统。 LLVM 命名最早源自于底层虚拟机&#xff08;Low Level Virtu…...

R语言---使用runway进行机器学习模型性能的比较

R语言—使用runway进行机器学习模型性能的比较 #dataloadrm(list=ls())#librarylibrary(dcurves)library(gtsummary)library(tidyverse)library(mlr3verse)library(tidyverse)library(data.table)</...

C++斩题录|递归专题 | leetcode50. Pow(x, n)

个人主页&#xff1a;平行线也会相交 欢迎 点赞&#x1f44d; 收藏✨ 留言✉ 加关注&#x1f493;本文由 平行线也会相交 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 &#x1f354;本专栏旨在提高自己算法能力的同时&#xff0c;记录一下自己的学习过程&#xff0c;希望…...

详解Redis之Lettuce实战

摘要 是 Redis 的一款高级 Java 客户端&#xff0c;已成为 SpringBoot 2.0 版本默认的 redis 客户端。Lettuce 后起之秀&#xff0c;不仅功能丰富&#xff0c;提供了很多新的功能特性&#xff0c;比如异步操作、响应式编程等&#xff0c;还解决了 Jedis 中线程不安全的问题。 …...

【3】单着色器文件读取

Basic.shader文件&#xff0c;可以发现顶点着色器和片段着色器是写在一个文件里的&#xff0c;这里我们将他们读取出来&#xff0c;而不是上一篇使用string的方式。 #shader vertex #version 330 corelayout(location 0) in vec4 position;void main() {gl_Position positio…...

祝贺埃文科技入选河南省工业企业数据安全技术支撑单位

近日&#xff0c;河南省工业信息安全产业发展联盟公布了河南省工业信息安全应急服务支撑单位和河南省工业企业数据安全技术支撑单位遴选结果,最终评选出19家单位作为第一届河南省工业信息安全应急服务支撑单位和河南省工业企业数据安全技术支撑单位。 埃文科技凭借自身技术优势…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

visual studio 2022更改主题为深色

visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中&#xff0c;选择 环境 -> 常规 &#xff0c;将其中的颜色主题改成深色 点击确定&#xff0c;更改完成...

初学 pytest 记录

安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...

2025季度云服务器排行榜

在全球云服务器市场&#xff0c;各厂商的排名和地位并非一成不变&#xff0c;而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势&#xff0c;对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析&#xff1a; 一、全球“三巨头”…...

Redis:现代应用开发的高效内存数据存储利器

一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发&#xff0c;其初衷是为了满足他自己的一个项目需求&#xff0c;即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源&#xff0c;Redis凭借其简单易用、…...

多模态图像修复系统:基于深度学习的图片修复实现

多模态图像修复系统:基于深度学习的图片修复实现 1. 系统概述 本系统使用多模态大模型(Stable Diffusion Inpainting)实现图像修复功能,结合文本描述和图片输入,对指定区域进行内容修复。系统包含完整的数据处理、模型训练、推理部署流程。 import torch import numpy …...