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

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

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

        一、右旋

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

74ce36d1ae1f4d979c9a088dc67ff7e3.png

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

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

bfadcfd6dd8c452e9768a90fd199efdd.png

        最后再次修改平衡因子：

9b934bd33f1349188b78e01a8e0b1f02.png

        下边可以看一个实例：

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

7538a8530da84cac9b16c9e95287f0a6.png

        在5的左子树插入数据：

96dc88a2bbb643ecbd06baafe1ae852c.png

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

69f3fd583c5e4de4b93e21e5cf13772d.png

                更新平衡因子：

668e0d3c75a44053bf03d2cbde021f44.png

        用过重复的测试和观察可以发现，到最后，旋转的节点和他的左子树最后的平衡因子都是从-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;
}

         运行结果（中序遍历）：

41eced73b97f4715a0811f5548124d69.png

二、左旋

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

896a1d48783b432983479a923fae9791.png

        它和右旋一样，不过是方向相反的，我们需要把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;
}

 运行结果：

3be2c82787664c05a876d18fa3419f27.png

三、左右双旋

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

f50f5d19c1f94745881020a13df09ce1.png

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

e34dc7bd998b4fa9b90fb46a4f7d1cb4.png

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

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

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

68a744aed5414d68adef53add42ca79d.png

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

3c2310b752364f5081f351f854a2a80e.png

旋转：

dfddb5ac533046c3ab9dd709c2b641ab.png

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

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

5853e9174b1c43328a7dffb7b31ff205.png

最后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;
}

运行结果：

25100a08c10f464683045755ccb7b9e6.png

四、右左双旋

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

57aed070786d4dfa8f1beb5697f54e4b.png

代码：

	//右左双旋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;
}

ee934faf8a2b4aef95665af1a79614cf.png

总代码：


#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.rhkb.cn/news/437375.html

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

相关文章

Dapper 如何确保数据的安全性和防止 SQL 注入攻击？

Dapper 如何确保数据的安全性和防止 SQL 注入攻击？

一、什么是SQL注入攻击 SQL注入攻击是一种常见的网络攻击手段&#xff0c;它利用了应用程序中安全措施不足的问题&#xff0c;允许攻击者插入或“注入”一个或多个SQL语句到原本的查询中。这种攻击可以用于获取、篡改或删除数据库中的数据&#xff0c;甚至可以执行一些数据库管…
阅读更多...
【web安全】——sql注入

【web安全】——sql注入

1.MySQL基础 1.1information_schema数据库详解 简介&#xff1a; 在mysql5版本以后&#xff0c;为了方便管理&#xff0c;默认定义了information_schema数据库&#xff0c;用来存储数据库元数据信息。schemata(数据库名)、tables(表名tableschema)、columns(列名或字段名)。…
阅读更多...
字节豆包C++一面-面经总结

字节豆包C++一面-面经总结

talk is cheap show me the code lc206&#xff1a;链表反转&#xff1a;给你单链表的头节点 head &#xff0c;请你反转链表&#xff0c;并返回反转后的链表。 class Solution { public:ListNode* reverseList(ListNode* head) {if(headnullptr||!head->next)return head…
阅读更多...
sentinel原理源码分析系列(二)-动态规则和transport

sentinel原理源码分析系列(二)-动态规则和transport

本文是sentinel原理源码分析系列第二篇&#xff0c;分析两个组件&#xff0c;动态配置和transport 动态规则 Sentinel提供动态规则机制&#xff0c;依赖配置中心&#xff0c;如nacos&#xff0c;zookeeper&#xff0c;组件支持动态配置&#xff0c;模板类型为规则&#xff0c;支…
阅读更多...
Qt开发技巧（九）去掉切换按钮，直接传样式文件，字体设置，QImage超强，巧用Qt的全局对象，信号槽断连，低量数据就用sqlite

Qt开发技巧（九）去掉切换按钮，直接传样式文件，字体设置，QImage超强，巧用Qt的全局对象，信号槽断连，低量数据就用sqlite

继续讲一些Qt开发中的技巧操作&#xff1a; 1.去掉切换按钮 QTabWidget选项卡有个自动生成按钮切换选项卡的机制&#xff0c;有时候不想看到这个烦人的切换按钮&#xff0c;可以设置usesScrollButtons为假&#xff0c;其实QTabWidget的usesScrollButtons属性最终是应用到QTabWi…
阅读更多...
python调用opencv报错“module ‘cv2‘ has no attribute ‘namedWindow‘”

python调用opencv报错“module ‘cv2‘ has no attribute ‘namedWindow‘”

之前电脑上使用pip install安装过opencv相关的python模块&#xff0c;不过后续学习opencv时主要使用OpenCVSharp在VS2022中创建项目测试。今天学习过程中突然想用python试试&#xff0c;不过运行下面代码时报错“module ‘cv2’ has no attribute namedWindow”。 import cv2c…
阅读更多...
巡检机器人室内配电室应用

巡检机器人室内配电室应用

智能巡检系统实施背景 电力系统发展已进入电气化、自动化、智能化建设加速推进的新阶段&#xff0c;设备规模大幅增长&#xff0c;新设备、新技术加快应用&#xff0c;装备水平取得长足发展&#xff0c;与此同时设备规模大幅增长&#xff0c;新设备、新技术加快应用&#xff0…
阅读更多...
神经网络介绍及其在Python中的应用（一）

神经网络介绍及其在Python中的应用（一）

作者简介&#xff1a;热爱数据分析&#xff0c;学习Python、Stata、SPSS等统计语言的小高同学~ 个人主页&#xff1a;小高要坚强的博客 当前专栏&#xff1a;Python之机器学习 本文内容&#xff1a;神经网络介绍及其在Python中的线性回归应用 作者“三要”格言&#xff1a;要坚…
阅读更多...
STM32（四）LED闪烁、流水灯及蜂鸣器操作

STM32（四）LED闪烁、流水灯及蜂鸣器操作

小节任务&#xff1a;在对GPIO函数初始化操作及配置好输入或输出模式后&#xff0c;使用GPIO的输入输出函数控制LED闪烁、流水灯及蜂鸣器操作&#xff0c;本小节先使用GPIO的四个输出函数 SetBits函数将指定端口设置为高电平 ResetBits函数将指定端口设置为低电平 WriteBit根据…
阅读更多...
c++进阶之多态讲解

c++进阶之多态讲解

这篇文章和大家一起学习一下c中的多态 多态的概念 多态的概念&#xff1a;通俗来讲&#xff0c;就是多种形态。多态分为编译时多态(静态多态)和运⾏时多态(动态多态)。 什么是静态多态 前⾯讲的函数重载和函数模板&#xff0c;它们传不同类型的参数就可以调用不同的函数&…
阅读更多...
Linux中的软硬链接和动静态库

Linux中的软硬链接和动静态库

硬链接 ln myfile.txt hard_file.link 264962 -rw-rw-r-- 2 zhangsan zhangsan 0 Sep 30 03:16 hard_file.link 264962 -rw-rw-r-- 2 zhangsan zhangsan 0 Sep 30 03:16 myfile.txt 273922 lrwxrwxrwx 1 zhangsan zhangsan 10 Sep 30 03:17 soft_file.link -> …
阅读更多...
Activiti7 工作流引擎学习

Activiti7 工作流引擎学习

目录 一. 什么是 Activiti 工作流引擎 二. Activiti 流程创建步骤 三. Activiti 数据库表含义 四. BPMN 建模语言 五. Activiti 使用步骤 六. 流程定义与流程实例 一. 什么是 Activiti 工作流引擎 Activiti 是一个开源的工作流引擎&#xff0c;用于业务流程管理&#xf…
阅读更多...
将给定的表达式树（二叉树）转换为等价的中缀表达式（通过括号反映操作符的计算次序）并输出

将给定的表达式树（二叉树）转换为等价的中缀表达式（通过括号反映操作符的计算次序）并输出

请设计一个算法&#xff0c;将给定的表达式树&#xff08;二叉树&#xff09;转换为等价的中缀表达式&#xff08;通过括号反映操作符的计算次序&#xff09;并输出。例如&#xff0c;当下列两棵表达式树作为算法输入时&#xff1a; 输出的中缀表达式分别为 (ab)∗(c∗(−d)) 和…
阅读更多...
推送k8s镜像到阿里云服务器

推送k8s镜像到阿里云服务器

1、服务打包 2、打包后进入Dockerfile的同级目录 运行 docker build -t 镜像名:镜像版本 . (这个点是当前目录的意思&#xff0c;不能忽略)例如 docker build -t trac:v1.0.4 .3、上传镜像到阿里云镜像服务 注意选择区域 例如&#xff1a; docker tag 70743d9bdba3 registr…
阅读更多...
[C++] 剖析AVL树功能的实现原理

[C++] 剖析AVL树功能的实现原理

文章目录 引言AVL树的关键性质为什么选择AVL树&#xff1f; AVL树的结构节点对象的类 AVL树的插入检查是否为空树并处理根节点查询插入位置&#xff08;非递归&#xff09;插入节点并连接父节点更新平衡因子&#xff08;在失去平衡的条件下进行旋转&#xff09; 旋转旋转的原则…
阅读更多...
计组复习笔记

计组复习笔记

计组笔记 汇编部分 通用寄存器&#xff08;General Registers&#xff09;: AX (Accumulator): 用于累加运算&#xff0c;也是乘法和除法的默认寄存器。BX (Base Register): 可以用作一个基址寄存器&#xff0c;通常用于存放数据的基地址。CX (Counter Register): 通常用于循环…
阅读更多...
【零散技术】Odoo PDF 打印问题问题合集

【零散技术】Odoo PDF 打印问题问题合集

序言:时间是我们最宝贵的财富,珍惜手上的每个时分 Odoo PDF打印 是一个必备功能&#xff0c;但是总会遇到一些奇奇怪怪的问题&#xff0c;此帖仅做记录&#xff0c;方便查阅。 目录 1、样式丢失 2、部分结构丢失 3、没有中文字体 1、样式丢失 这种情况一般是由于 …
阅读更多...
Redis: Sorted Set 底层算法的简单分析

Redis: Sorted Set 底层算法的简单分析

概述 我们先看下 Shorted Set 有序集合的内部数据结构所谓有序集合&#xff0c;比如有个容器&#xff0c;容器里边都已经排好序了&#xff0c;那无非就是快速的查找和插入不管你是查找还是插入&#xff0c;肯定要确定那个位置最简单的办法就是从最开头开始&#xff0c;挨个比较…
阅读更多...
查找与排序-插入排序

查找与排序-插入排序

排序算法可以分为内部排序和外部排序&#xff0c;内部排序是数据记录在内存中进行排序&#xff0c;而外部排序是因排序的数据很大&#xff0c;一次不能容纳全部的排序记录&#xff0c;在排序过程中需要访问外存。常见的内部排序算法有&#xff1a;插入排序、希尔排序、选择排序…
阅读更多...
2024年10月2日历史上的今天大事件早读

2024年10月2日历史上的今天大事件早读

1683年10月2日 清朝康熙帝统一台湾 1869年10月2日 印度民族解放运动领袖甘地诞辰 1890年10月2日 中共创始人之一李达诞生 1895年10月2日 天津中西学堂&#xff08;天津大学前身&#xff09;开学 1901年10月2日 郑士良等发起惠州起义 1909年10月2日 京张铁路正式通车 1920…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023