C++实现AVL树增删查

目录

1. AVL的概念

（1）名字的由来

（2）什么是AVL树

（3）实现方法

（4）为什么高度差是1

（5）对比二叉搜索树

2. AVL树的结构

 3. AVL树的功能

（1）旋转

右单旋

左单旋

 左右双旋

右左双旋

（2）节点的插入

（3）查找

（4）节点的删除

查找要删除的节点

删除节点

平衡调整

（5）遍历节点

 4. 判断是否是AVL树

5. 复杂度分析

时间复杂度

 空间复杂度

6. 析构函数

7. 源代码

1. AVL的概念

（1）名字的由来

AVL树的名字来自于它的发明者前苏联的科学家G.M.Adelson-Velsky和E.M.Landis在1962年的论文《An algorithm for the organization of information》中发表。

（2）什么是AVL树

AVL树是最先发明的自平衡二叉查找树，AVL树是一颗空树，或者具备下列性质的一颗二叉搜索树

1. 左右子树都是AVL树

2. 左右子树高度差的绝对值不超过1(<2)

 AVL树是一颗高度平衡搜索二叉树，通过控制高度差去控制平衡。

（3）实现方法

本文AVL树的实现是基于平衡因子(balance factor)来实现的，每个节点都有一个平衡因子，本文任何节点的平衡因子等于右子树高度减去左子树高度(平衡因子也可以等于左子树高度减去右子树高度，本文采用右减左)，也就是说任何节点的平衡因子等于0/1/-1/。(AVL树并不是必须要平衡因子，但是有了平衡因子可以更方便我们去进行观察和控制树是否平衡)。

（4）为什么高度差是1

AVL树要求高度差不超过1，为什么不是要求高度差不超过0呢？因为有些情况下做不到高度差是0，比如只有2个节点的时候或4个节点这些情况下，高度差最小为1，无法将高度差变为0.

（5）对比二叉搜索树

AVL树整体节点数量和分布和完全二叉树类似，高度可以控制在logN，那么增删查改的效率也可以控制在O(logN),相比二叉搜索树有了质的提升。

2. AVL树的结构

出来左右孩子还有当前节点的父亲节点，方便调整平衡因子，以及_bf来存储平衡因子，_kv来存储值

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;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;//各种功能private:int _size = 0;Node* _root = nullptr;};

 3. AVL树的功能

（1）旋转

旋转的原则

1. 保持搜索树的规则。

2. 让旋转的树从不满足变平衡，其次降低旋转树的高度。

 旋转分为四种：左单旋/右单旋/左右双旋/右左双旋。

右单旋

所有情况都可以总结为下图

1. 以12为根的树，其中a，b，c都是子树(可能是空树，h>=0),a/b/c均符合AVL树的要求。12可以是整颗树的根也可以是一整棵树中局部的子树的根。

2. 在a子树中插入一个新节点，导致a子树的高度，从h变为h+1，不断向上更新平衡因子，导致10的平衡因子从-1变成了-2，高度差超过了1，违反平衡规则。10为根的树左边太高了，需要往右边旋转，控制两棵树的平衡。

3. 旋转核心步骤，因为6<b子树的值<12,将b变成12的左子树，12变成6的右子树，6变成这棵树的根，符合搜索树的规则，控制了平衡，同时这棵的高度恢复到了插入之前的h+2，符合旋转原则。如果插入之前12是整颗树的一个局部子树，旋转后不会再影响上一层，插入结束了。

 代码实现

注意

	//右单旋void RotateR(Node* parent){Node* curL = parent->left;Node* curLR = curL->right;parent->left = curLR;//curLR是一定在parent左边的，即比parent的值小curL->right = parent;if (curLR)//如果它不是空的就将其父亲改为parentcurLR->_parent = parent;if (parent->_parent)//parent的父亲不是空，就改变父亲指向的孩子{curL->_parent = parent->_parent;//将旋转上来的节点父亲更改if (parent->_parent->left == parent){parent->_parent->left = curL;}elseparent->_parent->right = curL;}else//是空说明是根节点{_root = curL;curL->_parent = nullptr;//将新的根节点父亲置为空}parent->_parent = curL;//将原父亲节点的父亲改变parent->_bf = curL->_bf = 0;//修改完后这两个是平衡的}
左单旋

 如下图，基本跟上面右单旋类似

在a⼦树中插⼊⼀个新结点，导致a⼦树的⾼度从h变成h+1，不断向上更新平衡因⼦，导致10的平 衡因⼦从1变成2，10为根的树左右⾼度差超过1，违反平衡规则。10为根的树右边太⾼了，需要往 左边旋转，控制两棵树的平衡。

旋转核心步骤，因为10<b⼦树的值<15,将b变成10的右子树，10变成15的左⼦树，15变成这棵树新的根，符合搜索树的规则，控制了平衡，同时这棵的⾼度恢复到了插⼊之前的h+2，符合旋转原则。如果插⼊之前10整棵树的⼀个局部⼦树，旋转后不会再影响上⼀层，插⼊结束了。

 代码实现

	//左单旋void RotateL(Node* parent){Node* curR = parent->right;Node* curRL = curR->left;parent->right = curRL;curR->left = parent;if (curRL)//看是否为空{curRL->_parent = parent;}if (parent->_parent){curR->_parent = parent->_parent;if (parent->_parent->left == parent){parent->_parent->left = curR;}elseparent->_parent->right = curR;}else{_root = curR;curR->_parent = nullptr;}parent->_parent = curR;parent->_bf = curR->_bf = 0;}
 左右双旋

 通过上图我们可以看到，左边更高时插入的若不是5的左边就无法用右单旋来解决问题，我们就可以用两次旋转来解决，以5为旋转点来一个左单旋，以10为旋转点再进行一个右单旋，这棵树就平衡了。

插入问题很容易就解决了，但是平衡因子需要我们单独解决

大致有三种情况，我用具体的来演示

我们需要记录三个节点的平衡因子。平衡因子为-2的节点parent，与其左边的节点curL，与其左边的右边的节点curLR。

当curLR平衡因子为-1时

最后curL，curLR平衡因子为0，parent平衡因子为1

我们将所有左或右子树为空的地方插入高度为h的avl树，然后将curLR的左子树高度变为h+1，操作与结果和上图一样。

当curLR平衡因子为1时

 最后parent，curLR平衡因子为0，curL平衡因子为-1

同理将所有左或右子树为空的地方插入高度为h的avl树，然后将curLR的右子树高度变为h+1，操作与结果和上图一样

当curLR平衡因子为0时

最后 这三个节点的平衡因子都为0

我们由以上总结可得

1. 当curLR平衡因子为0时，最终这三个节点平衡因子都为0

2. 当curLR平衡因子为-1时，最终parent的平衡因子为1

3. 当curLR平衡因子为1时，最终curL的平衡因子为-1

 代码实现如下

	//左右双旋void RotateLR(Node* parent){//记录下来父亲P的左边与  左边的右边Node* curL = parent->left;Node* curLR = curL->right;int bf = curLR->_bf;//先进行一个左单旋，再进行一个右单旋RotateL(parent->left);RotateR(parent);//针对平衡因子的修改,通过画图可得规律if (bf == 0){parent->_bf = 0;curL->_bf = 0;curLR->_bf = 0;}else if (bf == -1){parent->_bf = 1;curL->_bf = 0;curLR->_bf = 0;}else if (bf == 1){parent->_bf = 0;curL->_bf = -1;curLR->_bf = 0;}else//除以上的情况肯定就是出错了assert(false);}
右左双旋

通过上图我们可以发现，右边更高时插入的的若不是14节点的右边就无法用左单旋来解决问题，我们就可以用两次旋转来解决，以14为旋转点右单旋，以10为旋转点再来一个左单旋，这棵树就平衡了。

我们下面来看一下平衡因子的问题

也是三种情况

当culRL平衡因子为-1时

 最终parent，curRL平衡因子为0，curR平衡因子为1

将所有左或右子树为空的地方插入高度为h的avl树，然后将curRL的左子树高度变为h+1，操作与结果和上图一样。

当curRL平衡因子为1时

 最终curRL，curR平衡因子为0，parent平衡因子为-1

将所有左或右子树为空的地方插入高度为h的avl树，然后将curRL的右子树高度变为h+1，操作与结果和上图一样。

当curRL平衡因子为0时

 最终这三个节点的平衡因子都为零

我们由上总结可得

1. 当curRL平衡因子为0时，最终这三个节点平衡因子都为0。

2. 当curRL平衡因子为-1时，最终curR平衡因子为1。

3. 当curRL平衡因子为1时，最终parent平衡因子为-1。

 代码实现如下

	//右左双旋void RotateRL(Node* parent){Node* curR = parent->right;Node* curRL = curR->left;int bf = curRL->_bf;RotateR(curR);RotateL(parent);if (bf == 0){parent->_bf = 0;curR->_bf = 0;curRL->_bf = 0;}else if (bf == -1){parent->_bf = 0;curR->_bf = 1;curRL->_bf = 0;}else if (bf == 1){parent->_bf = -1;curR->_bf = 0;curRL->_bf = 0;}elseassert(false);}
（2）节点的插入

插入值的大概流程

1. 插入一个值按二叉搜索树规则进行插入。

2. 新增节点以后，只会影响祖先节点的高度，也就可能会影响部分祖先节点的平衡因子，所以更新节点->根节点路径上的平衡因子，实际中最坏情况下要更新到根，有些情况更新到新中间就可以停止了，具体情况我们下面具体分析。

3. 更新平衡因子过程中没有问题，插入结束。

4. 更新平衡因子过程中出现不平衡，对不平衡子树旋转，旋转后本质调平衡的同时，本质降低了子树的高度，不会再影响上一层，所以插入结束了。

 平衡因子的更新

更新原则：

1. 平衡因子 = 右子树高度 - 左子树高度

2. 只有子树高度变化才会影响当前节点平衡因子

3. 插入节点，会增加高度，所以新增节点在parent的右子树，parent的平衡因子++，新增节      点在parent的左子树，parent平衡因子--

4. parent所在子树的高度是否变化决定了是否会继续往上更新

更新停止条件：

1. 更新后parent平衡因子==0，更新中parent的平衡因子变化为-1到0，或1到0，说明parent      子树一边高一边低，新增的节点插入在了低的那边，插入后parent所在的子树高度不变，      不会影响parent的父亲节点的平衡因子，更新结束。

2. 更新后parent的平衡因子==1或-1，更新前更新中parent的平衡因子变化为0到1，或0到-1，说明更新前parent子树两边一样高，新增的节点插入后，parent所在子树一边高一边低，parent所在的子树符合平衡要求，但是高度有增加，影响parent父亲节点的平衡因子所以要继续向上更新。

3. 更新后parent的平衡因子==2或-2，更新前到更新中parent的平衡因子变化为1->2或-1到-2，说明更新前parent的子树一边高一边低，新增插入节点在高的那边，高的更高破坏了平衡，parent所在的子树不符合平衡要求需要旋转处理。(旋转的目标有两个：1. 将parent子树旋转旋转平衡。2. 降低parent子树的高度，恢复到插入节点以前的高度。所以旋转后也不需要继续再往上更新了，插入结束)。

判断用什么旋转

其实我们根据上面旋转的讲解，可以总结出用什么旋转

当失衡节点平衡因子为-2时

看左节点，如果是-1，证明是右单旋，如果是1，就需要左右双旋来完成

当失衡节点平衡因子为2时

看右节点，如果是1，证明是左单旋，如果是-1，就需要右左双旋来完成

代码实现如下

	bool Insert(const pair<K,V>& kv){if (_root == nullptr){_root = new Node(kv);}else{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 (parent->_kv.first > kv.first){parent->left = cur;}elseparent->right = cur;cur->_parent = parent;//将新建的节点父亲赋值while (parent){if (cur == parent->left){parent->_bf--;}elseparent->_bf++;if (parent->_bf == 0)//不需要更新{break;}else if (parent->_bf == 1 || parent->_bf==-1)//如果它变成了1或-1说明高度变化了，需要向上更新{cur = parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2){//要进行旋转了//旋转分为四种情况，左单旋，右单旋，左右双旋，右左双旋if (parent->_bf == -2){if (cur->_bf == -1)//右单旋{RotateR(parent);}else if (cur->_bf == 1)//左右双旋{RotateLR(parent);}}else if (parent->_bf == 2){if (cur->_bf == 1)//左单旋{RotateL(parent);}else if (cur->_bf == -1)//右左双旋{RotateRL(parent);}}break;}else{assert(false);//正常不可能到这里，到这里直接说明错了}}}_size++;return true;}
（3）查找

与二叉搜索树基本一致，此处不过多赘述，搜索效率为OlogN

	Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->right;}else if (cur->_kv.first > key){cur = cur->left;}elsereturn cur;}return nullptr;}
（4）节点的删除

删除大体可以分为三步

查找要删除的节点

我们可以直接通过上面的Find函数来找到要删除的节点，如果找不到就直接返回

删除节点

删除分为三种情况

1. 要删除的节点为叶子结点

直接删除即可

2. 要删除的节点有一个子树

将这棵子树转接到要删除节点的父亲节点

3. 要删除的节点有两个子树

我们将其转化为上两种情况，找到左子树中的最大值或右子树中的最小值将这个节点的值赋值给我们要删除的节点，然后将找到的这个值删除(即删除左子树最小或右子树最大值)

平衡调整

删除完节点后我们就要进行平衡调整了，我们通过右子树高度减去左子树高度来更新平衡因子代码如下

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

从删除节点的父节点一直向上更新

当找到的失衡节点平衡因子为-2时

如上图根据左孩子的平衡因子来调整

与插入不同有平衡因子为0的情况(例如删除失衡节点右子树的节点)

当找到的失衡节点平衡因子为2时

 这就完成调整了

代码如下

	void Erase(const K& key){Node* tmp = Find(key);if (tmp == nullptr)return;Node* parent = tmp->_parent;//三种情况//1. 叶子if (tmp->left == nullptr && tmp->right == nullptr){if (tmp == _root)//如果是根节点{_root = nullptr;}else{if (parent->left == tmp){parent->left = nullptr;}else if (parent->right == tmp)parent->right = nullptr;elseassert(false);}delete tmp;tmp = nullptr;}//2. 有一个子树(左和右)else if (tmp->left == nullptr || tmp->right == nullptr){if (tmp == _root)//如果是根节点{if (tmp->left != nullptr)//如果左子树不为nullptr{_root = tmp->left;_root->_parent = nullptr;}else if (tmp->right != nullptr)//如果右子树不为nullptr{_root = tmp->right;_root->_parent = nullptr;}delete tmp;}else{if (parent->left == tmp)//看tmp是删除的父亲的左子树还是右子树{if (tmp->left != nullptr)//如果左子树不为nullptr{parent->left = tmp->left;tmp->left->_parent = parent;}else if (tmp->right != nullptr)//如果右子树不为nullptr{parent->left = tmp->right;tmp->right->_parent = parent;}delete tmp;}else if (parent->right == tmp){if (tmp->left != nullptr)//如果左子树不为nullptr{parent->right = tmp->left;tmp->left->_parent = parent;}else if (tmp->right != nullptr)//如果右子树不为nullptr{parent->right = tmp->right;tmp->right->_parent = parent;}delete tmp;}}}else//左右子树都有，选择左边最大或右边最小节点交换值,然后将左边最大或右边最小delete掉{Node* rsmall = tmp->right;//寻找tmp右子树中最小值parent = tmp;while (rsmall->left){parent = rsmall;rsmall = rsmall->left;}tmp->_kv = rsmall->_kv;if (parent->right == rsmall)//tmp的right就是右子树最小的值{parent->right = rsmall->right;}else{parent->left = rsmall->right;}if (rsmall->right)//如果不为空，就更新父节点rsmall->right->_parent = parent;delete rsmall;}Node* cur ;while (parent){parent->_bf = Height(parent->right) - Height(parent->left);if (parent->_bf == -2){cur = parent->left;cur->_bf = Height(cur->right) - Height(cur->left);if (cur->_bf == -1 || cur->_bf == 0){RotateR(parent);}else if (cur->_bf == 1){RotateLR(parent);}elseassert(false);}else if (parent->_bf == 2){cur = parent->right;cur->_bf = Height(cur->right) - Height(cur->left);if (cur->_bf == 1 || cur->_bf == 0){RotateL(parent);}else if (cur->_bf == -1){RotateRL(parent);}elseassert(false);}parent = parent->_parent;}_size--;}
（5）遍历节点

中序遍历，不过多赘述

	void InOrder(){_InOrder(_root);cout << endl;}void _InOrder(Node* root)//可以在外面再弄一个通过this指针访问{if (root == nullptr)return;_InOrder(root->left);cout << root->_kv.second << "   ";_InOrder(root->right);}

 4. 判断是否是AVL树

	void InOrder(){_InOrder(_root);cout << endl;}int _Height(){return Height(_root);}bool _IsBalanceTree(){return IsBalanceTree(_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 IsBalanceTree(Node* root){// 空树也是AVL树 if (nullptr == root)return true;// 计算pRoot结点的平衡因⼦：即pRoot左右⼦树的⾼度差 int leftHeight = Height(root->left);int rightHeight = Height(root->right);int diff = rightHeight - leftHeight;// 如果计算出的平衡因⼦与pRoot的平衡因⼦不相等，或者 // pRoot平衡因⼦的绝对值超过1，则⼀定不是AVL树 if (abs(diff) >= 2){cout << root->_kv.first << "⾼度差异常" << endl;return false;}if (root->_bf != diff){cout << root->_kv.first << "平衡因⼦异常" << endl;return false;}// pRoot的左和右如果都是AVL树，则该树⼀定是AVL树 return IsBalanceTree(root->left) && IsBalanceTree(root->right);}

5. 复杂度分析

对各个主要操作时间复杂度和空间复杂度同一分析

时间复杂度

Insert操作：平均和最坏情况下的时间复杂度均为O(logN),通过不断自调整来保持平衡，每次调整和旋转的操作时间都是常数级，查找插入位置过程时间复杂度也为O(logN)

Find操作：平均和最坏情况下的时间复杂度均为O(logN)

Erase操作：平均和最坏情况下的时间复杂度均为O(logN)，先查找节点位置，然后在进行调整，时间复杂度类似于插入操作

 空间复杂度

Insert操作：空间复杂度为O(1)。插入过程中空间消耗主要是创建新节点等

Find操作：空间复杂度为O(1)。

Erase操作：空间复杂度为O(1)。

 整颗AVL树的时间复杂度主要取决于树中节点的数量即O(N),N是节点的数量。

6. 析构函数

递归释放new动态开辟的空间

	~AvlTree(){Destroy(_root);}void Destroy(Node*& root){if (root == nullptr){return;}//递归销毁左子树Destroy(root->left);//递归销毁右子树Destroy(root->right);//销毁根节点delete root;root = nullptr;}

7. 源代码

#include<iostream>
#include<assert.h>
#include<vector>
#include<algorithm>using namespace std;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;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);}else{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 (parent->_kv.first > kv.first){parent->left = cur;}elseparent->right = cur;cur->_parent = parent;//将新建的节点父亲赋值while (parent){if (cur == parent->left){parent->_bf--;}elseparent->_bf++;if (parent->_bf == 0)//不需要更新{break;}else if (parent->_bf == 1 || parent->_bf==-1)//如果它变成了1或-1说明高度变化了，需要向上更新{cur = parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2){//要进行旋转了//旋转分为四种情况，左单旋，右单旋，左右双旋，右左双旋if (parent->_bf == -2){if (cur->_bf == -1)//右单旋{RotateR(parent);}else if (cur->_bf == 1)//左右双旋{RotateLR(parent);}}else if (parent->_bf == 2){if (cur->_bf == 1)//左单旋{RotateL(parent);}else if (cur->_bf == -1)//右左双旋{RotateRL(parent);}}break;}else{assert(false);//正常不可能到这里，到这里直接说明错了}}}_size++;return true;}//右单旋void RotateR(Node* parent){Node* curL = parent->left;Node* curLR = curL->right;parent->left = curLR;//curLR是一定在parent左边的，即比parent的值小curL->right = parent;if (curLR)//如果它不是空的就将其父亲改为parentcurLR->_parent = parent;if (parent->_parent)//parent的父亲不是空，就改变父亲指向的孩子{curL->_parent = parent->_parent;//将旋转上来的节点父亲更改if (parent->_parent->left == parent){parent->_parent->left = curL;}elseparent->_parent->right = curL;}else//是空说明是根节点{_root = curL;curL->_parent = nullptr;//将新的根节点父亲置为空}parent->_parent = curL;//将原父亲节点的父亲改变parent->_bf = curL->_bf = 0;//修改完后这两个是平衡的}//左单旋void RotateL(Node* parent){Node* curR = parent->right;Node* curRL = curR->left;parent->right = curRL;curR->left = parent;if (curRL)//看是否为空{curRL->_parent = parent;}if (parent->_parent){curR->_parent = parent->_parent;if (parent->_parent->left == parent){parent->_parent->left = curR;}elseparent->_parent->right = curR;}else{_root = curR;curR->_parent = nullptr;}parent->_parent = curR;parent->_bf = curR->_bf = 0;}//左右双旋void RotateLR(Node* parent){//记录下来父亲P的左边与  左边的右边Node* curL = parent->left;Node* curLR = curL->right;int bf = curLR->_bf;//先进行一个左单旋，再进行一个右单旋RotateL(parent->left);RotateR(parent);//针对平衡因子的修改,通过画图可得规律if (bf == 0){parent->_bf = 0;curL->_bf = 0;curLR->_bf = 0;}else if (bf == -1){parent->_bf = 1;curL->_bf = 0;curLR->_bf = 0;}else if (bf == 1){parent->_bf = 0;curL->_bf = -1;curLR->_bf = 0;}else//除以上的情况肯定就是出错了assert(false);}//右左双旋void RotateRL(Node* parent){Node* curR = parent->right;Node* curRL = curR->left;int bf = curRL->_bf;RotateR(curR);RotateL(parent);if (bf == 0){parent->_bf = 0;curR->_bf = 0;curRL->_bf = 0;}else if (bf == -1){parent->_bf = 0;curR->_bf = 1;curRL->_bf = 0;}else if (bf == 1){parent->_bf = -1;curR->_bf = 0;curRL->_bf = 0;}elseassert(false);}int Size(){return _size;}Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->right;}else if (cur->_kv.first > key){cur = cur->left;}elsereturn cur;}return nullptr;}void Erase(const K& key){Node* tmp = Find(key);if (tmp == nullptr)return;Node* parent = tmp->_parent;//三种情况//1. 叶子if (tmp->left == nullptr && tmp->right == nullptr){if (tmp == _root)//如果是根节点{_root = nullptr;}else{if (parent->left == tmp){parent->left = nullptr;}else if (parent->right == tmp)parent->right = nullptr;elseassert(false);}delete tmp;tmp = nullptr;}//2. 有一个子树(左和右)else if (tmp->left == nullptr || tmp->right == nullptr){if (tmp == _root)//如果是根节点{if (tmp->left != nullptr)//如果左子树不为nullptr{_root = tmp->left;_root->_parent = nullptr;}else if (tmp->right != nullptr)//如果右子树不为nullptr{_root = tmp->right;_root->_parent = nullptr;}delete tmp;}else{if (parent->left == tmp)//看tmp是删除的父亲的左子树还是右子树{if (tmp->left != nullptr)//如果左子树不为nullptr{parent->left = tmp->left;tmp->left->_parent = parent;}else if (tmp->right != nullptr)//如果右子树不为nullptr{parent->left = tmp->right;tmp->right->_parent = parent;}delete tmp;}else if (parent->right == tmp){if (tmp->left != nullptr)//如果左子树不为nullptr{parent->right = tmp->left;tmp->left->_parent = parent;}else if (tmp->right != nullptr)//如果右子树不为nullptr{parent->right = tmp->right;tmp->right->_parent = parent;}delete tmp;}}}else//左右子树都有，选择左边最大或右边最小节点交换值,然后将左边最大或右边最小delete掉{Node* rsmall = tmp->right;//寻找tmp右子树中最小值parent = tmp;while (rsmall->left){parent = rsmall;rsmall = rsmall->left;}tmp->_kv = rsmall->_kv;if (parent->right == rsmall)//tmp的right就是右子树最小的值{parent->right = rsmall->right;}else{parent->left = rsmall->right;}if (rsmall->right)//如果不为空，就更新父节点rsmall->right->_parent = parent;delete rsmall;}Node* cur ;while (parent){parent->_bf = Height(parent->right) - Height(parent->left);if (parent->_bf == -2){cur = parent->left;cur->_bf = Height(cur->right) - Height(cur->left);if (cur->_bf == -1 || cur->_bf == 0){RotateR(parent);}else if (cur->_bf == 1){RotateLR(parent);}elseassert(false);}else if (parent->_bf == 2){cur = parent->right;cur->_bf = Height(cur->right) - Height(cur->left);if (cur->_bf == 1 || cur->_bf == 0){RotateL(parent);}else if (cur->_bf == -1){RotateRL(parent);}elseassert(false);}parent = parent->_parent;}_size--;}void InOrder(){_InOrder(_root);cout << endl;}int _Height(){return Height(_root);}bool _IsBalanceTree(){return IsBalanceTree(_root);}~AvlTree(){Destroy(_root);}void Destroy(Node*& root){if (root == nullptr){return;}//递归销毁左子树Destroy(root->left);//递归销毁右子树Destroy(root->right);//销毁根节点delete root;root = nullptr;}private: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 IsBalanceTree(Node* root){// 空树也是AVL树 if (nullptr == root)return true;// 计算pRoot结点的平衡因⼦：即pRoot左右⼦树的⾼度差 int leftHeight = Height(root->left);int rightHeight = Height(root->right);int diff = rightHeight - leftHeight;// 如果计算出的平衡因⼦与pRoot的平衡因⼦不相等，或者 // pRoot平衡因⼦的绝对值超过1，则⼀定不是AVL树 if (abs(diff) >= 2){cout << root->_kv.first << "⾼度差异常" << endl;return false;}if (root->_bf != diff){cout << root->_kv.first << "平衡因⼦异常" << endl;return false;}// pRoot的左和右如果都是AVL树，则该树⼀定是AVL树 return IsBalanceTree(root->left) && IsBalanceTree(root->right);}void _InOrder(Node* root)//可以在外面再弄一个通过this指针访问{if (root == nullptr)return;_InOrder(root->left);cout << root->_kv.second << "   ";_InOrder(root->right);}int _size = 0;Node* _root = nullptr;};

这篇就到这里啦（づ￣3￣）づ╭❤～

ヾ(￣▽￣)Bye~Bye~

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

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

相关文章

芝法酱学习笔记（0.7）——harbor与项目容器化部署

芝法酱学习笔记（0.7）——harbor与项目容器化部署

前言 之前我们主要讲的jar包部署。使用jar包部署可能导致不同服务互相争抢资源&#xff08;隔离性&#xff09;&#xff0c;不同服务可能需要不同的jdk环境&#xff0c;有时也会造成困扰。故在微服务时代&#xff0c;我们通常使用docker部署 一、docker安装 docke相关的知识…
阅读更多...
新硬盘第一次使用需要怎样做？

新硬盘第一次使用需要怎样做？

无论是组装新电脑&#xff0c;还是给现有电脑增加存储空间&#xff0c;我们需要进行一些安装硬盘和设置硬盘的操作。对于没有相关经验的用户来说&#xff0c;对于拿到手的新硬盘会感到手足无措&#xff0c;不知道应该从哪里开始。今天小编详细介绍一下新硬盘第一次使用时的流程…
阅读更多...
Qt-窗口布局按钮输入类

Qt-窗口布局按钮输入类

1. 窗口布局 Qt 提供了很多摆放控件的辅助工具&#xff08;又称布局管理器或者布局控件&#xff09;&#xff0c;它们可以完成两件事&#xff1a; 自动调整控件的位置&#xff0c;包括控件之间的间距、对齐等&#xff1b; 当用户调整窗口大小时&#xff0c;位于布局管理器内的…
阅读更多...
AI没有是非观的原因

AI没有是非观的原因

人工智能没有价值观的原因主要可以归结为只有数据驱动的被动性相关算法&#xff0c;没有主动干预性及其反事实关系&#xff1a; &#xff08;1&#xff09;数据被动驱动 AI的学习、分析、预测只依赖于大量的数据&#xff0c;并通过模式识别和统计分析建立关联。而这些数据本身可…
阅读更多...
【算法】链表：2.两数相加（medium）+模拟

【算法】链表：2.两数相加（medium）+模拟

系列专栏 《分治》 《模拟》 《Linux》 目录 1、题目链接 2、题目介绍 3、解法 (模拟) 4、代码 1、题目链接 2. 两数相加 - 力扣&#xff08;LeetCode&#xff09; 2、题目介绍 3、解法 (模拟) 理解题目要求&#xff1a; 我们有两个链表&#xff0c;每个链表代表一个…
阅读更多...
51单片机-第十四节-AD/DA（XPT2046触摸屏）

51单片机-第十四节-AD/DA（XPT2046触摸屏）

一、AD/DA介绍&#xff1a; AD&#xff1a;模拟-数字转换&#xff0c;将模拟信号转换为计算机可操作的数字信号。 DA&#xff1a;数字-模拟转换&#xff0c;将计算机输出的数字信号转换为模拟信号。 二、运算放大器&#xff1a; 1.介绍&#xff1a; &#xff08;1&#xf…
阅读更多...
给网站加加速！下一代CDN(EdgeOne/边缘安全加速)使用与配置体验

给网站加加速！下一代CDN(EdgeOne/边缘安全加速)使用与配置体验

随着访问量的增加和用户需求的多样化&#xff0c;服务器的带宽有限&#xff0c;面对一些图片数据&#xff0c;显得“力不从心”。CDN技术&#xff0c;就很好的解决了这个问题&#xff0c;但是价格也是用户思考的问题。 EdgeOne不仅继承了传统CDN的核心优势&#xff0c;更在速度…
阅读更多...
uni-app 开发的应用快速构建成鸿蒙原生应用

uni-app 开发的应用快速构建成鸿蒙原生应用

uni-app 是一个使用 Vue.js 开发所有前端应用的框架&#xff0c;它支持编译到 iOS、Android、小程序等多个平台。对于 HarmonyOS&#xff08;鸿蒙系统&#xff09;&#xff0c;uni-app 提供了特定的支持&#xff0c;允许开发者构建鸿蒙原生应用。 一、uni-app 对 HarmonyOS 的支…
阅读更多...
【用户管理 添加用户 超级用户 用户和组】

【用户管理 添加用户 超级用户 用户和组】

用户管理 添加用户超级用户用户和组 添加用户 介绍用户的管理操作 比如&#xff0c;添加一个用户 sudo useradd -m test1 其中&#xff0c;sudo表示管理员身份运行 修改用户密码 sudo passwd test1 删除用户 sudo userdel test 超级用户 1.首次使用时&#xff0c;需要给roo…
阅读更多...
以光塑形：光固化3D打印机原理图文解析

以光塑形：光固化3D打印机原理图文解析

公众号端&#xff1a; 光固化打印机介绍https://mp.weixin.qq.com/s?__bizMzkwMjc0MTE3Mw&mid2247484073&idx1&sn0d0fd026b373b06cd7c340ec8f56a006&chksmc0a1af73f7d62665a632baebbde4e5e00ffb9c6bd31bf547b4a86855d5524535619a6175a428#rd 光固化打印机…
阅读更多...
IDEA上Mybatis介绍和使用

IDEA上Mybatis介绍和使用

MyBatis是一款优秀的持久层框架&#xff0c;用于简化JDBC的开发。 创建项目 在springboot项目中添加Mybatis和MySQL依赖项。 找到数据库选项&#xff0c;点击新建 -> 数据库源&#xff0c;选择MySQL。 输入完成信息后&#xff0c;可以先进行测试&#xff0c;可以成功连接再…
阅读更多...
逻辑回归LogisticRegression

逻辑回归LogisticRegression

一、逻辑回归的基础介绍 逻辑回归是一个分类模型 它可以用来预测某件事发生是否能够发生。分类问题是生活中最常见的问题&#xff1a; 生活中&#xff1a;比如预测上证指数明天是否会上涨&#xff0c;明天某个地区是否会下雨&#xff0c;西瓜是否熟了 金融领域&#xff1a;…
阅读更多...
p20 docker自己commit一个镜像 p21 容器数据卷 p22mysql同步数据(国内镜像被封锁暂时往后放)p23具名挂载和匿名挂载

p20 docker自己commit一个镜像 p21 容器数据卷 p22mysql同步数据(国内镜像被封锁暂时往后放)p23具名挂载和匿名挂载

如何自己commit一个镜像 这里还是先引用一下老师的笔记 关于如何自己commit一个镜像这个问题目前因为从仓库中拉下来的Tomcat里面是没有项目的&#xff0c;所以把webapps.dist里面的拷贝到webapps里面去作为自己的镜像在commit一下 这里用Tomcat举例子首先把镜像拉取下来执…
阅读更多...
MySql数据库---存储过程

MySql数据库---存储过程

存储过程概念 MySQL 5.0 版本开始支持存储过程。 简单的说&#xff0c;存储过程就是一组SQL语句集&#xff0c;功能强大&#xff0c;可以实现一些比较复杂的逻辑功能&#xff0c;类似于JAVA语言中的方法&#xff0c;类似Python中的函数&#xff1b; 存储过就是数据库 SQL 语言…
阅读更多...
多项目管理怎么进行❓看这篇就够了

多项目管理怎么进行❓看这篇就够了

多项目管理是一个复杂而细致的过程&#xff0c;涉及多个项目的同时进行和协调。首先&#xff0c;明确每个项目的目标和范围至关重要。在项目开始之初&#xff0c;应对所有项目进行全面评估&#xff0c;确定其战略价值、影响范围和资源需求。这有助于为每个项目设定清晰的优先级…
阅读更多...
反应香精市场报告：预计2030年全球市场规模将达到264.3亿美元

反应香精市场报告：预计2030年全球市场规模将达到264.3亿美元

“反应香精”通常是指通过在食品或饮料加工过程中发生的物理、化学或酶反应而产生的风味剂。可以有意添加这些香料以增强最终产品的味道、香气或其他感官方面。它们通常用于食品和饮料行业&#xff0c;以保持一致性、提高适口性或创造独特的风味特征。生产工艺香料的方法有多种…
阅读更多...
新网站做谷歌SEO为什么短期内很难看到显著效果？

新网站做谷歌SEO为什么短期内很难看到显著效果？

对于一个全新的网站来说&#xff0c;SEO的效果往往不会在短期内显现。这是因为SEO需要时间来积累权重和信任度。谷歌对新网站通常会有一个观察期&#xff0c;在这段时间内&#xff0c;网站的表现不稳定&#xff0c;排名也会波动较大&#xff0c;这是正常情况&#xff0c;这时候…
阅读更多...
excel表格转换为在线成绩查询怎么制作？

excel表格转换为在线成绩查询怎么制作？

在当前“双减”政策的背景下&#xff0c;学生的考试成绩不再被公开展示&#xff0c;这是对学生隐私的一种保护。然而&#xff0c;这同时也带来了一个新的问题&#xff1a;家长们对于孩子成绩的关切并未减少&#xff0c;他们依然迫切想要了解孩子的学习情况。以往&#xff0c;成…
阅读更多...
使用Provide和Inject设计Vue3插件

使用Provide和Inject设计Vue3插件

使用provide和inject的Vue依赖项注入非常适合构建Vue3插件或避免prop多层传递。 尽管不经常使用它&#xff0c;但是您可以仅使用两个内置方法来实现依赖项注入&#xff1a;provide和inject。 查看Composition API文档&#xff0c;在Vue 3.0中&#xff0c;使用Provide和Inject进…
阅读更多...
深度学习：循环神经网络—RNN的原理

深度学习：循环神经网络—RNN的原理

传统神经网络存在的问题&#xff1f; 无法训练出具有顺序的数据。模型搭建时没有考虑数据上下之间的关系。 RNN神经网络 RNN&#xff08;Recurrent Neural Network&#xff0c;循环神经网络&#xff09;是一种专门用于处理序列数据的神经网络。在处理序列输入时具有记忆性…
阅读更多...
最新文章

Copyright @ 2022~2023