「C++」AVL树的实现(动图)

在这里插入图片描述

💻文章目录

  • AVL树
    • 概念
    • AVL的查找
    • AVL树的插入
  • 代码部分
    • AVL树的定义
    • 查找
    • 插入
    • 旋转
  • 📓总结


AVL树

概念

AVL树又名高度平衡的二叉搜索树,由G. M. Adelson-Velsky和E. M. Landis发明,顾名思义,其任意节点的左右子树最大高度差都不超过1,以此来阻止二叉搜索树退化成为单叉树这种情况。

AVL树具有以下的特性:

  • 任意节点的左右子树最大高度差不超过1
  • 所有节点的左节点都比父节点小。
  • 所有节点的右节点都比父节点大。
  • 它的左右子树都是AVL树。
  • 中序遍历是有序的

AVL树与普通二叉搜索树的对比:

在这里插入图片描述

AVL的查找

AVL树的查找与二叉搜索树基本一致,因为其自身的性质,所以只要查找的数据比当前节点小就要到左节点找,反之就是右节点。

请添加图片描述

AVL树的插入

在介绍插入前得先说一下平衡因子,这是为了得知插入新结点后树是否还平衡的方式之一。

平衡因子是在每个结点上安置一个数字,如果是新插入的节点则它的数值为0,如果其在双亲节点的右边,则双亲节点的平衡因子++,反之–,然后继续向上调整,直到父节点的因子为0/2/-2。

在这里插入图片描述

AVL因为要保持其高度平衡的特性,所以每次插入都要检查其是否平衡,如果不平衡(平衡因子的绝对值大于1),则需要通过旋转来让树保持平衡。

AVL树的旋转大致分为两种情况:

  • 极端倾斜(左倾、右倾)
  • 非极端倾斜(局部左倾,局部右倾)

极端倾斜:
极端倾斜的情况比较容易解决,如果是右倾,那么只需要让平衡因子为2的节点做左旋运动,然后更新平衡因子即可,左倾则和右倾相反,做右旋操作。
请添加图片描述

局部倾斜:
局部倾斜分为局部左倾和右倾,而左右倾其中又分为三中情况,为了方便说明,我用parent来表示平衡因子(bf)为2的节点,subR来表示parent->right,subRL来表示subR->left 。

  • subRL为0则表示subRL为新增节点
  • subRL为1则表示新节点在subRL的右子树
  • subRL为-1则表示新节点在subRL的左子树

subRL为0的情况:
在这里插入图片描述
subRL为1的情况:
在这里插入图片描述
subRL为-1的情况:
在这里插入图片描述

代码部分

AVL树的定义

因为我们需要频繁去调整树的平衡,使用普通的二链结构会比较难以控制节点,所以我使用了三叉链的结构,多增加了一个指向父节点的指针。

template<class K, class V>
struct AVLTreeNode
{
	AVLTreeNode(const std::pair<K, V> kv)
	: _left(nullptr)	
	, _right(nullptr)
	, _parent(nullptr)
    , _kv(kv)
	, _bf(0)
	{}	

	AVLTreeNode<K, V>* _left;	//左节点
	AVLTreeNode<K, V>* _right;	//右节点
	AVLTreeNode<K, V>* _parent;	//父节点
    std::pair<K, V> _kv;		//使用pair当作数据
	int _bf;   // 节点的平衡因子
};

查找

二叉搜索树与AVL树的搜索基本无区别

template <class K, class V>
typename AVLTree<K, V>::Node* AVLTree<K, V>::find(const std::pair<K, V>& data)
{
    Node* cur = _root;	
    while(cur)
    {
        if(cur->_kv.first < data.first)
        {	//到右节点寻找
            cur = cur->_right;
        }
        else if(cur->_kv.first > data.first)
        {	//到左节点寻找
            cur = cur->_left;
        }
        else 
        {	//找到
            return cur;
        }
    }

    return cur;
}

插入

AVL树的插入无非也就是弄清楚倾斜的时机和位置,就和上方所说的,AVL树的旋转情况只有极端和非极端的,如果没有出现不平衡则向上调整。

template <class K, class V>
bool AVLTree<K, V>::Insert(const std::pair<K, V> data)
{
    if(!_root)
    {
        _root = new Node(data);
        return true;
    }

    Node* cur = _root;
    Node* parent = nullptr;
    
    while(cur)	//先搜索
    {
        if(cur->_kv.first < data.first)
        {
            parent = cur;
            cur = cur->_right;
        }
        else if(cur->_kv.first > data.first)
        {
            parent = cur;
            cur = cur->_left;
        }
        else 
            return false;
    }

    cur = new Node(data);		//创建新节点
    cur->_parent = parent;		//链接
    
    if(!parent->_left)
    {
        parent->_left = cur;
    }
    else 
    {
        parent->_right = cur;
    }

    while(parent)
    {
        if(cur == parent->_left)
            parent->_bf--;		//这里与上方动图有些许不同,动图与我平衡因子的加减是相反的
        else	// cur == parent->_right
            parent->_bf++;

        if(parent->_bf == 0)	//为0说明左右节点最大高度差一致
            break;
        else if(parent->_bf == 1 || parent->_bf == -1)	//为1则继续向上调整
        {
            cur = parent;		
            parent = parent->_parent;
        }
        else if(parent->_bf == 2 || parent->_bf == -2)	//出现了不平衡的清空
        {
            if(parent->_bf == 2 && cur->_bf == 1)	//极端右倾
            {
                RotateL(parent);					//左倾
            }
            else if(parent->_bf == -2 && cur->_bf == -1)	//极端左倾
            {
                RotateR(parent);					//右倾
            }
            else if(parent->_bf == 2 && cur->_bf == -1)	//局部左倾
            {
                RotateRL(parent);					//先右倾,再左倾
            }
            else if(parent->_bf == -2 && cur->_bf == 1)	//局部右倾
            {	
                RotateLR(parent);					//左倾再右倾
            }

            break;
        }
        else 
            assert(false);
    }
    return true;
}

旋转

AVL树的旋转其难点在于正确的连接节点,与调整平衡因子的数值。

void AVLTree<K, V>::RotateL(Node* parent)
{	//左旋
    Node* subR = parent->_right;	
    Node* subRL = subR->_left;
    Node* parentParent = parent->_parent;
	
    parent->_right = subRL;		//交换父节点和其右孩子的位置
    parent->_parent = subR;
    subR->_left = parent;		
    subR->_parent = parentParent;
    
    if(subRL)	//subRL有为空的可能性
        subRL->_parent = parent;

    if(_root == parent)
    {	
        _root = subR;
    }
    else 
    {	//连接祖父节点
        if(parent == parentParent->_left)
        {
            parentParent->_left = subR;
        }
        else 
        {
            parentParent->_right = subR;
        }
    }
    parent->_bf = subR->_bf = 0;	//调整平衡因子
}

void AVLTree<K, V>::RotateR(Node* parent)
{
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    Node* parentParent = parent->_parent;

    subL->_right = parent;
    subL->_parent = parentParent;

    parent->_left = subLR;
    parent->_parent = subL;

    if(subLR)
        subLR->_parent = parent;

    if(parent == _root)
        _root = subL;
    else
    {
        if(parent == parentParent->_left)
            parentParent->_left = subL;
        else
            parentParent->_right = subL;
    }

    subL->_bf = parent->_bf = 0;
} 

void AVLTree<K, V>::RotateRL(Node* parent)
{
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    int bf = subRL->_bf;	//先记录平衡因子,以防调整后丢失

    RotateR(parent->_right);
    RotateL(parent);
	//调整因子
    if(bf == 0)	//说明subRL是新增节点
    {
        parent->_bf = subR->_bf = subRL->_bf = 0;
    }
    else if(bf == 1)	//新增节点在subRL的右子树
    {
        parent->_bf = -1;
        subR->_bf = 0;
        subRL->_bf = 0;
    }
    else if(bf == -1) 	//新增节点在subRL的右子树
    {
        subRL->_bf = 0;
        subR->_bf = 1;
        parent->_bf = 0;
    }
    else 
    {
        assert(false);
    }
}

void AVLTree<K, V>::RotateLR(Node* parent)
{
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    int bf = subLR->_bf;

    RotateL(parent->_left);
    RotateR(parent);

    if(bf == 0)
    {
        parent->_bf = subL->_bf = subLR->_bf = 0;
    }
    else if(bf == -1)
    {
        parent->_bf = 1;
        subL->_bf = 0;
        subLR->_bf = 0;
    }
    else if(bf == 1)
    {
        subL->_bf = -1;
        parent->_bf = 0;
        subLR->_bf = 0;
    }
    else 
        assert(false);
}

📓总结

AVL的时间复杂度:

函数时间复杂度
find O ( l o g 2 n ) O(log_2n) O(log2n)
insert() O ( l o g 2 n ) O(log_2n) O(log2n)

📜博客主页:主页
📫我的专栏:C++
📱我的github:github

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

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

相关文章

模方4.1.0新版本正式上线啦!

新增单体化自动建模&#xff0c;直角搭桥、复制三角形两种方式补洞等功能&#xff0c;还有更多功能优化&#xff0c;让你的三维模型更好看&#xff01; 欢迎前往官网下载试用→武汉大势智慧-实景三维-云端建模-新型基础设施

2023年中国数字员工行业发展趋势分析:行业市场规模迅猛增长[图]

数字员工是指利用人工智能、自然语言处理、机器学习等技术&#xff0c;通过数字渠道提供自动化或半自动化的客户服务形式。数字人系统通过音频和视频结构化解析技术处理用户输入&#xff0c;并使用自然语言处理和机器学习等技术分析用户意图&#xff0c;生成相应的对话内容&…

串口工作流程硬核解析,没有比这更简单的了!

串口通信,就是我们常说的串口通讯,是一种短距离、点对点的数据传输方式。它基于串行通信协议,通过串口线连接设备进行数据交互。串口在很多硬件系统中广泛使用,是工控机、单片机、外设设备之间信息交换的重要接口。 那串口是怎么工作的呢?我们举个形象的例子。假设A和B是两台…

算法——双指针

一、背景知识 双指针&#xff08;Two Pointers&#xff09;&#xff1a;指的是在遍历元素的过程中&#xff0c;不是使用单个指针进行访问&#xff0c;而是使用两个指针进行访问&#xff0c;从而达到相应的目的。对撞时针&#xff1a; 两个指针方向相反对撞指针一般用来解决有序…

盘点35个Python书籍Python爱好者不容错过

盘点35个Python书籍Python爱好者不容错过 学习知识费力气&#xff0c;收集整理更不易。 知识付费甚欢喜&#xff0c;为咱码农谋福利。 链接&#xff1a;https://pan.baidu.com/s/1uf-MXZc9aC7y3Qju6VnCYw?pwd8888 提取码&#xff1a;8888 书籍名称&#xff1a; Django教…

效率提升利器:Automa插件的实用指南

Automa是一个chrome扩展&#xff0c;通过拖拽0代码实现工作流&#xff0c;模拟网页的各种点击、表单填写等操作&#xff0c;使用时点击插件脚本一键执行&#xff0c;或者设置定时执行&#xff0c;从而简化我们的工作。 功能介绍 官方文档地址&#xff1a;Getting started | Au…

Altium Designer学习笔记2

原理图的绘制 需要掌握的是系统自带原理图库元件的添加。

HR问:有没有免费的人才测评工具?

人才测评工具分为两种&#xff0c;一种是测评量表&#xff0c;一种是操作量表的工具&#xff0c;在线测评的方式没有普及之前&#xff0c;很多朋友都习惯把测评量表&#xff08;测评试题&#xff09;称为测评工具&#xff0c;其实我认为量表就是量表&#xff0c;而试试量表测评…

全国的科技创新情况数据分享,涵盖2020-2022年三年情况

随着国家对科技创新的重视和大力支持&#xff0c;全国的科技创新情况越来越受到关注。 我们根据中国城市统计年鉴的这方面指标&#xff0c;分析汇总得出全国科技创新情况数据&#xff0c;需要说明的是&#xff0c;由于统计年鉴指标调整&#xff0c;每一年的数据并非字段相同&a…

隐私计算迎来千亿级风口,一文讲清它的技术理论基础

一、安全多方计算 在讨论安全多方计算(下文使用 MPC) 之前&#xff0c;我们先讨论安全多方计算的设定&#xff0c;在MPC 的所有参与者中&#xff0c;某些参与者可能会被一个敌手 (攻击者) 控制&#xff0c;在敌手控制下的参与者被称为被腐化方&#xff0c;它在协议执行过程中会…

算法(圆的定义和相关术语)

无向图的度 图中每一个顶点的度定义为以该项点为一个端点的边的数目 #include <cstdio>const int MAXN 100;int degree[MAXN] { 0 };int main() {int n, m, u, v;scanf("%d%d", &n, &m);//在输出边度的时候就已经表示度的数目了&#xff0c;所以用一…

Atlassian发布最新补贴政策,Jira/Confluence迁移上云最低可至零成本

到2024年2月15日&#xff0c;Atlassian将不再提供对Jira、Confluence、Jira Service Management等Server版产品的支持。 近期&#xff0c;Atlassian推出了一项针对云产品的特殊优惠。现在从Server版迁移到云版&#xff0c;您能享受到高额补贴&#xff0c;甚至成本低至零元。立…

vue中data属性为什么是一个函数?

​&#x1f308;个人主页&#xff1a;前端青山 &#x1f525;系列专栏&#xff1a;Vue篇 &#x1f516;人终将被年少不可得之物困其一生 依旧青山,本期给大家带来vue篇专栏内容:vue-data属性 目录 为什么data属性是一个函数而不是一个对象&#xff1f; 一、实例和组件定义dat…

Servlet---API详解

文章目录 HttpServlet基础方法doXXX方法Servlet的生命周期 HttpServletRequest获取请求中的信息获取请求传递的参数获取 query string 里的数据获取form表单里的数据获取JSON里的数据如何解析JSON格式获取数据返回数据 HttpServletResponse设置响应的Header设置不同的状态码设置…

深入探讨软件测试技术:方法、工具与最佳实践

&#x1f482; 个人网站:【 海拥】【神级代码资源网站】【办公神器】&#x1f91f; 基于Web端打造的&#xff1a;&#x1f449;轻量化工具创作平台&#x1f485; 想寻找共同学习交流的小伙伴&#xff0c;请点击【全栈技术交流群】 引言 软件测试是软件开发生命周期中至关重要的…

【操作系统】文件系统之文件共享与文件保护

文章目录 文件共享硬链接软链接 文件保护口令保护加密保护访问控制 文件共享 为了实现文件的共享&#xff0c;引入了“计数器”字段&#xff0c;当一个文件每被一个用户所共享&#xff0c;那么计数器就加一。如果一个用户删除文件&#xff0c;计数器相应的减一。如果计数器为0…

威视佰科荣获:2023年“AI天马”高成长性企业

11月14日下午&#xff0c;2023年度“AI天马”认定评审会顺利召开。落实《深圳经济人工智能产业促进条例》&#xff0c;加快推进智能机器人、智能传感器、智能网联汽车、智能终端、脑科学和类脑智能等人工智能相关产业发展&#xff0c;加速AI产业化和产业AI化进程&#xff0c;持…

Redis篇---第十二篇

系列文章目录 文章目录 系列文章目录前言一、Memcache与Redis的区别都有哪些?二、单线程的redis为什么这么快三、redis的数据类型,以及每种数据类型的使用场景前言 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站,这篇…

BGP笔记实验

IGP(Interior Gateway Protocol)——内部网关协议 OSPF RIP IS-IS IGRP EIGRP EGP(External Gateway Protocol)——外部网关协议 EGP BGP——边界网关协议 AS——自治系统 由单一组织or机构独立维护的网络设备&网络资源的集合 网络范围太大 自治 AS号 为了区分不同…

66从零开始学Java之集合中的Collection体系

作者&#xff1a;孙玉昌&#xff0c;昵称【一一哥】&#xff0c;另外【壹壹哥】也是我哦 千锋教育高级教研员、CSDN博客专家、万粉博主、阿里云专家博主、掘金优质作者 前言 截止到今天&#xff0c;我们《从零开始学Java系列》的文章已经要到一个新的阶段了。在此之前&#xf…