【STL】AVLTree模拟实现

🕗 发布于 2024-10-15 20:01 c++ STL 数据结构 AVL树

AVLTree模拟实现

1 前言
2 AVL树的插入
3 代码

1 前言

二叉搜索树的不足：如果出现极端情况，效率会变得很低。

AVL：二叉平衡搜索树
平衡因子：右子树的高度 - 左子树的高度平衡因子绝对值不超过1(-1, 0, 1)

1.平衡因子为什么不是0？而是 -1， 0 ，1？？

做不到，两个节点的时候不能相等，四个节点也做不到

AVL树的效率：
增删查改：高度次 O(log N)
满二叉树：2^h - 1 = N
AVL树：2^h - x = N
x的范围：[1, 2^(h - 1) - 1]

2 AVL树的插入

2.1 平衡因子不继续向上更新的情况

插入的原则：
新增在左：parent的平衡因子–
新增在右：parent的平衡因子++

在这里插入图片描述

从这里可以看出，当平衡因子的值为 -1 或者 1 的时候，并不会停止向上更新。
只有当平衡因子更新为0的时候，才不会继续往上更新了。

2.2 平衡因子变为2或者-2，发生旋转

在这里插入图片描述
当平衡因子的值更新为 -2或者2的时候，就代表这棵树不平衡了，就需要进行旋转。这时候更新也停止了（因为要进行旋转了）

2.什么情况要继续往上更新？（更新结束的条件）
更新后的parent平衡因子==0，说明parent所在的子树的高度不变，不会再影响祖先，不用再继续往上更新
更新后的parent平衡因子 ==1 或者 -1，说明parent所在的子树的高度发生改变，会影响祖先，要继续往上更新
更新后的parent平衡因子 ==2 或者 -2，说明parent所在的子树的高度发生改变且不平衡，想办法调整平衡（对parent所在子树进行旋转，让他平衡）
更新到根节点 --> 更新结束

2.2.1 左单旋

发生左单旋的情况：(具体图，某一种情况)
在这里插入图片描述

发生左单旋的抽象图(有很多种情况)：
在这里插入图片描述

什么情况会发生左单旋？

在右边高的情况下往右边插入。

转化成代码就是：在插入之后，parent->_bf = 2 && cur->_bf = 1.这里parent->_bf = 2说明是右边高，如果parent->_bf = -2，说明是左边高。

总结：
cur->left 比 parent大，所以，cur->left做parent的右没有问题
cur->left比cur小，所以，cur->left做cur的左没有问题

核心操作：
parent->right = cur->left
cur->left = parent;

2.2.2 右单旋

发生右单旋的情况（具体图）：
在这里插入图片描述
发生右单旋的抽象图（有很多种情况）：

旋转：
右边高 --> 往左边旋转
左边高 --> 往右边旋转

旋转的时候要注意的问题：

保持他是搜索树
变成平衡树且降低这个子树的高度

2.2.3 左右双旋

左右双旋的情况：
当父节点左边高并且当前节点的右边高时，就会发生左右双旋。
在这里插入图片描述

双旋平衡因子的更新：
区分的关键，看插入节点的父节点的平衡因子
平衡因子的三种情况：h == 0, h > 0。h > 0又分为两种情况：插入节点是父节点的左子树或者插入节点是父节点的右子树

2.2.4 右左双旋

右左双旋：
当父节点的右边高并且当前节点的左边高时，就会发生右左双旋
在这里插入图片描述

如何分清是单旋还是双旋？
单旋：单纯的一边高，左边高或者右边高
双旋：有折现的产生。

3 代码

AVLTree.h

#pragma once
#include <iostream>
#include <assert.h>
using namespace std;

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


//new一个AVLTreeNode节点的时候就会调用这个构造函数
// 如果传入参数，就是kv
AVLTreeNode(const pair<K, V>& kv)
:_kv(kv)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_bf(0)
{}
};

template <class K, class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;
public:
bool Insert(const pair<K, V>& kv)
{
//搜索的插入
//...控制平衡
//新增在左边，父节点的平衡因子-- | 新增在右边，父节点的平衡因子++  新增的节点会影响到它的祖先
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}

Node* parent = nullptr;
Node* cur = _root;
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
{
assert("插入相同的节点");
}
}

//走到这里，找到了要插入的位置 --> 将cur插入进去
cur = new Node(kv);
if (cur->_kv.first < parent->_kv.first)
parent->_left = cur;
else
parent->_right = cur;

//因为是三叉链，所以cur的_parent指针还要指回去
cur->_parent = parent;

//走到这里，插入完成了。需要检查平衡因子，判断是否平衡，不平衡要进行旋转
while (parent)
{
//插入的位置是左孩子，bf--;插入的位置是右孩子，bf++
if (cur == parent->_left)
parent->_bf--;
else
parent->_bf++;

//接下来要判断根据不同的平衡因子进行不同的更新的情况
if (parent->_bf == 0)
{
break;  //如果是0， 就不用更新了
}
else if (parent->_bf == -1 || parent->_bf == 1)   //如果插入之后parent的平衡因子等于-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);
}
else
{
assert("平衡因子出错");
}
break;
}
else
{
assert("平衡因子出错");
}
}
return true;
}

void RotateL(Node* parent)
{
Node* cur = parent->_right;
Node* curleft = cur->_left;

//1.把curleft给parent的right  --> parent的_right指向curleft
parent->_right = curleft;

//判断curleft是否为空，如果不为空，就curleft的父节点指回去
if (curleft)
{
curleft->_parent = parent;
}

//2.parent的right给cur的left  --> cur的_left指向parent
cur->_left = parent;

//3.判断parent是不是当前的根节点,如果是，cur的_parent就为空。如果不是，cur的_parent还要指向ppnode
Node* ppnode = parent->_parent;

//4.parent还要往回指，因为是三叉链
parent->_parent = cur;

if (parent == _root)  //如果是根节点
{
_root = cur;
cur->_parent = nullptr;
}
else
{
//如果不是根节点，就要判断是ppnode的左孩子还是右孩子
if (ppnode->_left == parent)
ppnode->_left = cur;
else
ppnode->_right = cur;

//往回指
cur->_parent = ppnode;
}

//更新平衡因子
parent->_bf = cur->_bf = 0;
}

void RotateR(Node* parent)
{
Node* cur = parent->_left;
Node* curright = cur->_right;

//1.让parent的左指向cur的右
parent->_left = curright;

if (curright)
{
//第一次往回指
curright->_parent = parent;
}

//找到parent的父节点
Node* ppnode = parent->_parent;
//2.cur的右指向parent
cur->_right = parent;

//第二次往回指
parent->_parent = cur;

if (parent == _root)
{
_root = cur;
cur->_parent = nullptr;
}
else
{
parent->_parent = cur;
if (ppnode->_left == parent)
ppnode->_left = cur;
else
ppnode->_right = cur;

//第三次往回指
cur->_parent = ppnode;
}

//更新平衡因子
cur->_bf = parent->_bf = 0;
}

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

RotateL(cur);
RotateR(parent);

//根据不同的情况修改平衡因子
if (bf == 0)
{
cur->_bf = 0;
parent->_bf = 0;
curright->_bf = 0;
}
else if (bf == 1)   //说明左边低，右边高
{
parent->_bf = 0;
cur->_bf = -1;
curright->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 1;
cur->_bf = 0;
curright->_bf = 0;
}
else
{
assert("RotateLR false");
}
}

void RotateRL(Node* parent)
{
Node* cur = parent->_right;
Node* curleft = cur->_left;
int bf = curleft->_bf;   //提前保存下来

RotateR(cur);
RotateL(parent);

if (bf == 0)
{
cur->_bf = 0;
parent->_bf = 0;
curleft->_bf = 0;
}
else if (bf == 1)  //说明插入的位置是curleft的右边
{
parent->_bf = -1;
cur->_bf = 0;
curleft->_bf = 0;
}
else if (bf == -1)  //插入的位置是curleft的左边
{
parent->_bf = 0;
cur->_bf = 1;
curleft->_bf = 0;
}
else
{
assert("RotateRL false");
}
}

//bool Erase(const pair<K, V>& key)
//{

//}
int Height()
{
return Height(_root);
}

int Height(Node* root)
{
if (root == nullptr)
return 0;

int leftHeight = Height(root->_left);
int rightHeight = Height(root->_right);

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

bool IsBalance()
{
return IsBalance(_root);
}

bool IsBalance(Node* root)
{
if (root == nullptr)
return true;

int leftHight = Height(root->_left);
int rightHight = Height(root->_right);

if (rightHight - leftHight != root->_bf)
{
cout << "平衡因子异常:" << root->_kv.first << "->" << root->_bf << endl;
return false;
}

return abs(rightHight - leftHight) < 2
&& IsBalance(root->_left)
&& IsBalance(root->_right);
}

void Inorder()
{
_Inorder(_root);
}

private:
void _Inorder(Node* cur)
{
if (cur == nullptr)
return;

_Inorder(cur->_left);
cout << cur->_kv.first << " : " << cur->_kv.second << " : " << cur->_bf << endl;
_Inorder(cur->_right);
}
private:
Node* _root = nullptr;
};

Test_AVLTree.cpp

#include "AVLTree.h"


void testAVL1()
{
int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
AVLTree<int, int> t;
for (auto e : a)
{
t.Insert(make_pair(e, e));
}

t.IsBalance();
t.Inorder();
}

int main()
{
testAVL1();
return 0;
}

在这里插入图片描述

原文地址：https://blog.csdn.net/qq_64076540/article/details/142848524

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：【系统架构设计师】专题：计算机网络考点梳理
下一篇：2024-10-15 Nuxt3打包部署到Nginx流程

【代码随想录Day43】动态规划Part11
【代码】【代码随想录Day43】动态规划Part11。
阅读更多2024-10-15
python pip安装requirements.txt依赖与国内镜像
文章浏览阅读675次。pip install xxxxxx -i https://mirrors.aliyun.com/pypi/simple/由于众所周知的原因，国内python通过pip安装包时候
阅读更多2024-10-15
JavaScript前端开发技术详解
JavaScript前端开发是一个充满挑战和机遇的领域。随着技术的不断进步和用户需求的变化，前端开发者需要不断学习新知识、掌握新技能，以应对日益复杂和多样化的开发需求。同时，注重性能优化和安全实践也是
阅读更多2024-10-15
2025年国考报名流程详细图解—新手版
2025年国考报名流程详细图解—新手版
阅读更多2024-10-15
npm install进度卡在 idealTree:node_global: sill idealTree buildDeps
重新安装：pm config set registry https://registry.npmmirror.com。ping一下源：ping http://registry.npm.taobao.o
阅读更多2024-10-15
基于离群点修正、优化分解和DLinear模型的多步风速预测方法
本文提出了一种结合离群点修正、启发式算法、信号分解方法和DLinear模型的混合风速预测模型。该模型包括三个主要步骤：首先，通过检测并替换风速序列中的离群点，以减少其对预测精度的影响。接着，经过HI处
阅读更多2024-10-15
道路车辆功能安全 ISO 26262标准（4-4）—系统级产品开发
本系列文章主要讲解道路车辆功能安全 ISO 26262标准的相关知识。（系统级产品开发）
阅读更多2024-10-15
7.跨学科应用
1.基于深度学习的分子性质预测和新分子生成算法,指通过利用神经网络模型等习大量分子数据在保证分子稳定性和活性的前提下，生成新的药物分子,并预测新分子的药效和毒副作用等，以此减少新药物的研发时间和成本的
阅读更多2024-10-15
linux开发工具
linux开发工具
阅读更多2024-10-15
【OpenCV】（六）—— 阈值处理
本文介绍使用opencv进行阈值处理，包括基本阈值处理和自动阈值处理两种方法
阅读更多2024-10-15