数据结构：AVLTree的插入和删除的实现

在这里插入图片描述

个人主页 ： 个人主页
个人专栏 ： 《数据结构》 《C语言》《C++》

文章目录

  • 前言
  • 一、AVLTree
  • 二、AVLTree的插入
    • 插入新增节点
    • 调整平衡因子
    • 旋转
      • 左单旋(新增节点位于较高右子树的右侧)
      • 右单旋(新增节点位于较高左子树的左侧)
      • 右左双旋(新增节点在较高右子树的左子树上)
      • 左右双旋(新增节点在较高左子树的右子树上)
  • 三、AVLTree的删除
    • 删除节点
    • 调节平衡因子
  • 四、检查AVLTree的正确性
  • 代码实现
  • 总结

前言

本篇博客作为AVL树的插入和删除的实现。如果代码实现有问题，还请大佬们指出。

一、AVLTree

二叉搜索树虽然可以缩短查找的效率，但如果数据有序或者接近有序，二叉搜索树将退化成单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两个俄罗斯的数学家G.M.Adelson-Velskil和E.M.Landis在1962年发明了一种解决上述问题的方法：当二叉搜索树中插入新节点后，如果能保证每个节点的左右子树高度之差的绝对值不超过1，即可降低树的高度，从而减少平均搜索长度。
也就是说，一颗AVL树或者空树是具有以下性质的二叉树：

  • 它的左右子树都是AVL树
  • 左右子树高度之差(平衡因子)的绝对值不超过1(-1 \ 0 \ 1)。[ 平衡因子 = 右子树高度 - 左子树高度 ]

如下图所示：
在这里插入图片描述

如果一颗搜索二叉树是高度平衡的，它就是AVL树，如果它有N个节点，其高度为logn，搜索的时间复杂度为logn。

其中AVL树节点的定义：

template<class T>
struct AVLTreeNode
{AVLTreeNode(const T data = T()):_left(nullptr),_right(nullptr),_parent(nullptr),_data(data),_bf(0){}AVLTreeNode* _left;AVLTreeNode* _right;AVLTreeNode* _parent;T _data;int _bf;
};

其中_parent指针为指向父节点的指针，保证在插入和删除时，可以通过该指针进行回溯寻找父节点。(当然也可以不用该指针，转而在插入和删除的过程中，使用栈保存路径来进行回溯)

二、AVLTree的插入

AVL树的插入可以分为两步：

  1. 依据二叉搜索树的方式插入新节点
  2. 调整节点的平衡因子

插入新增节点

第一点很好实现，用两个指针变量cur，parent。cur来与新增节点比较，如果cur大于新增节点，cur就去左子树，如果cur小于新增节点，cur就去右子树，直到cur走的nullptr，表示新增节点要插入的位置。parent作为cur的父节点。需要注意的是，如果树为空，要进行特殊处理。

		// 树为空if (_root == nullptr) {_root = new Node(data);return true;}// 寻找新增节点要插入的位置Node* cur = _root;Node* parent = nullptr;while (cur) {parent = cur;if (cur->_data < data){cur = cur->_right;}else if (cur->_data > data){cur = cur->_left;}else{return false;}}// 插入新增节点cur = new Node(data);cur->_parent = parent;if (parent->_data > data){parent->_left = cur;}else{parent->_right = cur;}

调整平衡因子

第二点调整平衡因子就有些麻烦，因为对于插入节点的祖先节点而言，它们的平衡因子都可能改变甚至失衡。
如下图所示：
在这里插入图片描述

对于上图中新增节点的祖先节点的平衡因子都发生改变。那么我们要如何处理平衡因子呢？

(平衡因子 = 右子树高度 - 左子树高度)

  • 如果插入节点是父节点的左子树(左子树高度+1)，那么父节点的平衡因子-1
  • 如果插入节点是父节点的右子树(右子树高度+1)，那么父节点的平衡因子+1

经过上述调整，父节点的平衡因子就会分成三种情况 0(该子树高度不变)，正负1(该子树的高度改变)，正负2(该子树已经失衡)。
在这里插入图片描述
如上图所示，我们在s的左子树插入一个节点，s的平衡因子变为0，s作为r的右子树的高度不变，r的平衡因子不需要改变，所以当调整完，父节点的平衡因子为0，我们不需要向上回溯处理祖先节点的平衡因子。
在这里插入图片描述

如上图所示，我们在c的左子树插入一个节点，c的平衡因子变为-1，c作为b的右子树的高度改变了，b的平衡因子也需要跟着改变，b的平衡因子变为1… 直到某一祖先节点的平衡因子变为0(如在插入一节点在s的左子树，那么其祖先节点r的平衡因子就为0)，正负2(在t节点的左子树插入一节点，那么其祖先s节点的平衡因子变为2)，回溯到根节点(上图所示)才能停止。
在这里插入图片描述
如上图所示，我们在t的右子树插入一个节点，t的平衡因子变为1，t作为s的右子树的高度改变了，s的平衡因子变为2，此时s的平衡因子失衡。此时我们就要对s这一子树进行旋转。

		while (parent){if (parent->_left == cur) // 新增节点是父节点的左子节点{parent->_bf--;}else if(parent->_right == cur) // 新增节点是父节点的左子节点{parent->_bf++;}if (parent->_bf == 0) // 调整平衡因子后，父节点的平衡因子为0{break;}else if (parent->_bf == 1 || parent->_bf == -1) // 调整平衡因子后，父节点的平衡因子为正负1{cur = parent;parent = cur->_parent;}else if(parent->_bf == 2 || parent->_bf == -2) // 调整平衡因子后，父节点的平衡因子为正负2{// 失衡处理break;}}

旋转

对于失衡节点的旋转，我们可以分为四种情况左单旋，右单旋，左右双旋，右左双旋。
对于下图s的平衡因子失衡，我们就可以对于左单旋，使其回复平衡。
在这里插入图片描述

左单旋(新增节点位于较高右子树的右侧)

如下图s节点而言，新增节点位于其较高右子树的右侧。我们就需要对s节点进行左单旋。

在这里插入图片描述
那么如何进行左单旋呢？
我们先将定义四个指针pparent(r节点，s节点父节点)，parent(s节点)，subR(t节点，也就是s节点的右子树的根节点)，subRL(t节点的左子树的根节点，在这里为nullptr)。此时我们只需要使parent->_right = subRL，subR-> _left = parent，subRL-> _parent = parent，subR-> _parent = parent-> _parent， parent-> _parent = subR，pparent-> _left = subR，使subR作为新子数的根节点，parent作为t较低左子树的根节点，再连接父节点指针即可(要注意此时subRL有可能为空，当parent为根节点时，pparent为空)，此时 t 和 s 的平衡因子为0。
在这里插入图片描述
这是对于这个s节点的左单旋，那有没有可以概括整个左单旋的模型呢？
在这里插入图片描述

在这个模型中，我们可能会疑惑为什么a，b，c的高度都为h呢？这是因为如果当b = c = h，a = h-1，那么此时
parent的平衡因子已经失衡，且无论我们怎么旋转都不能解决失衡问题，再如果b = h-1，c = a = h，此时如果新增节点在b上，parent的平衡因子不会改变，如果新增节点在c上,subR的平衡因子就会先失衡。所以a，b，c的高度都要相当。
这样我们依据左单旋的模型就可以清晰的写出左单旋的代码，但不要忘记我们的节点还有一个父指针，要连接父子指针。

void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;subR->_left = parent;if (subRL != nullptr){subRL->_parent = parent;}Node* pparent = parent->_parent;if (pparent == nullptr) // 处理根节点{_root = subR;}else{if (pparent->_left == parent){pparent->_left = subR;}else if (pparent->_right == parent){pparent->_right = subR;}}subR->_parent = pparent;parent->_parent = subR;parent->_bf = 0;subR->_bf = 0;}

右单旋(新增节点位于较高左子树的左侧)

右单旋与左单旋类似，这里我们就直接上模型了。
在这里插入图片描述
如上图所示，我们只需要使parent-> _left = subLR，subL->_right = parent，subRL->_parent = parent，subL->_parent = parent->_parent，parent->_parent = subL再将parent原先的父节点与该子树新的根节点subL连接即可。

void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;subL->_right = parent;if (subLR != nullptr){subLR->_parent = parent;}Node* pparent = parent->_parent;if (parent->_parent == nullptr){_root = subL;}else{if (pparent->_left == parent){pparent->_left = subL;}else if (pparent->_right == parent){pparent->_right = subL;}}subL->_parent = parent->_parent;parent->_parent = subL;subL->_bf = 0;parent->_bf = 0;}

右左双旋(新增节点在较高右子树的左子树上)

这里我们先上用例，再上模型。
如下图，如果我们在i，k，m，o节点下新增一个节点，都会发生右左双旋。
在这里插入图片描述
我们新增节点为m节点的左子节点，m的平衡因子变为-1，n的平衡因子变为-1…p的平衡因子变为-1，h的平衡因子变为2。此时h的平衡因子失衡(新增节点位于h节点较高右子树中，新增节点又位于p节点的左子树中)。我们需要先对p节点右单旋，再对h节点左单旋。
在这里插入图片描述

这样我们就可以完成右左双旋的操作。如果我们将新增节点加在i节点的左子节点上，那么虽然该树依据需要进行右左双旋的操作，h 和 p节点的平衡因子会发生改变。

在这里插入图片描述

因此，我们不仅需要两个指针parent(指向h节点，左单旋)，subR(指向p节点，右单旋)，还需要一个变量记录l节点的平衡因子。当l的平衡因子为1时，h的平衡因子为-1，p的平衡因子为0。当l的平衡因子为-1时，h的平衡因子为0，p的平衡因子为1。

在这里插入图片描述

这样我们就可以清楚的依据右左双旋模型来实现代码，但不要忘记将新子树的根节点与旧父节点相连接。

void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(subR);RotateL(parent);if (bf == 1){parent->_bf = -1;}else if (bf == -1){subR->_bf = 1;}}

左右双旋(新增节点在较高左子树的右子树上)

左右双旋与右左双旋类似，这里就直接上模型了。
在这里插入图片描述
我们先对subL节点左单旋，再对parent节点右单旋，最后依据subLR节点的平衡因子来修改parent节点，subL节点的平衡因子

void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(subL);RotateR(parent);if (bf == -1){parent->_bf = 1;}else if(bf == 1){subL->_bf = -1;}}

至此四种旋转就结束了，那么什么时候使用那种旋转呢？
在这里插入图片描述
依据上图判断parent节点与cur节点的平衡因子即可知晓使用那种平衡。

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){RotateLR(parent);}else if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent);}// 旋转后，该子树就不需要再向上回溯break;

三、AVLTree的删除

AVRTree的删除与二叉搜索树类似，也可以分成三种情况来看(实际情况一与情况二在实现上可以合并)

  • 情况一：要删除节点为叶子节点，则直接删除，调节平衡因子
  • 情况二：要删除节点有一个子节点，将该节点的父节点原来指向该节点的指针，直接指向该节点的子节点，删除该节点，调节平衡因子
  • 情况三：要删除节点有两个子节点，找该节点在中序遍历中的直接前驱节点，将该节点与前驱节点直接替换，该前驱节点必定只有一个右子节点或没有子节点，按照情况二删除前驱节点，调整平衡因子。

删除节点

我们将情况一和情况而合并为同一种情况处理。这种情况删除节点很好处理，我们只需找到该节点让该节点的父节点原指向该节点的指针指向该节点的子节点即可。但情况三有一个问题，当我们找到该节点后，如何找该节点在中序遍历中的直接前驱节点？
如下图所示：该图中序遍历结果就是字母a到字母t的顺序
在这里插入图片描述
如果我们要删除h节点，那h节点在中序遍历中的直接前驱就是g节点，如果删除的是p节点，那么前驱节点就是o节点，如果删除d节点，前驱节点就是c节点。那么有什么发现吗？一个节点的“前驱节点”就是该节点左子树的最右节点，毕竟中序遍历是左 根 右，左子树的最后一个节点就是该节点的“前驱节点”。

		Node* cur = _root;    // 要删除的节点Node* prev = nullptr; // 要删除节点的父节点Node* sub = nullptr;  // 要删除节点的子节点int flag = 0; // flag = 1表示删除节点是右子节点   flag = -1表示删除节点是左节点while (cur != nullptr && cur->_data != data){if (cur->_data > data){cur = cur->_left;}else if (cur->_data < data){cur = cur->_right;}}if (cur == nullptr){return false;}prev = cur->_parent;// 处理有两个子节点if (cur->_left != nullptr && cur->_right != nullptr){// 将cur 与 中序次序的直接前序替换sub = cur->_left;while (sub->_right != nullptr){sub = sub->_right;}prev = sub->_parent;cur->_data = sub->_data;cur = sub;// prev->_right = sub->_left;}// 处理有单个子节点if (cur->_left != nullptr){sub = cur->_left;}else{sub = cur->_right;}if (prev == nullptr) // 删除的是根节点{delete cur;cur = nullptr;_root = sub;if(sub != nullptr)sub->_parent = nullptr;}else{if (sub != nullptr){sub->_parent = prev;}if (prev->_left == cur){flag = -1;prev->_left = sub;}else{flag = 1;prev->_right = sub;}delete cur;cur = nullptr;// 调节平衡因子}

调节平衡因子

依据平衡因子 = 右子树高度 - 左子树高度

  • 如果删除的节点是父节点的左子节点，那么父节点的平衡因子+1
  • 如果删除的节点是父节点的右子节点，那么父节点的平衡因子-1

那么修改后，父节点的平衡因子会有三种情况。

  1. 父节点的平衡因子本身是0，修改后变成正负1，此时该子树高度不变，不需要向上回溯。
    在这里插入图片描述
    如上图删除o节点，对于以n为根节点的子树而言高度不变，不需要向上回溯调整平衡因子。
  2. 父节点的平衡因子本身不为0，删除较高子树的节点，修改后变成0，此时该子树高度发生改变，需要向上回溯调节祖先节点的平衡因子
    在这里插入图片描述
    如上图删除t节点，s节点的平衡因子变为0，对于以s节点为根节点的子树而言，其高度减少，需要向上回溯，p节点的平衡因子变为-1，对于以p节点为根节点的子树而言，其高度不变，不需要向上回溯。
  3. 父节点的平衡因子本身不为0，删除较低子树的节点，修改后平衡因子变成正负2，此时该子树失衡，需要旋转。我们现将parent(父节点)的较高子节点记录为sub。此时我们又可以分成三种情况。
  1. sub的平衡因子为0，此时我们只需要单旋处理即可，不需要向上调整平衡因子。
    在这里插入图片描述
    如果我们是连续删除e，g，f节点，那么b节点作为d节点中较高节点(左子节点)的平衡因子为0，需要右单旋来完成平衡。
    2.sub的平衡因子不为0，prev(父节点)的平衡因子与sub(父节点的子节点中较高子节点)平衡因子同号，只需要一个单旋来完成平衡，但该子树的高度发生改变，需要向上回溯，调节祖先节点的平衡因子。
    在这里插入图片描述
    如上图我们删除节点q，此时r节点的平衡因子为2，s节点的平衡因子为1，我们需要左单旋来完成平衡，但新的以s节点为根的子树高度变低了，我们需要向上回溯，调整p节点的平衡因子，此时p的平衡因子为-1。对于模型中sub的左子树部分，可能有人会疑惑为什么高度为h-1，而不是h？如果sub左子树部分高度为h，该模型不就是情况1的模型。
    3.sub的平衡因子不为0，prev的平衡因子与sub的平衡因子异号，此时需要执行双旋来完成平衡，且完成双旋后高度降低，需要向上回溯，调节祖先节点的平衡因子。
    在这里插入图片描述
    如上图我们连续删除a，c，e，g，t节点，此时h节点的平衡因子为2，p节点的平衡因子为-1，我们需要右左双旋来完成平衡，先对sub右旋，再对prev左旋，旋转后，此时以l为根节点的新子树高度减小，需要向上调整，但l节点恰好是整个树的根节点。不用向上调整。

至此删除节点后调节平衡因子的所以情况都以说完。

			while (prev != nullptr) // 调节平衡因子{if (flag == -1) // 如果子节点删除完成后，其父节点的左右子节点都为nullptr，此时直接判断perv->_left == cur则无法区分。{prev->_bf++; }else if (flag == 1){prev->_bf--;}if (prev->_bf == -1 || prev->_bf == 1){break; // 该子树的高度不变}else if (prev->_bf != 0) // prev->_bf == 2 || prev->_bf == -2{// 使 sub 表示最高子树if (prev->_bf > 0){sub = prev->_right;}else{sub = prev->_left;}if (sub->_bf == 0) // 该子树平衡后高度不变{if (prev->_left == sub){RotateR(prev);sub->_bf = 1;prev->_bf = -1;}else{RotateL(prev);sub->_bf = -1;prev->_bf = 1;}break;}else if ((prev->_bf) * (sub->_bf) > 0) // 同号  {if (sub == prev->_right){RotateL(prev);}else if (sub == prev->_left){RotateR(prev);}prev = sub->_parent;}else if ((prev->_bf) * (sub->_bf) < 0) // 异号  {if (sub == prev->_right){RotateRL(prev);}else if (sub == prev->_left){RotateLR(prev);}sub = sub->_parent;prev = sub->_parent;}}else if (prev->_bf == 0){sub = prev;prev = prev->_parent;}//  更新 flag 的值if (prev != nullptr){if (prev->_left == sub){flag = -1;}else if (prev->_right == sub){flag = 1;}}}

四、检查AVLTree的正确性

验证AVLTree的正确分为两步：

  • 验证其是否是二叉搜索树，打印中序遍历结果，看结果序列是否是升序序列
  • 验证其是否是平衡数，每个子节点的高度差不大于1，节点的平衡因子是否正确。

这两步都非常简单，我们只需递归比较每个节点的左右子树的高度，看是否符合定义即可。

	bool isAVLTEree(){return _isAVLTree(_root);}bool _isAVLTree(Node* root){if (root == nullptr)return true;int leftHeight = _Hight(root->_left);int rightHeight = _Hight(root->_right);if(rightHeight - leftHeight != root->_bf){cout << root->_data << "平衡因子失衡" << endl;}return abs(leftHeight - rightHeight) >= 2 ? false : true;}size_t _Hight(Node* root){if (root == nullptr){return 0;}return max(_Hight(root->_left), _Hight(root->_right)) + 1;}

代码实现

AVLTree.h文件存放AVLTree插入删除的实现。
test.cpp文件存放的是测试用例。

#pragma once
#include <iostream>
#include <assert.h>
#include <vector>
#include <stdlib.h>
#include <time.h>
#include <string>using namespace std;template<class T>
struct AVLTreeNode
{AVLTreeNode(const T data = T()):_left(nullptr),_right(nullptr),_parent(nullptr),_data(data),_bf(0){}AVLTreeNode* _left;AVLTreeNode* _right;AVLTreeNode* _parent;T _data;int _bf;
};template<class T>
class AVLTree
{
public:typedef AVLTreeNode<T> Node;AVLTree():_root(nullptr){}bool insert(const T data){if (_root == nullptr){_root = new Node(data);return true;}Node* cur = _root;Node* parent = nullptr;while (cur){parent = cur;if (cur->_data < data){cur = cur->_right;}else if (cur->_data > data){cur = cur->_left;}else{return false;}}cur = new Node(data);cur->_parent = parent;if (parent->_data > data){parent->_left = cur;}else{parent->_right = cur;}while (parent){if (parent->_left == cur){parent->_bf--;}else{parent->_bf++;}if (parent->_bf == 0){break;}else if (parent->_bf == 1 || parent->_bf == -1){cur = parent;parent = cur->_parent;}else{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){RotateLR(parent);}else if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent);}break;}}return true;}bool Erase(const T data){Node* cur = _root;Node* prev = nullptr;Node* sub = nullptr;int flag = 0; // flag = 1表示删除节点是右子节点   flag = -1表示删除节点是左节点while (cur != nullptr && cur->_data != data){if (cur->_data > data){cur = cur->_left;}else if (cur->_data < data){cur = cur->_right;}}if (cur == nullptr){return false;}prev = cur->_parent;// 处理有两个子节点if (cur->_left != nullptr && cur->_right != nullptr){// 将cur 与 中序次序的直接前序替换sub = cur->_left;while (sub->_right != nullptr){sub = sub->_right;}prev = sub->_parent;cur->_data = sub->_data;cur = sub;// prev->_right = sub->_left;}// 处理有单个子节点if (cur->_left != nullptr){sub = cur->_left;}else{sub = cur->_right;}if (prev == nullptr) // 删除的是根节点{delete cur;cur = nullptr;_root = sub;if(sub != nullptr)sub->_parent = nullptr;}else{if (sub != nullptr){sub->_parent = prev;}if (prev->_left == cur){flag = -1;prev->_left = sub;}else{flag = 1;prev->_right = sub;}delete cur;cur = nullptr;while (prev != nullptr) // 调节平衡因子{if (flag == -1) // 如果子节点删除完成后，其父节点的左右子节点都为nullptr，此时直接判断perv->_left == cur则无法区分。{prev->_bf++; }else if (flag == 1){prev->_bf--;}if (prev->_bf == -1 || prev->_bf == 1){break; // 该子树的高度不变}else if (prev->_bf != 0) // prev->_bf == 2 || prev->_bf == -2{// 使 sub 表示最高子树if (prev->_bf > 0){sub = prev->_right;}else{sub = prev->_left;}if (sub->_bf == 0) // 该子树平衡后高度不变{if (prev->_left == sub){RotateR(prev);sub->_bf = 1;prev->_bf = -1;}else{RotateL(prev);sub->_bf = -1;prev->_bf = 1;}break;}else if ((prev->_bf) * (sub->_bf) > 0) // 同号  {if (sub == prev->_right){RotateL(prev);}else if (sub == prev->_left){RotateR(prev);}prev = sub->_parent;}else if ((prev->_bf) * (sub->_bf) < 0) // 异号  {if (sub == prev->_right){RotateRL(prev);}else if (sub == prev->_left){RotateLR(prev);}sub = sub->_parent;prev = sub->_parent;}}else if (prev->_bf == 0){sub = prev;prev = prev->_parent;}//  更新 flag 的值if (prev != nullptr){if (prev->_left == sub){flag = -1;}else if (prev->_right == sub){flag = 1;}}}}return true;}void InOrder(){_InOrder(_root);}bool isAVLTEree(){return _isAVLTree(_root);}size_t Hight(){return _Hight(_root);}
private:bool _isAVLTree(Node* root){if (root == nullptr)return true;int leftHeight = _Hight(root->_left);int rightHeight = _Hight(root->_right);if(rightHeight - leftHeight != root->_bf){cout << root->_data << "平衡因子失衡" << endl;}return abs(leftHeight - rightHeight) >= 2 ? false : true;}size_t _Hight(Node* root){if (root == nullptr){return 0;}return max(_Hight(root->_left), _Hight(root->_right)) + 1;}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_data << " ";_InOrder(root->_right);}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;subR->_left = parent;if (subRL != nullptr){subRL->_parent = parent;}Node* pparent = parent->_parent;if (pparent == nullptr){_root = subR;}else{if (pparent->_left == parent){pparent->_left = subR;}else if (pparent->_right == parent){pparent->_right = subR;}}subR->_parent = pparent;parent->_parent = subR;parent->_bf = 0;subR->_bf = 0;}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;subL->_right = parent;if (subLR != nullptr){subLR->_parent = parent;}Node* pparent = parent->_parent;if (parent->_parent == nullptr){_root = subL;}else{if (pparent->_left == parent){pparent->_left = subL;}else if (pparent->_right == parent){pparent->_right = subL;}}subL->_parent = parent->_parent;parent->_parent = subL;subL->_bf = 0;parent->_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){parent->_bf = 1;}else if(bf == 1){subL->_bf = -1;}}void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(subR);RotateL(parent);if (bf == 1){parent->_bf = -1;}else if (bf == -1){subR->_bf = 1;}}Node* _root;
};

// test.cpp 文件
#include "AVLTree.h"void test1()
{//vector<int> nums({ 16,3,7,11,9,26,18,14,15 });vector<int> nums({ 4,2,6,1,3,5,15,7,16,14 });AVLTree<int> tree;for (auto val : nums){tree.insert(val);}tree.InOrder();cout << endl;cout << tree.isAVLTEree() << endl;cout << tree.Hight() << endl;
}void test2()
{const int N = 1000;vector<int> v(N);srand(time(0));for (int i = 0; i < N; i++){v[i] = rand();cout << v[i] << endl;}AVLTree<int> tree;for (auto val : v){tree.insert(val);//cout << "insert:" << val << "->" << tree.isAVLTEree() << endl;}cout << tree.Hight() << endl;cout << tree.isAVLTEree() << endl;int i = 0;for (auto val : v){tree.Erase(val);cout << "Erase:" << val << "->" << i++ << endl;}cout << tree.isAVLTEree() << endl;}void test3()
{string str("abcdefghijklmnopqrst");AVLTree<char> t;for (auto data : str){t.insert(data);}for (int i = 0; i < str.size(); i++){t.Erase(str[i]);}t.InOrder();cout << t.isAVLTEree() << endl;
}void test4()
{AVLTree<int> t;t.insert(1);t.insert(3);t.insert(2);t.insert(4);for (int i = 0; i < 5; i++){t.Erase(i);}cout << t.isAVLTEree() << endl;
}
int main()
{test2();return 0;
}

2000个数据测试结果。
在这里插入图片描述

20000个数据结果
在这里插入图片描述
200000个测试结果

在这里插入图片描述
2000000个数据测试结果。

在这里插入图片描述

总结

以上就是我对于AVLTree插入和删除的理解。感谢支持！！！
在这里插入图片描述

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

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

相关文章

golang 2018，go 1.19安装Gin

golang 2018，go 1.19安装Gin

GOPROXYhttps://mirrors.aliyun.com/goproxy/ 一致提示URL不能有点&#xff0c;给我整郁闷了&#xff0c;换了这个地址好了 但是一致提示zip的包问题&#xff0c;最后还是不行又换回七牛 NEWBEE&#xff01; [GIN-debug] Environment variable PORT is undefined. Using por…
阅读更多...
Django中如何创建表关系，请求生命周期流程图

Django中如何创建表关系，请求生命周期流程图

Django中ORM创建表关系 如何创建表关系(一对一 &#xff0c; 一对多 &#xff0c; 多对多) 图书表&#xff0c;出版社表&#xff0c;作者表&#xff0c;作者详情表 换位思考法判断表关系 图书表和出版社表 >>> 一对多 >>> 图书表是多&#xff0c;出…
阅读更多...
深入了解SpringMvc接收数据

深入了解SpringMvc接收数据

目录 一、访问路径&#xff08;RequestMapping&#xff09; 1.1 访问路径注解作用域 1.2 路径精准&#xff08;模糊&#xff09;匹配 1.3 访问路径限制请求方式 1.4 进阶访问路径请求注解 1.5 与WebServlet的区别 二、接收请求数据 2.1 请求param参数 2.2 请求路径参数 2.3 请求…
阅读更多...
消息中心常见解决方案分享

消息中心常见解决方案分享

解决方案 1、问题2、设计3、流程 看了大部分的消息中心解决方案&#xff0c;发现大家的中心思想都大差不差&#xff0c;区别基本都是在符合自身业务场景的做了一些定制化处理。本文为我对消息中心基本骨架的知识梳理&#xff0c;亦在帮助大家对消息中心设计有一个基本的理解。 …
阅读更多...
【Python】AppUI自动化—appium自动化开发环境部署、APP测试案例（17）上

【Python】AppUI自动化—appium自动化开发环境部署、APP测试案例（17）上

文章目录 一.appium简介1.什么是appium2.appium 的工作原理3.APP类型4.APP页面布局 二,appium开发环境部署&#xff08;python环境&#xff09;1.下载安装环境1.1.下载安装所需环境1.2.Appium-desktop&#xff08; Appium-Server-GUI &#xff09;配置1.3.Appium-Inspector 配置…
阅读更多...
ablation study

ablation study

文章目录 ablation study1、消融实验思想是什么&#xff1f;2、消融实验意义3、消融实验应用场景举例 ablation study 1、消融实验思想是什么&#xff1f; “消融实验”&#xff08;ablation study&#xff09;通常指的是通过逐步移除系统的一部分来评估该系统的贡献。这种方法…
阅读更多...
GIS入门，xyz地图瓦片是什么，xyz数据格式详解，如何发布离线XYZ瓦片到nginx或者tomcat中

GIS入门，xyz地图瓦片是什么，xyz数据格式详解，如何发布离线XYZ瓦片到nginx或者tomcat中

XYZ介绍 XYZ瓦片是一种在线地图数据格式，由goole公司开发。 与其他瓦片地图类似，XYZ瓦片将地图数据分解为一系列小的图像块，以提高地图显示效率和性能。 XYZ瓦片提供了一种开放的地图平台，使开发者可以轻松地将地图集成到自己的应用程序中。同时，它还提供了高分辨率图像和…
阅读更多...
ChatGPT 4 分析天猫双十一历年成交额趋势情况

ChatGPT 4 分析天猫双十一历年成交额趋势情况

收集历年的双十一成交额数据如下： 年份成交额：亿元20090.520109.362011
阅读更多...
【Java】定时任务 - Timer/TimerTask 源码原理解析

【Java】定时任务 - Timer/TimerTask 源码原理解析

一、背景及使用 日常实现各种服务端系统时&#xff0c;我们一定会有一些定时任务的需求。比如会议提前半小时自动提醒&#xff0c;异步任务定时/周期执行等。那么如何去实现这样的一个定时任务系统呢&#xff1f; Java JDK提供的Timer类就是一个很好的工具&#xff0c;通过简单…
阅读更多...
01:2440----点灯大师

01:2440----点灯大师

目录 一:点亮一个LED 1:原理图 2:寄存器 3:2440的框架和启动过程 A:框架 B:启动过程 4:代码 5:ARM知识补充 6:c语言和汇编的应用 A:代码 B:分析汇编语言 C:内存空间 7:内部机制 二:点亮2个灯 三:流水灯 四:按键控制LED 1:原理图 2:寄存器配置 3:代码 一:点…
阅读更多...
汽车操纵稳定性matlab仿真

汽车操纵稳定性matlab仿真

1、内容简介 略 14-可以交流、咨询、答疑 2、内容说明 汽车操纵稳定性matlab仿真&#xff0c;包含完整的论文 操纵动力学、两自由度 摘要&#xff1a;当今&#xff0c;仿真技术日益广泛地应用于汽车工程领域&#xff0c;操纵稳定性研究越来越多地使用成熟的计算机仿真理论…
阅读更多...
MongoDB基础知识~

MongoDB基础知识~

引入MongoDB&#xff1a; 在面对高并发&#xff0c;高效率存储和访问&#xff0c;高扩展性和高可用性等的需求下&#xff0c;我们之前所学习过的关系型数据库(MySql,sql server…)显得有点力不从心&#xff0c;而这些需求在我们的生活中也是随处可见的&#xff0c;例如在社交中…
阅读更多...
高防CDN：护航网络安全的卓越之选

高防CDN：护航网络安全的卓越之选

在当今数字化时代&#xff0c;网络攻击与日俱增&#xff0c;为了确保网站和应用程序的稳定运行&#xff0c;高防CDN&#xff08;高防御内容分发网络&#xff09;应运而生。选择高防CDN的理由不仅源于其强大的防护性能&#xff0c;还体现了其与硬件防火墙异曲同工的奥妙。 选择高…
阅读更多...
【蓝桥杯软件赛 零基础备赛20周】第3周——填空题

【蓝桥杯软件赛 零基础备赛20周】第3周——填空题

报名明年4月蓝桥杯软件赛的同学们&#xff0c;如果你是大一零基础&#xff0c;目前懵懂中&#xff0c;不知该怎么办&#xff0c;可以看看本博客系列&#xff1a;备赛20周合集 20周的完整安排请点击&#xff1a;20周计划 文章目录 00. 2023年第14届参赛数据0. 上一周答疑1. 填空…
阅读更多...
进亦忧，退亦忧，Github Copilot 集成进入 Visual Studio 带来的思考

进亦忧，退亦忧，Github Copilot 集成进入 Visual Studio 带来的思考

开篇想到《岳阳楼记》的结尾&#xff1a; 不以物喜&#xff0c;不以己悲&#xff1b;居庙堂之高则忧其民&#xff1b;处江湖之远则忧其君。是进亦忧&#xff0c;退亦忧。然则何时而乐耶&#xff1f;其必曰&#xff1a;“先天下之忧而忧&#xff0c;后天下之乐而乐”乎。未来30…
阅读更多...
【信息安全原理】——传输层安全（学习笔记）

【信息安全原理】——传输层安全（学习笔记）

&#x1f4d6; 前言&#xff1a;为保证网络应用&#xff0c;特别是应用广泛的Web应用数据传输的安全性&#xff08;机密性、完整性和真实性&#xff09;&#xff0c;可以在多个网络层次上采取安全措施。本篇主要介绍传输层提供应用数据安全传输服务的协议&#xff0c;包括&…
阅读更多...
python异常、模块与包

python异常、模块与包

1.异常 异常&#xff1a;当检测到一个错误时&#xff0c;Python解释器就无法继续执行了&#xff0c;反而出现了一些错误的提示&#xff0c;这就是所谓的“异常”&#xff0c;也就是我们常说的BUG。 1.1捕获异常 基本语法&#xff1a; try:可能发生错误代码 except:如果出现…
阅读更多...
数据分析实战 | SVM算法——病例自动诊断分析

数据分析实战 | SVM算法——病例自动诊断分析

目录 一、数据分析及对象 二、目的及分析任务 三、方法及工具 四、数据读入 五、数据理解 六、数据准备 七、模型训练 八、模型应用及评价 一、数据分析及对象 CSV文件——“bc_data.csv” 数据集链接&#xff1a;https://download.csdn.net/download/m0_70452407/88…
阅读更多...
阿里云国际站：全球加速GA

阿里云国际站：全球加速GA

文章目录 一、前言 二、阿里云全球加速的概念 三、阿里云全球加速的功能优势 四、阿里云全球加速的原理 五、阿里云全球加速的应用场景 六、写在最后 一、前言 随着互联网的快速发展&#xff0c;网站速度已经成为了用户访问体验的一个重要指标。阿里云加速作为一种新的技…
阅读更多...
黑马程序员微服务Docker实用篇

黑马程序员微服务Docker实用篇

Docker实用篇 0.学习目标 1.初识Docker 1.1.什么是Docker 微服务虽然具备各种各样的优势&#xff0c;但服务的拆分通用给部署带来了很大的麻烦。 分布式系统中&#xff0c;依赖的组件非常多&#xff0c;不同组件之间部署时往往会产生一些冲突。在数百上千台服务中重复部署…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023