C++实现AVL树

ops/2024/10/21 13:22:29/

文章目录

  • 为什么要有AVL树
  • 1.AVL树
  • 2.实现AVL树
    • 2.1AVL树节点的定义
    • 2.2AVL树的插入
      • 2.2.1.AVL树的旋转
    • AVL树的验证
  • 代码

为什么要有AVL树

我们都知道二叉搜索树的规则，插入一个节点时，如果比当前节点值大就到右边，反之则到左边。这样使得中序遍历这颗树可以得到一个有序的数组。如果我们要查找这颗树当中的一个值，最大的时间复杂度是多少呢？O(N)，发生这种事情的原因呢，如果我们插入一个有序的数据，它就会排成一条链。
二叉搜索树
如果树的结构为这种结构的话，我们要查找一个数就可能需要遍历这个数的所有节点。为了解决这个问题，两位俄国的数学家：G.M.Adelson-Velskii和E.M.Landis在1962年发明连里一种解决上述问题的方法：当二叉搜索树中插入新的节点后，如果能保证每个节点的左右子树高度差的绝对值不超过1，即可降低书的高度，从而减少平均搜索长度。

1.AVL树

AVL树是具有以下性质的二叉搜索树：

1.它的左右子树都是AVL树
2.左右子树高度之差（简称平衡因子）的绝对值不超过1.

如果一颗二叉搜索树是高度平衡的。那么它就是AVL树。如果它右n个节点，其高度课保持再logn，搜索时间复杂度为logn

2.实现AVL树

2.1AVL树节点的定义

在二叉平衡树的基础上，添加了平衡因子_bf（左右子树高度之差），以及parent指针，用来指向父节点。

#include <iostream>
using namespace std;template <class K,class V>
struct AVLTreeNode
{AVLTreeNode(const 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;pair<K, V> _kv;int _bf;
};template <class K,class V>
class AVLTree
{typedef AVLTreeNode<K,V> Node;
public:private:Node* _root = nullptr;
};

2.2AVL树的插入

AVL树的插入可以说是AVL树最重要的内容，不过因为AVL树是再二叉平衡树的基础上加入了平衡因子，所以最开始的插入操作和二叉平衡树是相同的。在插入后就要更新平衡因子。
cur插入后，parent的平衡因子一定需要调整，在插入之前，parent
的平衡因子分为三种情况：-1，0, 1, 分以下两种情况：

  1. 如果cur插入到parent的左侧，只需给parent的平衡因子-1即可
  2. 如果cur插入到parent的右侧，只需给parent的平衡因子+1即可

此时：parent的平衡因子可能有三种情况：0，正负1， 正负2

  1. 如果parent的平衡因子为0，说明插入之前parent的平衡因子为正负1，插入后被调整成0，此时满足
    AVL树的性质，插入成功
  2. 如果parent的平衡因子为正负1，说明插入前pParent的平衡因子一定为0，插入后被更新成正负1，此
    时以parent为根的树的高度增加，需要继续向上更新
bool Insert(const pair<K, V> kv){//1.前期操作与二叉树搜索树的插入操作相似if (!_root){_root = new Node(kv);return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (kv.first > cur->_kv.first){parent = cur;//更新父节点cur = cur->_right;}else if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else{return false;//已存在}}cur = new Node(kv);if (kv.first > parent->_kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//链接父节点//2.新节点插入后，AVL树的平衡性可能会遭到破坏，此时就需要更新平衡因子，并检测是否破坏了AVL树while (parent){if (parent->_right == cur){parent->_bf++;}else{parent->_bf--;}if (parent->_bf == 0){break;//更新后bf为0，表示对二叉树的平衡无影响，可以直接退出}else if (parent->_bf == 1 || parent->_bf == -1){cur = parent;parent = parent->_parent;//向上更新}else if (parent->_bf == -2 || parent->_bf == 2){//出现问题了，要进行处理}else{assert(false);//表示早已出现问题，直接断错}}return true;}

以上就是AVL树中插入的基础结构，先进行的二叉搜索树中的插入操作，然后在节点插入过后，因为AVL树的平衡性可能会改变，所以我们要开始对树进行处理。下面就是针对当树的平衡性出现问题时，我们应该进行的操作。即旋转
也就是上面未提到的第3点
3. 如果pParent的平衡因子为正负2，则pParent的平衡因子违反平衡树的性质，需要对其进行旋转处理

2.2.1.AVL树的旋转

如果在一颗原本平衡的AVL树中插入一个新的节点，造成了AVL树的不平衡。此时我们必须要调整树的结构，使之平衡化。根据插入位置的不同，AVL树的旋转可以分未4种：
1.新节点插入较高左子树的左侧——此时parent的平衡因子为-2，cur的平衡因子为-1
用图片表示：
右旋

右旋之后：原本parent和cur的平衡因子都变为0。

上图在插入前，AVL树是平衡的，新节点插入到30的左子树(注意：此处不是左孩子)中，30左子树增加
了一层，导致以60为根的二叉树不平衡，要让60平衡，只能将60左子树的高度减少一层，右子树增加一层，
即将左子树往上提，这样60转下来，因为60比30大，只能将其放在30的右子树，而如果30有右子树，右子树根的值一定大于30，小于60，只能将其放在60的左子树，旋转完成后，更新节点的平衡因子即可。在旋转过程中，有以下几种情况需要考虑：
1. 30节点的右孩子可能存在，也可能不存在
2. 60可能是根节点，也可能是子树
如果是根节点，旋转完成后，要更新根节点
如果是子树，可能是某个节点的左子树，也可能是右子树

void RotateR(Node* parent){Node* SubL = parent->_left;Node* SubLR = SubL->_right;Node* ppnode = parent->_parent;//最后链接更新后的"头节点"parent->_left = SubLR;SubL->_right = parent;if (SubLR)SubLR->_parent = parent;parent->_parent = SubL;if (_root == parent){_root = SubL;SubL->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = SubL;}else{ppnode->_right = SubL;}SubL->_parent = ppnode;}//更新bfparent->_bf = 0;SubL->_bf = 0;}

2.新节点插入较高右子树的右侧——parent的平衡因子为2，cur的平衡因子为1：左旋
具体的操作和上面并没有太多的差别，来看看图片的表示吧：
左旋

void RotateL(Node* parent){Node* SubR = parent->_right;Node* SubRL = SubR->_left;Node* ppnode = parent->_parent;parent->_right = SubRL;SubR->_left = parent;if (SubRL)SubRL->_parent = parent;parent->_parent = SubR;if (_root == parent){_root = SubR;SubR->_parent = nullptr;}else{if (ppnode->_right == parent){ppnode->_right = SubR;}else{ppnode->_left = SubR;}SubR->_parent = ppnode;}SubR->_bf = 0;parent->_bf = 0;}

3.新节点插入较高子树的右侧——左右：先左旋再右旋
这种情况比前两种的情况就要复杂了。仅仅旋转一次已经满足不了条件了
画的步骤比较多，从网络偷了一张图：
左右旋

void RotateLR(Node* parent){Node* SubL = parent->_left;Node* SubLR = SubL->_right;int bf = SubLR->_bf;RotateL(SubL);RotateR(parent);if (bf == -1){SubLR->_bf = 0;SubL->_bf = 0;parent->_bf = 1;}else if (bf == 1){SubLR->_bf = 0;SubL->_bf = -1;parent->_bf = 0;}else if (bf == 0){SubLR->_bf = 0;SubL->_bf = 0;parent->_bf = 0;}else{assert(false);}}

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

右旋左旋

void RotateRL(Node* parent){Node* SubR = parent->_right;Node* SubRL = SubR->_left;int bf = SubRL->_bf;RotateR(SubR);RotateL(parent);//更新bfif (bf == 1){SubR->_bf = 0;parent->_bf = -1;}else if (bf == -1){parent->_bf = 0;SubR->_bf = 1;}else{parent->_bf = 0;SubR->_bf = 0;}}

完成各个旋转函数的实现，让我们再补起前面的代码吧

bool Insert(const pair<K, V> kv){//1.前期操作与二叉树搜索树的插入操作相似if (!_root){_root = new Node(kv);return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (kv.first > cur->_kv.first){parent = cur;//更新父节点cur = cur->_right;}else if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else{return false;//已存在}}cur = new Node(kv);if (kv.first > parent->_kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//链接父节点//2.新节点插入后，AVL树的平衡性可能会遭到破坏，此时就需要更新平衡因子，并检测是否破坏了AVL树while (parent){if (parent->_right == cur){parent->_bf++;}else{parent->_bf--;}if (parent->_bf == 0){break;//更新后bf为0，表示对二叉树的平衡无影响，可以直接退出}else if (parent->_bf == 1 || parent->_bf == -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{RotateLR(parent);}break;//更新完毕}else{assert(false);//表示早已出现问题，直接断错}}return true;}

AVL树的验证

我们写下了这个程序，但是怎么证明我们写对了呢？总不能使用俺寻思之力吧。为此我们还要写一个验证AVL树的函数。
我们都知道，AVL树一定也是二叉搜索树，所以如果中序打印出来不是一个有序的数组那么一定出问题了。验证完二叉搜索树后就是验证其为AVL树。
1.验证其为二叉搜索树

中序遍历为有序序列

写一个中序遍历，看打印结果

int main()
{//testint a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };AVLTree<int, int> t;for (auto e : a){t.Insert(make_pair(e, e));}t.inorder();return 0;
}

打印结果：1 2 3 4 5 6 7 14 15 16
没问题！
2。验证其为AVL树
节点的左右高度差的绝对值一定小于2，且左右高度差等于bf。

1.每个节点子树高度差的绝对值不超过1
2.节点的平衡因子计算是否正确

bool isbanlance(){return _isbanlance(_root);}private:bool _isbanlance(Node* root){if (!root) return true;int hleft = _height(root->_left);int hright = _height(root->_right);if (abs(hleft - hright) > 1){cout << root->_kv.first<<"不平衡！" << endl;return false;}if (hright - hleft != root->_bf){cout << root->_kv.first<<"平衡因子异常！" << endl;return false;}return _isbanlance(root->_left) && _isbanlance(root->_right);}

test

int main()
{//testint a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };AVLTree<int, int> t;for (auto e : a){t.Insert(make_pair(e, e));cout << e << "->" << t.isbanlance() << endl;}t.inorder();return 0;
}

打印结果：
4->1
2->1
6->1
1->1
3->1
5->1
15->1
7->1
16->1
14->1
1 2 3 4 5 6 7 14 15 16
目前看没有问题，但这也只是小范围的数据，接下来我们试试大数据的。
大数据插入
可以看出随机数的插入也是没有问题的，那么我们的AVL树可以说是没有问题的。

优化验证函数
在查找树的高度的时候就已经，对树进行了遍历，后续却还要再次遍历一遍树结构，造成了时间的浪费，那么我们是不是可以在查找高度的时候直接把高度带回来，后面也不判断了。

bool _IsBalance(Node* root, int& height){if (root == nullptr){height = 0;return true;}int leftHeight = 0, rightHeight = 0;if (!_IsBalance(root->_left, leftHeight)|| !_IsBalance(root->_right, rightHeight)){return false;}if (abs(rightHeight - leftHeight) >= 2){cout << root->_kv.first << "不平衡" << endl;return false;}if (rightHeight - leftHeight != root->_pf){cout << root->_kv.first << "平衡因子异常" << endl;return false;}height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;return true;}

代码

#include <iostream>
#include <assert.h>
#include <cstdbool>
#include <vector>
#include <cmath>
#include<utility>
using namespace std;template <class K,class V>
struct AVLTreeNode
{AVLTreeNode(const 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;pair<K, V> _kv;int _bf;
};template <class K,class V>
class AVLTree
{typedef AVLTreeNode<K,V> Node;
public:bool Insert(const pair<K, V>& kv){//1.前期操作与二叉树搜索树的插入操作相似if (!_root){_root = new Node(kv);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (kv.first > cur->_kv.first){parent = cur;//更新父节点cur = cur->_right;}else if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else{return false;//已存在}}cur = new Node(kv);if (kv.first > parent->_kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//链接父节点//2.新节点插入后，AVL树的平衡性可能会遭到破坏，此时就需要更新平衡因子，并检测是否破坏了AVL树while (parent){if (parent->_right == cur){parent->_bf++;}else{parent->_bf--;}if (parent->_bf == 0){break;//更新后bf为0，表示对二叉树的平衡无影响，可以直接退出}else if (parent->_bf == 1 || parent->_bf == -1){//cur = parent;cur = 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{RotateLR(parent);}break;//更新完毕}else{assert(false);//表示早已出现问题，直接断错}}return true;}void RotateR(Node* parent){Node* SubL = parent->_left;Node* SubLR = SubL->_right;Node* ppnode = parent->_parent;//最后链接更新后的"头节点"parent->_left = SubLR;SubL->_right = parent;if (SubLR)SubLR->_parent = parent;parent->_parent = SubL;if (_root == parent){_root = SubL;SubL->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = SubL;}else{ppnode->_right = SubL;}SubL->_parent = ppnode;}//更新bfparent->_bf = 0;SubL->_bf = 0;}void RotateL(Node* parent){Node* SubR = parent->_right;Node* SubRL = SubR->_left;Node* ppnode = parent->_parent;parent->_right = SubRL;SubR->_left = parent;if (SubRL)SubRL->_parent = parent;parent->_parent = SubR;if (_root == parent){_root = SubR;SubR->_parent = nullptr;}else{if (ppnode->_right == parent){ppnode->_right = SubR;}else{ppnode->_left = SubR;}SubR->_parent = ppnode;}SubR->_bf = 0;parent->_bf = 0;}void RotateRL(Node* parent){Node* SubR = parent->_right;Node* SubRL = SubR->_left;int bf = SubRL->_bf;RotateR(SubR);RotateL(parent);//更新bfif (bf == 1){SubR->_bf = 0;parent->_bf = -1;}else if (bf == -1){parent->_bf = 0;SubR->_bf = 1;}else{parent->_bf = 0;SubR->_bf = 0;}}void RotateLR(Node* parent){Node* SubL = parent->_left;Node* SubLR = SubL->_right;int bf = SubLR->_bf;RotateL(SubL);RotateR(parent);if (bf == -1){SubLR->_bf = 0;SubL->_bf = 0;parent->_bf = 1;}else if (bf == 1){SubLR->_bf = 0;SubL->_bf = -1;parent->_bf = 0;}else if (bf == 0){SubLR->_bf = 0;SubL->_bf = 0;parent->_bf = 0;}else{assert(false);}}void inorder()//中序遍历{_inorder(_root);cout << endl;}int height(){return _height(_root);}bool isbanlance(){return _isbanlance(_root);}private:bool _isbanlance(Node* root){if (!root) return true;int hleft = _height(root->_left);int hright = _height(root->_right);if (abs(hleft - hright) > 1){cout << root->_kv.first<<"不平衡！" << endl;return false;}if (hright - hleft != root->_bf){cout << root->_kv.first<<"平衡因子异常！" << endl;return false;}return _isbanlance(root->_left) && _isbanlance(root->_right);}private:int _height(Node* root){if (!root) return 0;int hleft = _height(root->_left);int hright = _height(root->_right);return max(hleft, hright) + 1;}private:void _inorder(Node* root){if (!root){return;}_inorder(root->_left);cout << root->_kv.first<<' ';_inorder(root->_right);}
private:Node* _root = nullptr;
};

测试代码

//testconst int N = 1000000;vector<int> v;v.reserve(N);srand(time(0));for (size_t i = 0; i < N; i++){v.push_back(rand() + i);//cout << v.back() << endl;}size_t begin2 = clock();AVLTree<int, int> t;for (auto e : v){t.Insert(make_pair(e, e));//cout << "Insert:" << e << "->" << t.IsBalance() << endl;}size_t end2 = clock();cout << t.isbanlance();

讲的比较乱。写的也比较赶。大概会有错误的地方，前面写的代码，后面我可能改了，应该都修改了，但也可能会遗漏。文章写到比较杂，感谢你的浏览。
完
在这里插入图片描述


http://www.ppmy.cn/ops/5581.html

相关文章

前端-每天一道面试题（2）-localStorage/sessionStorage/cookie的区别

前端-每天一道面试题（2）-localStorage/sessionStorage/cookie的区别

都是本地缓存数据的方式。 cookie:类型为小型文本文件&#xff0c;是某些网站为了辨别用户身份而储存在用户本地终端上的数据。是为了解决HTTP无状态导致的问题。最大为4KB,由一个名称&#xff0c;一个值&#xff0c;和其它几个用于控制cookie有效期&#xff0c;安全性&#x…
阅读更多...
单链表的应用

单链表的应用

文章目录 目录1. 单链表经典算法OJ题目1.1 [移除链表元素](https://leetcode.cn/problems/remove-linked-list-elements/description/)1.2 [链表的中间节点](https://leetcode.cn/problems/middle-of-the-linked-list/description/)1.3 [反转链表](https://leetcode.cn/problem…
阅读更多...
windows 下 docker compose 安装 ollama 和 open-webui ，打造私有GPT

windows 下 docker compose 安装 ollama 和 open-webui ，打造私有GPT

在人工智能领域&#xff0c;GPT&#xff08;Generative Pre-trained Transformer&#xff09;模型因其强大的文本生成能力而广受欢迎。但是&#xff0c;由于资源限制&#xff0c;个人用户可能难以直接运行和训练这样的大型模型。幸运的是&#xff0c;有一些开源项目如Ollama和O…
阅读更多...
每日一题（4.20）

每日一题（4.20）

目录 Leecode-118-杨辉三角题目示例解题思路代码实现 Leecode-238-除自身以外数组的乘积题目示例解题思路代码实现 Leecode-118-杨辉三角 题目 给定一个非负整数 numRows&#xff0c;生成「杨辉三角」的前 numRows 行。 在「杨辉三角」中&#xff0c;每个数是它左上方和右上…
阅读更多...
Mac M1芯片启动项目时出现 no zstd-jni in java.library.path 问题排查

Mac M1芯片启动项目时出现 no zstd-jni in java.library.path 问题排查

优质博文&#xff1a;IT-BLOG-CN 问题 通过 Mac M1芯片的电脑启动项目时出现了zstd-jni包的问题&#xff0c;同事的M2芯片启动项目是正常的&#xff0c;所以初步判断是M1芯片和zstd-jni包之间不兼容的问题。 java.lang.UnsatisfiedLinkError: no zstd-jni in java.library.pa…
阅读更多...
考察自动化立体库应注意的几点

考察自动化立体库应注意的几点

导语 大家好&#xff0c;我是智能仓储物流技术研习社的社长&#xff0c;老K。专注分享智能仓储物流技术、智能制造等内容。 整版PPT和更多学习资料&#xff0c;请球友到知识星球 【智能仓储物流技术研习社】自行下载 考察自动化立体仓库的关键因素&#xff1a; 仓库容量&#x…
阅读更多...
【nodejs】使用express-generator快速搭建项目框架

【nodejs】使用express-generator快速搭建项目框架

文章目录 一、全局安装express-generator二、安装依赖三、启动项目四、修改文件便重启服务器1、全局安装nodemon2、修改 package.json 文件3、npm start 启动项目 一、全局安装express-generator npm install -g express-generator二、安装依赖 项目根目录打开终端&#xff0…
阅读更多...
消息转化器(解决由于后端给前端响应的格式中不能处理Long类型，因为js只会处理前16位，这样会导致后面的精度丢失)

消息转化器(解决由于后端给前端响应的格式中不能处理Long类型，因为js只会处理前16位，这样会导致后面的精度丢失)

问题描述&#xff1a;由于后端给前端响应的格式中不能处理Long类型&#xff0c;因为js只会处理前16位&#xff0c;这样会导致后面的精度丢失。 解决方法&#xff0c;将后端响应给前端的数据转化位JSON格式&#xff0c;将long类型的序列化一下 下面为具体方法(JAVA对象转化为J…
阅读更多...
最新文章

Copyright @ 2022~2023