数据结构——“AVL树”的四种数据旋转的方法

        因为上次普通的二叉搜索树在极端情况下极容易造成我们的链式结构（这会导致我们查询的时间复杂度变为O(n)），然而AVL树就很好的解决了这一问题（归功于四种旋转的方法），它让我们的树的查询的时间复杂度变得接近于甚至等于O(logN)。它相比于普通的二叉搜索树，它增加了平衡因子来维持树的高度，增加了纸箱上一个节点的parent指针。另外，平衡因子的计算方法是右子树的高度减去左子树的高度，当当前节点的平衡因子的值为-1、0、1的时候，我们认为当前节点是平衡的，当为其他值的时候就不平衡，需要通过旋转来将树调整平衡。

        废话不多说，让我们了解一下四种旋转方式吧。

        一、右旋

        右旋的情况（最小）出现在一直向左子树插入数据，就像这样：

        最后插入的6让10的平衡因子变为-2，让本就不怎么平衡的数变得彻底不平衡，因此就需要右旋。它的规则是什么呢？

        当树满足右旋的条件的时候（当前节点的平衡因子为2或者-2），右旋的时候，平衡因子为-2，在这里满足条件的是10节点，我们把它的左子树的右子树给该节点的左子树，即：用节点10替换掉8的右子树，但是8的右子树是有东西的，而10的左子树刚好又不指向8，那么就进行互换一次。

        最后再次修改平衡因子：

        下边可以看一个实例：

        这是一棵已经满足AVL树的树：

        在5的左子树插入数据：

     节点更新带6，不满足条件，需要旋转：

                更新平衡因子：

        用过重复的测试和观察可以发现，到最后，旋转的节点和他的左子树最后的平衡因子都是从-2、-1变到0、0.

        值得注意的是在插入节点后，需要向上更新平衡因子，倘若更新后遇到平衡因子为0，那就没有再次向上更新的必要了。

插入代码结构如下：

	//AVL树的插入bool Insert(K key){Node* cur = _root;Node* parent = nullptr;//插入数据if (cur == nullptr){_root = new Node(key);}else{//寻找插入的位置while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{return false;}}//插入cur = new Node(key);if (key > parent->_key)//插入的值大于父亲节点，那么就需要在父亲节点的右边插入{parent->_right = cur;parent->_right->_parent = parent;}else if(key < parent->_key)//插入的值小于父亲节点，那么就需要在父亲节点的左边插入{parent->_left = cur;parent->_left->_parent = parent;}else{assert(false);}}//更新平衡因子while (parent){if (cur == parent->_left){parent->_bl--;}else if (cur == parent->_right){parent->_bl++;}//检查树是否平衡if (parent->_bl == 0)//平衡，退出函数{return true;}else if (parent->_bl == 1 || parent->_bl == -1)//半平衡，向上更新,直到为0或者更新到根{cur = parent;parent = parent->_parent;}else if (parent->_bl == 2 || parent->_bl == -2)//不平衡，旋转{这里是四种旋转的区域return true;}else{assert(false);}}return true;}

        那么知道原理后，就来用代码实现以下：

	//右旋void RotateR(Node* node){Node* kidL = node->_left;Node* kidLR = node->_left->_right;Node* pparent = node->_parent;//先把该节点移动到kidl的右边node->_left = kidLR;if (kidLR)//只有在kidLR不为空的情况下才可以更新kidLR的父亲节点{kidLR->_parent = node;}kidL->_right = node;node->_parent = kidL;if (pparent == nullptr)//如果被旋转节点的父亲为空，则说明此节点为根节点{_root = kidL;kidL->_parent = nullptr;}else//不为根节点{if (node == pparent->_left)//判断被旋转的节点在父亲节点的左边还是右边{pparent->_left = kidL;}else{pparent->_right = kidL;}kidL->_parent = pparent;}kidL->_bl = node->_bl = 0;//更新平衡因子}

        在写代码的过程中，为了防止出错，建议把需要更改的节点的位置用指针记录下来，一方面是为了防止在写代码的过程中因为误操作修改了指针的指向，导致再次使用的时候因为指针的变化从而操作本不应该操作的节点，另一方面是优化代码可读性，毕竟连续的“->”会让人感觉头疼。

看看示例：

int main()
{AVLTree<int> tree;tree.Insert(10);tree.Insert(8);tree.Insert(7);tree.Insert(6);tree.Insert(5);tree.Insert(4);tree.InTraversal();return 0;
}

         运行结果（中序遍历）：

二、左旋

        左旋和右旋一样，它的发生情况是这种的：

        它和右旋一样，不过是方向相反的，我们需要把13的左边给10的右边，然后把10给13的左边，做后需要注意的细节和右旋一样，就是父亲节点的更新。这一点需要大家画图研究一下。

        另外，经过观察可以得到，左旋的条件是被旋转的节点平衡因子为2，它的右子树的平衡因子为1。

        由于和右旋相反，所以可以在右旋代码中做修改（几乎所有的被改数值都和右旋相反）：

//左旋void RotateL(Node* node){Node* kidR = node->_right;Node* kidRL = node->_right->_left;Node* pparent = node->_parent;//先把该节点移动到kidl的左边node->_right = kidRL;if (kidRL)//只有在kidRL不为空的情况下才可以更新kidRL的父亲节点{kidRL->_parent = node;}kidR->_left = node;node->_parent = kidR;if (pparent == nullptr)//如果被旋转节点的父亲为空，则说明此节点为根节点{_root = kidR;kidR->_parent = nullptr;}else//不为根节点{if (node == pparent->_left)//判断被旋转的节点在父亲节点的左边还是右边{pparent->_left = kidR;}else{pparent->_right = kidR;}kidR->_parent = pparent;}kidR->_bl = node->_bl = 0;//更新平衡因子}

示例：

int main()
{AVLTree<int> tree;tree.Insert(1);tree.Insert(2);tree.Insert(3);tree.Insert(4);tree.Insert(5);tree.Insert(6);tree.InTraversal();return 0;
}

 运行结果：

三、左右双旋

        左右双旋的情况（最小）大致是这样：

        这种情况比较复杂，但是解决方法就是先对5进行左旋，再对10进行右旋，对5左旋是为了把这棵树变为纯粹的左边高（旋转后满足右旋的条件），然后再进行右旋。

        在这里有一个值得注意的问题：被调整的节点的左子树的右子树的高度会影响被调整的节点的左子树或者被调整的节点的平衡因子，举个例子：

        1.上边的例子是8的平衡因子为0的情况，那么最后parent（10）和kid（5）的平衡因子为0。

        2.当8的平衡因子为1的时候（框里的代表能够满足左右双旋的情况）影响的是被调整的节点的左子树的平衡因子，即5的平衡因子

       a.在8节点右边插入节点：

旋转：

        最后5的节点的平衡因子为-1，10的节点的平衡因子为0。

        b. a.在8节点左边插入节点：

最后5的节点的平衡因子为0，10的节点的平衡因子为1。

        另外通过观察可得被旋转的节点的平衡因子为-2，它的左子树平衡因子为1的时候，发生左右旋转。

代码如下：

	//左右双旋void RotateLR(Node* node){Node* kidL = node->_left;Node* kidLR = node->_left->_right;int bl = kidLR->_bl;//先对左边的节点进行左旋RotateL(kidL);//再对该节点进行右旋RotateR(node);if (bl == 0){node->_bl = kidL->_bl = kidLR->_bl = 0;}else if (bl == 1){kidL->_bl = -1;node->_bl = kidLR->_bl = 0;}else if (bl == -1){node->_bl = 1;kidL->_bl = kidLR->_bl = 0;}}

测试示例：

int main()
{AVLTree<int> tree;tree.Insert(10);tree.Insert(5);tree.Insert(11);tree.Insert(4);tree.Insert(8);tree.Insert(9);tree.InTraversal();return 0;
}

运行结果：

四、右左双旋

        同左旋和右旋的关系，他们只是方向相反，能更改的东西也应该相反，它的形成条件如下图：

代码：

	//右左双旋void RotateRL(Node* node){Node* kidR = node->_right;Node* kidRL = kidR->_left;int bl = kidRL->_bl;//先对右边的节点进行右旋RotateR(kidR);//再对该节点进行左旋RotateL(node);if (bl == 0){node->_bl = kidR->_bl = kidRL->_bl = 0;}else if (bl == 1){node->_bl = -1;kidR->_bl = kidRL->_bl = 0;}else if (bl == -1){kidR->_bl = 1;node->_bl = kidRL->_bl = 0;}else{return assert(false);}}

示例：

int main()
{AVLTree<int> tree;tree.Insert(10);tree.Insert(9);tree.Insert(15);tree.Insert(11);tree.Insert(16);tree.Insert(12);tree.Insert(13);tree.InTraversal();return 0;
}

总代码：


#include<iostream>
#include<assert.h>using namespace std;template <class K>
struct AVLTreenode
{AVLTreenode(K key):_key(key){}K _key;AVLTreenode* _left = nullptr;AVLTreenode* _right = nullptr;AVLTreenode* _parent = nullptr;int _bl = 0;
};template <class K>
class AVLTree
{
private:using Node = AVLTreenode<K>;Node* _root = nullptr;
public:void _InTraversal(Node* p){if (p == nullptr)return;_InTraversal(p->_left);cout << p->_key << " ";_InTraversal(p->_right);}//搜索树的中序遍历void InTraversal(){_InTraversal(_root);}//搜索树的查找Node* Find(const K& key){assert(_root);Node* cur = _root;while (cur){if (cur->_key > key){cur = cur->_left;}else if (cur->_key < key){cur = cur->_right;}else{return cur;}}return nullptr;}//AVL树的插入bool Insert(K key){Node* cur = _root;Node* parent = nullptr;//插入数据if (cur == nullptr){_root = new Node(key);}else{//寻找插入的位置while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{return false;}}//插入cur = new Node(key);if (key > parent->_key)//插入的值大于父亲节点，那么就需要在父亲节点的右边插入{parent->_right = cur;parent->_right->_parent = parent;}else if(key < parent->_key)//插入的值小于父亲节点，那么就需要在父亲节点的左边插入{parent->_left = cur;parent->_left->_parent = parent;}else{assert(false);}}//更新平衡因子while (parent){if (cur == parent->_left){parent->_bl--;}else if (cur == parent->_right){parent->_bl++;}//检查树是否平衡if (parent->_bl == 0)//平衡，退出函数{return true;}else if (parent->_bl == 1 || parent->_bl == -1)//半平衡，向上更新,直到为0或者更新到根{cur = parent;parent = parent->_parent;}else if (parent->_bl == 2 || parent->_bl == -2)//不平衡，旋转{if (parent->_bl == -2 && parent->_left->_bl == -1)//右旋{RotateR(parent);}else if (parent->_bl == 2 && parent->_right->_bl == 1)//左旋{RotateL(parent);}else if (parent->_bl == -2 && parent->_left->_bl == 1)//左右双旋{RotateLR(parent);}else if (parent->_bl == 2 && parent->_right->_bl == -1)//右左双旋{RotateRL(parent);}return true;}else{assert(false);}}return true;}//右旋void RotateR(Node* node){Node* kidL = node->_left;Node* kidLR = node->_left->_right;Node* pparent = node->_parent;//先把该节点移动到kidl的右边node->_left = kidLR;if (kidLR)//只有在kidLR不为空的情况下才可以更新kidLR的父亲节点{kidLR->_parent = node;}kidL->_right = node;node->_parent = kidL;if (pparent == nullptr)//如果被旋转节点的父亲为空，则说明此节点为根节点{_root = kidL;kidL->_parent = nullptr;}else//不为根节点{if (node == pparent->_left)//判断被旋转的节点在父亲节点的左边还是右边{pparent->_left = kidL;}else{pparent->_right = kidL;}kidL->_parent = pparent;}kidL->_bl = node->_bl = 0;//更新平衡因子}//左旋void RotateL(Node* node){Node* kidR = node->_right;Node* kidRL = node->_right->_left;Node* pparent = node->_parent;//先把该节点移动到kidl的左边node->_right = kidRL;if (kidRL)//只有在kidRL不为空的情况下才可以更新kidRL的父亲节点{kidRL->_parent = node;}kidR->_left = node;node->_parent = kidR;if (pparent == nullptr)//如果被旋转节点的父亲为空，则说明此节点为根节点{_root = kidR;kidR->_parent = nullptr;}else//不为根节点{if (node == pparent->_left)//判断被旋转的节点在父亲节点的左边还是右边{pparent->_left = kidR;}else{pparent->_right = kidR;}kidR->_parent = pparent;}kidR->_bl = node->_bl = 0;//更新平衡因子}//左右双旋void RotateLR(Node* node){Node* kidL = node->_left;Node* kidLR = node->_left->_right;int bl = kidLR->_bl;//先对左边的节点进行左旋RotateL(kidL);//再对该节点进行右旋RotateR(node);if (bl == 0){node->_bl = kidL->_bl = kidLR->_bl = 0;}else if (bl == 1){kidL->_bl = -1;node->_bl = kidLR->_bl = 0;}else if (bl == -1){node->_bl = 1;kidL->_bl = kidLR->_bl = 0;}else{return assert(false);}}//右左双旋void RotateRL(Node* node){Node* kidR = node->_right;Node* kidRL = kidR->_left;int bl = kidRL->_bl;//先对右边的节点进行右旋RotateR(kidR);//再对该节点进行左旋RotateL(node);if (bl == 0){node->_bl = kidR->_bl = kidRL->_bl = 0;}else if (bl == 1){node->_bl = -1;kidR->_bl = kidRL->_bl = 0;}else if (bl == -1){kidR->_bl = 1;node->_bl = kidRL->_bl = 0;}else{return assert(false);}}};

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

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

QT--基础

QT--基础

将默认提供的程序都注释上意义 0101.pro QT core gui #QT表示要引入的类库 core&#xff1a;核心库 gui&#xff1a;图形化界面库 #如果要使用其他库类中的相关函数&#xff0c;则需要加对应的库类后&#xff0c;才能使用 greaterThan(QT_MAJOR_VERSION, 4): QT wid…
阅读更多...
关于frp Web界面-----frp Server Dashboard 和 frp Client Admin UI

关于frp Web界面-----frp Server Dashboard 和 frp Client Admin UI

Web 界面 官方文档&#xff1a;https://gofrp.org/zh-cn/docs/features/common/ui/ 目前 frpc 和 frps 分别内置了相应的 Web 界面方便用户使用。 客户端 Admin UI 服务端 Dashboard 服务端 Dashboard 服务端 Dashboard 使用户可以通过浏览器查看 frp 的状态以及代理统计信…
阅读更多...
GD32片内flash读写数据

GD32片内flash读写数据

如有技术问题及技术需求请加作者微信！ GD32片内Flash的读写数据是微控制器编程中的常见任务，主要用于存储程序代码、配置参数或用户数据等。以下将详细介绍GD32片内Flash的读写数据方法和程序。 一、GD32 Flash的基本特性 存储空间划分：GD32的Flash存储空间通常分为主存储块…
阅读更多...
罕见 P0 故障！上交所崩了 ~

罕见 P0 故障！上交所崩了 ~

大家好啊&#xff0c;我是董董灿。 昨天&#xff08;9月27号&#xff09;很多朋友可能都刷到一个消息&#xff1a;上交所崩了。 原因是在近期经济政策的刺激下&#xff0c;我大A股市场出现反弹&#xff0c;很多投资者纷纷涌入大A进行交易。 A 股反弹本来是件好事&#xff0c…
阅读更多...
常见网络服务搭建之SSH服务搭建

常见网络服务搭建之SSH服务搭建

SSH为Secure Shell的缩写&#xff0c;由IETF的网络小组&#xff08;Network Working Group&#xff09;所制定的建立在应用层基础上的安全协议。SSH是较可靠&#xff0c;专为远程登录会话和其他网络服务提供安全性的协议&#xff0c;利用SSH协议可以有效防止远程管理过程中的信…
阅读更多...
计算机毕业设计 招生宣传管理系统的设计与实现 Java实战项目 附源码+文档+视频讲解

计算机毕业设计 招生宣传管理系统的设计与实现 Java实战项目 附源码+文档+视频讲解

博主介绍&#xff1a;✌从事软件开发10年之余&#xff0c;专注于Java技术领域、Python人工智能及数据挖掘、小程序项目开发和Android项目开发等。CSDN、掘金、华为云、InfoQ、阿里云等平台优质作者✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精…
阅读更多...
代码随想录算法训练营第十七天|654.最大二叉树 617.合并二叉树 700.二叉搜索树中的搜索 98.验证二叉搜索树

代码随想录算法训练营第十七天|654.最大二叉树 617.合并二叉树 700.二叉搜索树中的搜索 98.验证二叉搜索树

654.最大二叉树 给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下&#xff1a; 二叉树的根是数组中的最大元素。左子树是通过数组中最大值左边部分构造出的最大二叉树。右子树是通过数组中最大值右边部分构造出的最大二叉树。 通过给定的数组构建最大二…
阅读更多...
番外篇 | 复现AC-YOLOv5，进行自动化织物缺陷检测

番外篇 | 复现AC-YOLOv5，进行自动化织物缺陷检测

前言：Hello大家好，我是小哥谈。我们提出了一种基于AC-YOLOv5的新型纺织缺陷检测方法。将空洞空间金字塔池化（ASPP）模块引入YOLOv5主干网络中，提出了squeeze-and-excitation（CSE）通道注意力模块，并将其引入到YOLOv5主干网络中。🌈 目录 🚀1.基础概念 🚀2.添…
阅读更多...
Chrome浏览器如何修改语言（修改成英文、中文）

Chrome浏览器如何修改语言（修改成英文、中文）

一、背景 有的时候需要修改chrome浏览器的语言&#xff0c;比如如下是中文&#xff0c;我要修改成英文 二、下面的方法已经无效了 在语言里添加"英语"并且置顶&#xff0c;试了很久&#xff0c;设置完后重启浏览器什么的&#xff0c;都无法改成英文。 这个可能…
阅读更多...
ECMAScript 与 JavaScript 的区别详解

ECMAScript 与 JavaScript 的区别详解

ECMAScript 与 JavaScript 的区别详解 在前端开发的学习过程中&#xff0c;很多开发者会遇到两个常见的术语&#xff1a;ECMAScript 和 JavaScript。这两个术语常常被混淆&#xff0c;因为它们密切相关&#xff0c;甚至有时被认为是同一件事。本文将详细解析 ECMAScript 和 Ja…
阅读更多...
青动CRM V3.2.1

青动CRM V3.2.1

全面解决企业销售团队的全流程客户服务难题旨在助力企业销售全流程精细化、数字化管理&#xff0c;全面解决企业销售团队的全流程客户服务难题&#xff0c;帮助企业有效盘活客户资源、量化销售行为&#xff0c;合理配置资源、建立科学销售体系&#xff0c;提升销售业绩。标准授…
阅读更多...
【面试题】软件测试实习（含答案）

【面试题】软件测试实习（含答案）

软件测试实习常见面试题&#xff0c;主要是功能测试相关的基础问题 目录 一、软件测试基础 1、介绍一下你最近的项目&#xff0c;以及工作职责 2、软件项目的测试流程? 3、黑盒测试与白盒测试的区别? 4、黑盒测试常见的设计方法?怎么理解等价类方法和边界值方法 1&…
阅读更多...
言语理解(2)

言语理解(2)

B B出现在文章中的第一句话&#xff0c;属于转折前的内容非重点 在这一过程中&#xff0c;属于对前面的指代&#xff0c;后面可以引出文章中的中心内容 A D没有提及到农村&#xff0c;C选项和文段中的最后一句话是相契合的 B 色彩是文章中的主题词&#xff0c;不过属于转折&…
阅读更多...
SpringBoot搭建

SpringBoot搭建

第一种创建方式 第二种创建方式 第三种创建 第四种手动创建 最后把controller写好
阅读更多...
解决Windows远程桌面 “为安全考虑,已锁定该用户账户,原因是登录尝试或密码更改尝试过多,请稍后片刻再重试,或与系统管理员或技术支持联系“问题

解决Windows远程桌面 “为安全考虑,已锁定该用户账户,原因是登录尝试或密码更改尝试过多,请稍后片刻再重试,或与系统管理员或技术支持联系“问题

根本原因就是当前主机被通过远程桌面输入了过多的错误密码&#xff0c;被系统锁定。这种情况多数是你的服务器远程桌面被人试图攻击了&#xff0c;不建议取消系统锁定策略。如果阿里云或者腾讯云主机&#xff0c;只需要在管理后台通过管理终端或者VNC登陆一次&#xff0c;锁定即…
阅读更多...
RTA-OS Port Guide学习(三)-基于S32K324 OS

RTA-OS Port Guide学习(三)-基于S32K324 OS

文章目录 前言HardwareSupported DevicesRegister UsageInitializationModificationRequired OS resourcesInterruptsInterrupt Priority LevelsAllocation of ISRs to Interrupt VectorsVector TableWriting Category 1 Interrupt HandlersWriting Category 2 Interrupt Handl…
阅读更多...
【Echarts】折线图和柱状图如何从后端动态获取数据？

【Echarts】折线图和柱状图如何从后端动态获取数据？

&#x1f680;个人主页&#xff1a;一颗小谷粒 &#x1f680;所属专栏&#xff1a;Web前端开发 很荣幸您能阅读我的文章&#xff0c;诚请评论指点&#xff0c;欢迎欢迎 ~ 目录 1.1 前端数据分析 1.2 数据库表分析 1.3 后端数据处理 1.4 前端接收数据 继上一篇文章&…
阅读更多...
Linux入门2——初识Linux权限

Linux入门2——初识Linux权限

目录 0. Linux下的用户 1.文件访问者的分类 2.文件类型和访问权限 3. 文件权限值的表示方法 4.文件访问权限的相关设置方法 4.1 修改文件的访问权限 4.2修改文件的拥有者和所属组 0. Linux下的用户 在学习Linux权限之前&#xff0c;我们要先来了解Linux下的用户&#x…
阅读更多...
【文心智能体 | AI大师工坊】如何使用智能体插件，完成一款旅游类智能体的开发，来体验一下我的智能体『​​​​​​​厦门CityWalk』

【文心智能体 | AI大师工坊】如何使用智能体插件，完成一款旅游类智能体的开发，来体验一下我的智能体『​​​​​​​厦门CityWalk』

目录 1.1、智能体运行效果 1.2、创作灵感来源 1.3、如何制作智能体 1.4、可能会遇到的几个问题 1.5、快速调优指南 『厦门CityWalk&#x1f680;』我的优质智能体&#xff1a;https://0nxj3k.smartapps.baidu.com/?_swebfr1&_swebScene3621000000000000 在当今这个全…
阅读更多...
智慧水利综合解决方案

智慧水利综合解决方案

1. 智慧水利综合解决方案概述 智慧水利综合解决方案旨在通过集成先进技术&#xff0c;实现水利管理的智能化和高效化。该方案涵盖平台建设、业务系统建设和系统集成服务三大应用场景&#xff0c;通过数字孪生、GIS平台开发等技术手段&#xff0c;全面提升水利行业的管理能力和…
阅读更多...
最新文章

Copyright @ 2022~2023