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

news/2024/4/25 18:58:01
在这里插入图片描述

💻文章目录

  • 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->_rightparent->_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;elseparentParent->_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


https://www.xjx100.cn/news/3091606.html

相关文章

OpenCV [c++](图像处理基础示例小程序汇总)

OpenCV [c++](图像处理基础示例小程序汇总) 推荐 原创 NCUTer 2023-04-04 14:18:49 文章标签 Image 图像处理 文章分类 计算机视觉 人工智能 在51CTO的第一篇博文 阅读数1467 一、图像读取与显示 #include<opencv2/opencv.hpp> #include<iostream>using…

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

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

弄懂Rust编程中的Trait

1.定义 trait trait 定义了某个特定类型拥有可能与其他类型共享的功能。可以通过 trait 以一种抽象的方式定义共享的行为。可以使用 trait bounds 指定泛型是任何拥有特定行为的类型。 一个类型的行为由其可供调用的方法构成。如果可以对不同类型调用相同的方法的话&#xff…

C语言——深入理解指针(第四章)

一、二级指针 在讲二级指针之前&#xff0c;我们先回顾一下指针的定义一直之前讲的一级指针。 1.指针的定义 一级指针&#xff1a;是一个指针变量&#xff0c;指向一个普通变量&#xff0c;并保存该普通变量的地址;二级指针&#xff1a;是一个指针变量&#xff0c;指向一个一…

轻松驾驭Linux命令:账户查看、目录文件操作详解

&#x1f3a5; 屿小夏 &#xff1a; 个人主页 &#x1f525;个人专栏 &#xff1a; Linux系统操作 &#x1f304; 莫道桑榆晚&#xff0c;为霞尚满天&#xff01; 文章目录 &#x1f4d1;引言&#x1f324;️查看账户☁️whoami☁️who &#x1f324;️ls和目录文件的创建删除☁…

Vue3入门(与Vue2进行对比)

1. Vue2 选项式 API vs Vue3 组合式API 特点&#xff1a; 代码量变少分散式维护变成集中式维护 2. Vue3的优势 使用create-vue搭建Vue3项目 1. 认识create-vue create-vue是Vue官方新的脚手架工具&#xff0c;底层切换到了 vite &#xff08;下一代前端工具链&#xff09;&…

axios 请求合集

post 请求 请求负载请求参数&#xff08;Request Payload&#xff09; import axios from axios import qs from query-stringexport function getRoles(data){return axios.post(目标地址,data,{headers:{Content-Type: application/json,},}) }表单请求参数&#xff08;Form…

鸿蒙原生应用/元服务开发-AGC分发如何配置版本信息(上)

1.配置HarmonyOS应用的“发布国家或地区”。 2.设置是否为开放式测试版本。 注意&#xff1a;HarmonyOS应用开放式测试当前仅支持手机、平板、智能手表。如开发者想发布为开放式测试版本&#xff0c;选择“是”。正式发布的版本请选择“否”。 3.在“软件版本”下点击“软件包…