移情别恋c++ ദ്ദി˶ｰ̀֊ｰ́ ) ——14.AVL树

1.AVL 树

1.1AVL 树的概念

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

一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

1.它的左右子树都是AVL树

2.左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在 O(log_2 n)，搜索时间复杂度O(log_2 n)。

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;//右子树高度-左子树高度,只有孩子发生变化，bf才有可能发生变化！！！！，若改变父亲，bf不变！！！！！！AVLtreenode(const pair<K, V>& _kv)    //初始化列表:_left(nullptr),_right(nullptr),_parent(nullptr),kv(_kv),bf(0){}
};

3.AVL树的插入！！！！！！！ 

3.1初步插入

初步插入与bst的插入一致，不过里面的数据类型是pair<first,second>,并且是根据first进行比较

if (root == nullptr)
{root = new node(_kv);return true;
}
node* parent = nullptr; //比bst多了一个parent
node* cur = root;       //while (cur)
{parent = cur;if (cur->kv.first < _kv.first){cur = cur->_right;}else if (cur->kv.first > _kv.first){cur = cur->_left;}else{return false;}
}
cur = new node(_kv);
if (parent->kv.first < _kv.first)
{parent->_right = cur;
}
else
{parent->_left = cur;
}
cur->_parent = parent;    //记得连接parent和cur

3.2调整平衡因子 

while (cur != root)
{if (cur == parent->_left)parent->bf--;//第一次！！！检查parent左边原来必为空else {parent->bf++;//第一次！！！检查parent右边原来必为空}if (parent->bf == 0) //相当于bf没改变，可直接退出{break;}else if (parent->bf == 1 || parent->bf == -1) //bf改变了继续向上找   {cur = parent;parent = parent->_parent;}else if(parent->bf == -2 || parent->bf == 2){          //-2||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;//1次旋转完成后不需要再调整了}
}

3.3旋转调整！！！！！！ 

1.新节点插入较高右子树的右侧---右右：左单旋

 

 由上述可知，c必定是x类型的avl树，如果是其他类型的，可能60这个节点的平衡因子就变成-2或2了，（当然，这只是单独举一个例子分析，便于分析代码，不代表所有情况）

void rotateL(node* parent)//左旋，（新节点插入到较高右子树的右侧）//   1.右右
{node* subr = parent->_right;node* subrl = subr->_left;parent->_right = subrl;subr->_left= parent;node* ppnode = parent->_parent;parent->_parent = subr;if (subrl) //subrl可能为空！！！！！！！！！！！！！！！{subrl->_parent = parent;}if (parent == root) // 即如果parent->_parent==nullptr{root = subr;subr->_parent = nullptr;}else{if (ppnode->_left == parent)   //需要再查找一下放左边还是右边{ppnode->_left = subr;}else if (ppnode->_right == parent){ppnode->_right = subr;}subr->_parent = ppnode;}parent->bf = subr->bf = 0;   //重置平衡因子
}

2.新节点插入较高左子树的左侧---左左：右单旋 

和左单旋分析方法一致

void rotateR(node* parent)//右旋，（新节点插入到较高左子树的左侧）//   2.左左
{node* subl = parent->_left;node* sublr = subl->_right;parent->_left = sublr;if (sublr)               //sublr可能为空！！！！！！！sublr->_parent = parent;node* ppnode = parent->_parent;subl->_right = parent;parent->_parent=subl;if (root == parent){root = subl;subl->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subl;}else if (ppnode->_right == parent){ppnode->_right = subl;}subl->_parent = ppnode;}subl->bf = parent->bf = 0;//重置平衡因子}

3. 新节点插入较高左子树的右侧---左右：先左单旋再右单旋

十分巧妙的是：经过一次左旋(parent->_left)后，就变成左左类型了，这样就能复用右单旋(parent)达成平衡 

void rotateLR(node* parent)//左旋一次，再右旋一次，还需要根据不同的_bf更新平衡因子
{node* subl = parent->_left;node* sublr= subl->_right;int _bf = sublr->bf;rotateL(parent->_left);rotateR(parent);if (_bf == 0){//sublr自己就是新增加的节点parent->bf = subl->bf = sublr->bf = 0;}else if (_bf == 1){//sublr的右子树新增parent->bf = 0;subl->bf = -1;sublr->bf = 0;}else if (_bf == -1){//sublr的左子树新增parent->bf = 1;subl->bf = 0;sublr->bf = 0;}
}

4.新节点插入较高右子树的左侧---右左：先右单旋再左单旋  

与上方分析方法一致

void rotateRL(node* parent)   //右旋一次，再左旋一次，还需要根据不同的_bf更新平衡因子
{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 = 0;subr->bf = 1;subrl->bf = 0;}else if (_bf == 1){   //subrl的左子树新增parent->bf = -1;subr->bf = 0;subrl->bf = 0;}
}

总结：

假如以pParent为根的子树不平衡，即pParent的平衡因子为2或者-2，分以下情况考虑

1. pParent的平衡因子为2，说明pParent的右子树高，设pParent的右子树的根为pSubR

当pSubR的平衡因子为1时，执行左单旋

当pSubR的平衡因子为-1时，执行右左双旋

2. pParent的平衡因子为-2，说明pParent的左子树高，设pParent的左子树的根为pSubL

当pSubL的平衡因子为-1是，执行右单旋

当pSubL的平衡因子为1时，执行左右双旋

旋转完成后，原pParent为根的子树个高度降低，已经平衡，不需要再向上更新。  

4.AVL树的判断 

 AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步：

1. 验证其为二叉搜索树

：如果中序遍历可得到一个有序的序列，就说明为二叉搜索树

2. 验证其为平衡树

（1）每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)

（2）节点的平衡因子是否计算正确  

void inorder()
{_inorder(root);
}void _inorder(node* root)
{if (root == nullptr)return;_inorder(root->_left);cout << root->kv.first << " ";_inorder(root->_right);
}int _height(node* root)//取得高度
{if (root == nullptr)return 0;int lh = _height(root->_left);int rh = _height(root->_right);return lh > rh ? lh + 1 : rh + 1;//记得+1
}bool isbalance()
{return _isbalance(root);
}bool _isbalance(node* root)
{if (root == nullptr)return true;int lh = _height(root->_left);int rh = _height(root->_right);if ((rh - lh) !=root->bf)//判断是否符合平衡因子计算公式{cout << "异常" << endl;return false;}return (rh - lh) <2 && (rh - lh)>-2 && _isbalance(root->_left) && _isbalance(root->_right);//递归判断左右子树
}

5.完整代码 

 AVL.h：

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;//右子树高度-左子树高度,只有孩子发生变化，bf才有可能发生变化！！！！，若改变父亲，bf不变！！！！！！AVLtreenode(const pair<K, V>& _kv):_left(nullptr),_right(nullptr),_parent(nullptr),kv(_kv),bf(0){}
};template<class K, class V>
class AVLtree
{
public:typedef AVLtreenode<K, V> node;bool insert(const pair<K,V>& _kv){if (root == nullptr){root = new node(_kv);return true;}node* parent = nullptr; //比bst多了一个parentnode* cur = root;       //while (cur){parent = cur;if (cur->kv.first < _kv.first){cur = cur->_right;}else if (cur->kv.first > _kv.first){cur = cur->_left;}else{return false;}}cur = new node(_kv);if (parent->kv.first < _kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//开始调整//调整平衡因子while (cur != root){if (cur == parent->_left)parent->bf--;//第一次！！！检查parent左边原来必为空else {parent->bf++;//第一次！！！检查parent右边原来必为空}if (parent->bf == 0) //相当于bf没改变，可直接退出{break;}else if (parent->bf == 1 || parent->bf == -1) //bf改变了继续向上找   {cur = parent;parent = parent->_parent;}else if(parent->bf == -2 || parent->bf == 2){          //-2||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;//1次旋转完成后不需要再调整了}}return true;}void rotateL(node* parent)//左旋，（新节点插入到较高右子树的右侧）//   1.右右{node* subr = parent->_right;node* subrl = subr->_left;parent->_right = subrl;subr->_left= parent;node* ppnode = parent->_parent;parent->_parent = subr;if (subrl) //subrl可能为空！！！！！！！{subrl->_parent = parent;}if (parent == root) //即如果parent->_parent==nullptr{root = subr;subr->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subr;}else if (ppnode->_right == parent){ppnode->_right = subr;}subr->_parent = ppnode;}parent->bf = subr->bf = 0;   //重置平衡因子}void rotateR(node* parent)//右旋，（新节点插入到较高左子树的左侧）//   2.左左{node* subl = parent->_left;node* sublr = subl->_right;parent->_left = sublr;if (sublr)               //sublr可能为空！！！！！！！sublr->_parent = parent;node* ppnode = parent->_parent;subl->_right = parent;parent->_parent=subl;if (root == parent){root = subl;subl->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subl;}else if (ppnode->_right == parent){ppnode->_right = subl;}subl->_parent = ppnode;}subl->bf = parent->bf = 0;}void rotateRL(node* parent)   //右旋一次，再左旋一次，还需要根据不同的_bf更新平衡因子{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 = 0;subr->bf = 1;subrl->bf = 0;}else if (_bf == 1){   //subrl的左子树新增parent->bf = -1;subr->bf = 0;subrl->bf = 0;}}void rotateLR(node* parent)//左旋一次，再右旋一次，还需要根据不同的_bf更新平衡因子{node* subl = parent->_left;node* sublr= subl->_right;int _bf = sublr->bf;rotateL(parent->_left);rotateR(parent);if (_bf == 0){//sublr自己就是新增加的节点parent->bf = subl->bf = sublr->bf = 0;}else if (_bf == 1){//sublr的右子树新增parent->bf = 0;subl->bf = -1;sublr->bf = 0;}else if (_bf == -1){//sublr的左子树新增parent->bf = 1;subl->bf = 0;sublr->bf = 0;}}void inorder(){_inorder(root);}void _inorder(node* root){if (root == nullptr)return;_inorder(root->_left);cout << root->kv.first << " ";_inorder(root->_right);}int _height(node* root){if (root == nullptr)return 0;int lh = _height(root->_left);int rh = _height(root->_right);return lh > rh ? lh + 1 : rh + 1;}bool isbalance(){return _isbalance(root);}bool _isbalance(node* root){if (root == nullptr)return true;int lh = _height(root->_left);int rh = _height(root->_right);if ((rh - lh) !=root->bf){cout << "异常" << endl;return false;}return (rh - lh) <2 && (rh - lh)>-2 && _isbalance(root->_left) && _isbalance(root->_right);}private:node* root = nullptr;
};

test.c:

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<map>using namespace std;#include"AVL.h"int main()
{int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };//int arr[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };AVLtree<int, int> it;for (auto i : arr){it.insert(make_pair(i,i));}it.inorder();cout << endl<<it.isbalance() << endl;return 0;
}

6.AVL树的性能

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

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

数据结构之图的遍历

数据结构之图的遍历

文章目录 广度优先遍历深度优先遍历 广度优先遍历 广度优先遍历过程类似于二叉树的层序遍历&#xff0c;从起始顶点开始一层一层向外进行遍历 比如现在要找东西&#xff0c;假设有三个抽屉&#xff0c;东西在那个抽屉不清楚&#xff0c;现在要将其找到&#xff0c;广度优先遍历…
阅读更多...
【FFT】信号处理——快速傅里叶变换【通俗易懂】

【FFT】信号处理——快速傅里叶变换【通俗易懂】

快速傅里叶变换&#xff08;Fast Fourier Transform, FFT&#xff09;是一种用于将信号从时间域转换到频率域的算法。 傅里叶变换的核心思想是&#xff1a;任何周期性信号都可以分解成多个不同频率的正弦波或余弦波的叠加。 简单来说&#xff0c;FFT可以帮助我们理解一个信号…
阅读更多...
鲲鹏计算这五年：硬生态基本盘稳住，才能放手进击软生态

鲲鹏计算这五年：硬生态基本盘稳住，才能放手进击软生态

文 | 智能相对论 作者 | 叶远风 数智化深入发展、新质生产力成为主旋律的当下&#xff0c;本土计算产业的发展被寄予越来越多的关注和期待。自2019年开启以来&#xff0c;鲲鹏计算产业生态已经整整走过5个年头。 因此&#xff0c;今年华为全联接大会的鲲鹏之夜&#xff0c;在…
阅读更多...
大模型价格战，打到了负毛利，卷or不卷？

大模型价格战，打到了负毛利，卷or不卷？

国产大模型淘汰赛在加速。这轮淘汰赛会持续一两年&#xff0c;只有少数真正具备实力的基础模型企业能继续活下去 中国市场的大模型价格战已经打了近半年。这轮价格战已经打到了负毛利&#xff0c;而且暂时没有停止迹象。头部云厂商仍在酝酿新一轮降价。这轮降价会在今年9月下旬…
阅读更多...
【初阶数据结构】详解二叉树 - 树和二叉树（三）（递归的魅力时刻）

【初阶数据结构】详解二叉树 - 树和二叉树（三）（递归的魅力时刻）

文章目录 前言1. 二叉树链式结构的意义2. 手搓一棵二叉树3. 二叉树的遍历&#xff08;重要&#xff09;3.1 遍历的规则3.2 先序遍历3.3 中序遍历3.4 后序遍历3.5 遍历的代码实现3.5.1 先序遍历代码实现3.5.2 中序遍历代码实现3.5.3 后序遍历代码实现 4. 统计二叉树结点的个数5.…
阅读更多...
【iOS】MVC架构模式

【iOS】MVC架构模式

文章目录 前言MVC架构模式基本概念通信方式简单应用 总结 前言 “MVC”&#xff0c;即Model&#xff08;模型&#xff09;&#xff0c;View&#xff08;视图&#xff09;&#xff0c;Controller&#xff08;控制器&#xff09;,MVC模式是架构模式的一种。 关于“架构模式”&a…
阅读更多...
828华为云征文｜华为云Flexus X实例docker部署最新Appsmith社区版，搭建自己的低代码平台

828华为云征文｜华为云Flexus X实例docker部署最新Appsmith社区版，搭建自己的低代码平台

828华为云征文&#xff5c;华为云Flexus X实例docker部署最新Appsmith社区版&#xff0c;搭建自己的低代码平台 华为云最近正在举办828 B2B企业节&#xff0c;Flexus X实例的促销力度非常大&#xff0c;特别适合那些对算力性能有高要求的小伙伴。如果你有自建MySQL、Redis、Ng…
阅读更多...
Apache Hudi现代数据湖核心技术概论

Apache Hudi现代数据湖核心技术概论

1. 什么是 Apache Hudi 1.1 简介 Apache Hudi (Hadoop Upserts Deletes and Incrementals) 是一个开源的数据湖框架&#xff0c;旨在提供高效的数据管理和数据更新功能。它允许在大数据平台上执行诸如数据插入、更新和删除操作&#xff0c;同时支持增量式数据处理。Hudi 最初…
阅读更多...
C++之STL—vector容器基础篇

C++之STL—vector容器基础篇

头文件 #include <vector> //vector容器 #include <algorithm> //算法 基本用法&&概念 vector<int> v; v.push_back(10); vector<int >::iterator v.begin(); v.end(); 三种遍历方式 #include <vector> #include <algorithm>…
阅读更多...
C++基础知识7 list

C++基础知识7 list

list 1. list的介绍及使用1.1 list的介绍1.2 list的使用1.2.1 list的构造1.2.2 list iterator的使用1.2.3 list capacity1.2.4 list element access1.2.5 list modifiers1.2.6 list的迭代器失效 2.1 模拟实现list 1. list的介绍及使用 1.1 list的介绍 1.2 list的使用 1.2.1 l…
阅读更多...
51.字符串比较实例-用户登录

51.字符串比较实例-用户登录

//已知正确的用户名和密码&#xff0c;请用程序实现模拟用户登录 //总共三次机会&#xff0c;登录之后给出相应的提示 import java.util.Scanner;public class 登录 {public static void main(String[] args) {//1.定义两个变量&#xff0c;记录正确的用户名和密码String righ…
阅读更多...
操作系统迁移(CentOs -＞ Ubuntu)

操作系统迁移(CentOs -＞ Ubuntu)

目录 1. CentOs操作系统:备份数据 1.1 gitee备份 1.1.1 CentOs安装git 1.1.1.1 运行安装命令 1.1.1.2 运行安装命令时出错 1.1.1.3 再次执行安装命令 1.1.2 gitee创建仓库 1.1.2.1 创建仓库 1.1.3 备份 1.1.3.1 复制链接 1.1.3.2 克隆仓库 1.1.3.3 备份 1.3.3.4 查…
阅读更多...
uniapp小程序持续获取用户位置信息，后台位置获取

uniapp小程序持续获取用户位置信息，后台位置获取

做一个小程序持续获取用户位置信息的功能&#xff0c;即使小程序切换到后台也能继续获取&#xff0c;getLocation这个api只有小程序在前台才能获取位置&#xff0c;所以不用这个 先申请一个腾讯地图key 在uniapp项目配置源码视图里加上这个代码 先获取权限&#xff0c;再开启…
阅读更多...
ERNIESpeed-128K在线智能聊天机器人项目（附源码）

ERNIESpeed-128K在线智能聊天机器人项目（附源码）

本项目是基于百度千帆的智能聊天模型ERNIESpeed-128K开发的 一、技术栈 后端&#xff1a;java8springboot2.6.13 数据库&#xff1a;MongoDB 前端&#xff1a;vue2element-uimarked&#xff08;md格式&#xff09; 二、MongoDB与对话存储的设计 使用MongoDB来储存对话&am…
阅读更多...
【Linux】常用指令（下）（内含more、less、 head、tail、date、find、grep、zip、tar以及学习笔记）

【Linux】常用指令（下）（内含more、less、 head、tail、date、find、grep、zip、tar以及学习笔记）

文章目录 前言1. more指令2. less指令&#xff08;重要&#xff09;3. head指令4. tail指令5. 管道&#xff08;做到学会使用即可&#xff09;6. date指令6.1 时间戳 7. cal指令8. find指令9. grep指令10. zip/unzip指令11. tar指令 前言 Linux下的常用指令终于要在本文落下帷…
阅读更多...
kitti2bag原始数据转为bag包工具使用、SLAM精度评估工具evo安装及使用、KITTI原始数据集对应关系

kitti2bag原始数据转为bag包工具使用、SLAM精度评估工具evo安装及使用、KITTI原始数据集对应关系

最近在学习SLAM&#xff0c;需要使用到精度评估工具evo&#xff0c;写下这篇笔记记录自己暂时使用到的命令&#xff0c;在此只做一个记录&#xff0c;后续学习过程中需要使用新命令会逐渐追加上去。 目录 evo的安装 evo的使用 Kitti序列00-10对应关系 kitti2bag工具包安装…
阅读更多...
docker部署Stirling-PDF

docker部署Stirling-PDF

github网址&#xff1a; GitHub - Stirling-Tools/Stirling-PDF: #1 Locally hosted web application that allows you to perform various operations on PDF files 1、官方docker镜像无法拉取&#xff0c;使用别人阿里云私人镜像仓库下载Stirling-PDF镜像&#xff1a; dock…
阅读更多...
Maven-四、继承

Maven-四、继承

Maven进阶 文章目录 Maven进阶前言继承设置继承依赖管理总结 前言 一个项目中的不同模块可能引用的是同一个依赖&#xff0c;在这种情况下&#xff0c;单独在某个模块内引用太麻烦&#xff0c;于是maven使用继承的思想&#xff0c;在父模块中配置依赖包&#xff0c;其他需要这…
阅读更多...
IDEA连接数据库报错：Access denied for user ****

IDEA连接数据库报错：Access denied for user ****

使用IDEA开发时&#xff0c;通过Databse连接数据库。多次连接报错&#xff1a;Access denied for user **** 如下所示&#xff1a; ​ ‍ ‍ ​ ‍ 花了不少时间排查&#xff0c;确认账号、密码&#xff0c;后面发现账号后多了个空格&#xff0c;而且不容易发现&#xf…
阅读更多...
Excel的基本应用 ___2

Excel的基本应用 ___2

快速插入函数 方法一&#xff1a; 方法二&#xff1a;快捷键 Alt&#xff1a;求和 动态查看 利用函数清单选择函数 相对地址和绝对地址的转换 FnF4
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023