[数据结构 C++] AVL树的模拟实现

在这里插入图片描述

文章目录

  • 1、AVL树
    • 1.1 AVL树的概念
  • 2、AVL树节点的定义
  • 3、AVL树的插入和旋转
    • 3.1 左单旋
      • 左旋代码实现
    • 3.2 右单旋
      • 右旋代码实现
    • 3.3 右左双旋
      • 右左双旋的代码实现
    • 3.4 左右双旋
      • 左右双旋的代码实现
    • 3.5 insert接口实现
  • 4、判断是否为AVL树
    • 判断AVL树的代码实现
  • 5、AVL树的性能

问题引入：
在上一篇文章中，我们提到了二叉搜索树在插入时，可能会形成单边树，会降低二叉搜索的性能。因此我们需要平衡二叉搜索树，降低二叉搜索树的高度，使得二叉搜索树趋于一颗完全二叉树的样子，这样就可以提高二叉搜索树的性能。本篇文章就来介绍一种平衡二叉树，AVL树。
在这里插入图片描述

1、AVL树

1.1 AVL树的概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

  • 它的左右子树都是AVL树
  • 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
    在这里插入图片描述
    如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在O(log N)，搜索时间复杂度O(log N)。
    我们了解了AVL树的基本规则后，下面我们来实现一下AVL树。

2、AVL树节点的定义

template <class K, class V>
struct AVLTreeNode
{
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	pair<K, V> _kv;

	// 右子树 - 左子树 的高度差
	int _bf; // 平衡因子

	AVLTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_kv(kv)
		,_bf(0)
	{}
};

3、AVL树的插入和旋转

AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么
AVL树的插入过程可以分为两步：
1. 按照二叉搜索树的方式插入新节点
2. 调整节点的平衡因子
当某个节点的平衡因子被修改为2的时候，就需要旋转来调节，因此就存在一下四种旋转方式：

3.1 左单旋

我们将 左单旋的情况抽象出来，如下图所示：
在这里插入图片描述

当 h >= 0，且parent->_bf == 2 && subR->_bf == 1时，触发左旋。
在这个图中，只能是在 c 子树新增，才能触发左旋的条件parent->_bf == 2 && subR->_bf == 1。此时进行左旋。
如果是在 b 子树新增，那么仅仅左旋是不够的，
旋转步骤：将60的左树变为30的右树，将60的左树变为30，最后将parent和subR的平衡因子变为0就完成了左旋。

左旋代码实现

// 左单旋
void RotateL(Node* parent)
{
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    Node* parentParent = parent->_parent;

    parent->_right = subRL;
    if (subRL)
        subRL->_parent = parent;
    subR->_left = parent;
    parent->_parent = subR;

    if (_root == parent) // 父节点就是根节点
    {
        _root = subR;
        subR->_parent = nullptr;
    }
    else // 子树情况
    {
        if (parentParent->_left == parent)
        {
            parentParent->_left = subR;
        }
        else
        {
            parentParent->_right = subR;
        }
        subR->_parent = parentParent;
    }
    // 修改平衡因子
    parent->_bf = subR->_bf = 0;
}

3.2 右单旋

我们将 右单旋的情况抽象出来，如下图所示：
在这里插入图片描述
当 h >= 0，且 parent->_bf == 2 && subL->_bf == -1时，触发右旋。
在这个图中，只能是在 a子树新增，才能触发右旋的条件parent->_bf == -2 && subL->_bf == -1。此时进行右旋。
如果是在 b 子树新增，那么仅仅右旋是不够的。
旋转步骤：将30的右树接到60的左树并断开与30的链接，再将60接到30的右树，并将60的父节点改为3，最后再调整parent与SubL的平衡因子为0，就完成整个右旋。

右旋代码实现

// 右单旋
void RotateR(Node* parent)
{
    Node* parentParent = parent->_parent;
    Node* subL = parent->_left;
    Node* subLR = subL->_right;

    parent->_left = subLR;
    if (subLR)
        subLR->_parent = parent;
    subL->_right = parent;
    parent->_parent = subL;

    if (_root == parent) // 父节点是根节点
    {
        _root = subL;
        subL->_parent = nullptr;
    }
    else // 子树情况
    {
        if (parentParent->_left == parent)
        {
            parentParent->_left = subL;
        }
        else
        {
            parentParent->_right = subL;
        }
        subL->_parent = parentParent;
    }
    // 修改平衡因子
    parent->_bf = subL->_bf = 0;
}

3.3 右左双旋

我们将 右左双旋的所有情况抽象出来，如下图所示：
在这里插入图片描述

右左双旋的本质是先将子树右旋，让右侧一侧高，再进行整体的左旋，这样就完成了高度的调整。
双旋的插入位置可以是 b/c 子树，此类型插入之后就会触发右左双旋。
旋转步骤：直接复用右旋，再复用左旋即可。不过旋转的基点不同，右旋是以subR为基点，左旋是以parent为基点旋转的。旋转就完成了，难点在于平衡因子的调节。
平衡因子的调节：
这里主要是 记下subRL最初的平衡因子，它的平衡因子就代表了插入节点是在subRL的左边还是右边插入的，由此可以推出最终的parent与subR的平衡因子。

  • 当subRL->_bf = 1时，最后parent->_bf = -1，subR->_bf = 0，subRL->_bf = 0;
  • 当subRL->_bf = -1时，最后parent->_bf = 0，subR->_bf = 1，subRL->_bf = 0;
  • 当subRL->_bf = 0时，最后parent->_bf = 0，subR->_bf = 0，subRL->_bf = 0;

右左双旋的代码实现

// 右左双旋
void RotateRL(Node* parent)
{
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    int bf = subRL->_bf;

    RotateR(subR);
    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 左边插入
    {
        parent->_bf = 0;
        subR->_bf = 1;
        subRL->_bf = 0;
    }
    else
    {
        assert(false);
    }
}

3.4 左右双旋

我们将 右左双旋的所有情况抽象出来，如下图所示：
在这里插入图片描述

左右双旋与右左双旋的思路是差不多的，我们来看看。
左右双旋的本质是先将子树左旋，让左侧一侧高，在进行整体的右旋,这样就完成了高度的调整。
双旋的插入位置可以是 b/c 子树，此类型插入之后就会触发左右双旋。
旋转步骤：直接复用左旋，再复用右旋即可。不过旋转的基点不同，右旋是以subR为基点，左旋是以parent为基点旋转的。旋转就完成了，难点也是在于平衡因子的调节。
平衡因子的调节：
这里主要是 记下subLR最初的平衡因子，它的平衡因子就代表了插入节点是在subLR的左边还是右边插入的，由此可以推出最终的parent与subL的平衡因子。

  • 当subLR->_bf = 1时，最后parent->_bf = 1，subL->_bf = 0，subLR->_bf = 0;
  • 当subLR->_bf = 1时，最后parent->_bf = 0，subL->_bf = -1，subLR->_bf = 0;
  • 当subLR->_bf = 0时，最后parent->_bf = 0，subL->_bf = 0，subLR->_bf = 0;

左右双旋的代码实现

// 左右双旋
void RotateLR(Node* parent)
{
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    int bf = subLR->_bf;

    RotateL(subL);
    RotateR(parent);

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

3.5 insert接口实现

bool Insert(const pair<K, V>& kv)
{
    if (_root == nullptr)
    {
        _root = new Node(kv);
        return true;
    }

    Node* parent = nullptr;
    Node* cur = _root;
    // 1、先找到插入的位置
    while (cur)
    {
        if (cur->_kv.first < kv.first)
        {
            parent = cur;
            cur = cur->_right;
        }
        else if (cur->_kv.first > kv.first)
        {
            parent = cur;
            cur = cur->_left;
        }
        else
        {
            return false;
        }
    }
    // 2、new一个节点，并与parent链接起来
    cur = new Node(kv);
    if (parent->_kv.first < kv.first)
    {
        parent->_right = cur;
        cur->_parent = parent;
    }
    else
    {
        parent->_left = cur;
        cur->_parent = parent;
    }
    // 3、调平横 —— 旋转 + 平衡因子的调节
    while (parent)
    {
        if (parent->_left == cur)
        {
            parent->_bf--;
        }
        else
        {
            parent->_bf++;
        }

        if (0 == parent->_bf)
        {
            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)
            {
                RotateL(parent);
            }
            else if (parent->_bf == 2 && cur->_bf == -1)
            {
                RotateRL(parent);
            }
            else if (parent->_bf == -2 && cur->_bf == 1)
            {
                RotateLR(parent);
            }
            else if (parent->_bf == -2 && cur->_bf == -1)
            {
                RotateR(parent);
            }

            // 1、旋转让这颗子树平衡了
            // 2、旋转降低了这颗子树的高度，恢复到跟插入前一样的高度，所以对上一层没有影响，不用继续更新
            break;
        }
        else
        {
            assert(false);
        }
    }
    return true;
}

4、判断是否为AVL树

AVL树的本质是搜索二叉树 + 平衡机制，所以验证步骤：
1、首先判断是否为搜索树，写一个中序遍历，看看是不是升序即可；
2、按照AVL树的性质来判断：

  • 每个节点的左右子树高度差绝对值小于等于1；
  • 节点的平衡因子是否正确；

判断AVL树的代码实现

bool _IsBalance(Node* pRoot)
{
    if (pRoot == nullptr)
        return true;

    int leftHeight = _Height(pRoot->_left);
    int rightHeight = _Height(pRoot->_right);
    if (rightHeight - leftHeight != pRoot->_bf)
    {
        cout << pRoot->_kv.first << "平衡因子异常" << endl;
        return false;
    }

    return rightHeight - leftHeight < 2
        && _IsAVLTree(pRoot->_left)
        && _IsAVLTree(pRoot->_right);
}

size_t _Height(Node* pRoot)
{
    if (pRoot == nullptr)
        return 0;

    int leftHeight = _Height(pRoot->_left);
    int rightHeight = _Height(pRoot->_right);

    return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

void _InOrder(Node* pRoot)
{
    if (pRoot == nullptr)
        return;

    _InOrder(pRoot->_left);
    cout << pRoot->_kv.first << " ";
    _InOrder(pRoot->_right);
}

5、AVL树的性能

AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即O(log N)。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。
AVL树的实现代码放在代码仓库：https://gitee.com/xiaobai-is-working-hard-jy/data-structure/tree/master/AVLTree

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

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

相关文章

金和OA c6 uploadfileeditorsave接口存在任意文件上传漏洞

金和OA c6 uploadfileeditorsave接口存在任意文件上传漏洞

产品简介 金和网络是专业信息化服务商&#xff0c;为城市监管部门提供了互联网监管解决方案&#xff0c;为企事业单位提供组织协同OA系统升开发平台&#xff0c;电子政务一体化平台智慧电商平合等服务 漏洞概述 金和-c6 uploadfileeditorsave 任意文件上传&#xff0c;攻击者…
阅读更多...
计算机网络（9）：无线网络

计算机网络（9）：无线网络

无线局域网 WLAN 无线局域网常简写为 WLAN (Wireless Local Area Network)。 无线局域网的组成 无线局域网可分为两大类。第一类是有固定基础设施的&#xff0c;第二类是无固定基础设施的。所谓“固定基础设施”是指预先建立起来的、能够覆盖一定地理范围的一批固定基站。 …
阅读更多...
6个关键词，回顾网络安全行业的 2023！

6个关键词，回顾网络安全行业的 2023！

话不多说&#xff0c;直接上 01 生成式人工智能 AIGC 热度&#xff1a;⭐️⭐️⭐️⭐️⭐️ AIGC 的发展不仅降低了内容创作的门槛&#xff0c;还为聊天机器人、数字人、元宇宙等领域提供了新的发展机遇。2023 年 8 月&#xff0c;首届人工智能生成内容国际会议在上海落地&…
阅读更多...
Paddle3D 2 雷达点云CenterPoint模型训练

Paddle3D 2 雷达点云CenterPoint模型训练

2 Paddle3D 雷达点云CenterPoint模型训练–包含KITTI格式数据地址 2.0 数据集 百度DAIR-V2X开源路侧数据转kitti格式。 2.0.1 DAIR-V2X-I\velodyne中pcd格式的数据转为bin格式 参考源码&#xff1a;雷达点云数据.pcd格式转.bin格式 def pcd2bin():import numpy as npimport…
阅读更多...
C++面向对象语法总结(三）

C++面向对象语法总结(三）

目录 《C面向对象语法总结(一&#xff09;》《C面向对象语法总结(二&#xff09;》 二十一、多继承 C允许一个类可以有多个父类&#xff08;不建议使用&#xff0c;会增加程序设计复杂度&#xff09;在多继承中&#xff0c;会按照继承顺序将父类的成员变量放到子类成员变量的…
阅读更多...
踩坑Vant组件 Dialog的组件调用

踩坑Vant组件 Dialog的组件调用

今天踩了一个非常蠢的坑&#xff0c;自己给自己蠢死的坑 在使用组件调用时自己没引入Dialog组件导致一直报错 不知道为什么全局引入不好使&#xff0c;后来使用了局部引用 现在没问题了 就这样局部引入一个Dialog.Component就可以了
阅读更多...
CEEMDAN +组合预测模型(Transformer - BiLSTM+ ARIMA)

CEEMDAN +组合预测模型(Transformer - BiLSTM+ ARIMA)

目录 往期精彩内容&#xff1a; 前言 1 风速数据CEEMDAN分解与可视化 1.1 导入数据 1.2 CEEMDAN分解 2 数据集制作与预处理 3 基于CEEMADN的 Transformer - BiLSTM 模型预测 3.1 定义CEEMDAN-Transformer - BiLSTM预测模型 3.2 设置参数&#xff0c;训练模型 4 基于A…
阅读更多...
【日积月累】Java Lambda 表达式

【日积月累】Java Lambda 表达式

目录 【日积月累】Java Lambda 表达式 1.前言2.语法3.应用场景3.1简化匿名内部类的编写3.1简化匿名内部类的编写3.2简化集合类中的操作3.3实现函数式接口3.4简化多个方法的调用3.5简化异步编程 4.总结5.参考 文章所属专区 日积月累 1.前言 Lambda表达式是一个匿名函数&#…
阅读更多...
数据库索引、三范式、事务

数据库索引、三范式、事务

索引 索引&#xff08;Index&#xff09;是帮助 MySQL 高效获取数据的数据结构。常见的查询算法,顺序查找,二分查找,二叉排序树查找,哈希散列法,分块查找,平衡多路搜索树 B 树&#xff08;B-tree&#xff09;。 常见索引原则有 选择唯一性索引&#xff1a;唯一性索引的值是唯…
阅读更多...
爬虫入门与urllibrequests

爬虫入门与urllibrequests

前情摘要 一、web请求全过程剖析 我们浏览器在输入完网址到我们看到网页的整体内容, 这个过程中究竟发生了些什么? 我们看一下一个浏览器请求的全过程 接下来就是一个比较重要的事情了. 所有的数据都在页面源代码里么? 非也~ 这里要介绍一个新的概念 那就是页面渲染数据的…
阅读更多...
[C#]使用onnxruntime部署Detic检测2万1千种类别的物体

[C#]使用onnxruntime部署Detic检测2万1千种类别的物体

【源码地址】 github地址&#xff1a;https://github.com/facebookresearch/Detic/tree/main 【算法介绍】 Detic论文&#xff1a;https://arxiv.org/abs/2201.02605v3 项目源码&#xff1a;https://github.com/facebookresearch/Detic 在Detic论文中&#xff0c;Detic提到…
阅读更多...
基于Java SSM框架实现中国古诗词学习平台项目【项目源码】

基于Java SSM框架实现中国古诗词学习平台项目【项目源码】

基于java的SSM框架实现中国古诗词学习平台系统演示 JSP技术介绍 JSP技术本身是一种脚本语言&#xff0c;但它的功能是十分强大的&#xff0c;因为它可以使用所有的JAVA类。当它与JavaBeans 类进行结合时&#xff0c;它可以使显示逻辑和内容分开&#xff0c;这就极大的方便了用…
阅读更多...
Docker中的核心概念

Docker中的核心概念

1.镜像 Image 一个镜像就代表一个软件。mysql镜像、redis镜像、mq镜像 2.容器 Container 一个镜像运行一次就会生成一个容器&#xff0c;容器就是一个运行的软件服务。 3.远程仓库 Repository 远程仓库用来存储所有软件的镜像&#xff0c;Docker Hub 4.本地仓库 用来存储…
阅读更多...
谷歌推出了一种名为提示扩展（Prompt Expansion）的创新框架，旨在帮助用户更轻松地创造出既高质量又多样化的图像。

谷歌推出了一种名为提示扩展（Prompt Expansion）的创新框架，旨在帮助用户更轻松地创造出既高质量又多样化的图像。

谷歌推出了一种名为提示扩展&#xff08;Prompt Expansion&#xff09;的创新框架&#xff0c;旨在帮助用户更轻松地创造出既高质量又多样化的图像。 论文标题: Prompt Expansion for Adaptive Text-to-Image Generation 论文链接: https://arxiv.org/pdf/2312.16720.pdf 问…
阅读更多...
如何删除K8S中的Pod

如何删除K8S中的Pod

天行健&#xff0c;君子以自强不息&#xff1b;地势坤&#xff0c;君子以厚德载物。 每个人都有惰性&#xff0c;但不断学习是好好生活的根本&#xff0c;共勉&#xff01; 文章均为学习整理笔记&#xff0c;分享记录为主&#xff0c;如有错误请指正&#xff0c;共同学习进步。…
阅读更多...
生信技能32 - 导入UCSC公共数据库SNP数据至本地MySQL数据库

生信技能32 - 导入UCSC公共数据库SNP数据至本地MySQL数据库

本文以导入SNP151.txt数据库为例，其他数据库文件操作类似。 1. 数据文件下载 UCSC下载网址： https://hgdownload.cse.ucsc.edu/goldenPath/hg19/database/ 以下为Linux下载文件方式 wget https://hgdownload.cse.ucsc.edu/goldenPath/hg19/database/snp151.sql wget -c -…
阅读更多...
[ASIS 2019]Unicorn shop

[ASIS 2019]Unicorn shop

点入题目看见四个可购买的东西&#xff0c;但是都购买不了&#xff0c;最后一个价格大的脱俗&#xff0c;猜测成功买到后会得到flag&#xff0c;但是购买时提示操作失败只允许一个字符。查看源码发现在utf-8后面特意标注提示 涉及到了字符编码和字符集的概念&#xff1a; UTF-…
阅读更多...
单机多进程,每个进程多张卡 mpi nccl 程序设计检验

单机多进程,每个进程多张卡 mpi nccl 程序设计检验

做了部分注释&#xff0c;比较乱 本示例结构&#xff1a; 1&#xff0c;源代码 #include <stdlib.h> #include <stdio.h> #include "cuda_runtime.h" #include "nccl.h" #include "mpi.h" #include <unistd.h> #include <…
阅读更多...
流量预测资源总结（不断更新）

流量预测资源总结（不断更新）

目录 整理流量预测数据集&#xff08;1&#xff09;Telecom Italia 意大利电信 2015&#xff08;2&#xff09;City Cellular Traffic Map (C2TM) 2015&#xff08;3&#xff09;、LTE Network Traffic Data_kaggle&#xff08;4&#xff09;、Cellular Traffic Analysis Data …
阅读更多...
Python十大实用技巧【附源码】

Python十大实用技巧【附源码】

1、什么是Python? Python简介 Python 是一个高层次的结合了解释性、编译性、互动性和面向对象的脚本语言。 Python 的设计具有很强的可读性&#xff0c;相比其他语言经常使用英文关键字&#xff0c;其他语言的一些标点符号&#xff0c;它具有比其他语言更有特色语法结构。 …
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站