做淘口令的网站,银川商城网站建设,5免费建站网站,php充值网站源码个人主页 #xff1a; 个人主页 个人专栏 #xff1a; 《数据结构》 《C语言》《C》 文章目录 前言一、AVLTree二、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树节点的定义
templateclass 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树的插入可以分为两步
依据二叉搜索树的方式插入新节点调整节点的平衡因子
插入新增节点
第一点很好实现用两个指针变量curparent。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的平衡因子变为0s作为r的右子树的高度不变r的平衡因子不需要改变所以当调整完父节点的平衡因子为0我们不需要向上回溯处理祖先节点的平衡因子。
如上图所示我们在c的左子树插入一个节点c的平衡因子变为-1c作为b的右子树的高度改变了b的平衡因子也需要跟着改变b的平衡因子变为1… 直到某一祖先节点的平衡因子变为0(如在插入一节点在s的左子树那么其祖先节点r的平衡因子就为0)正负2(在t节点的左子树插入一节点那么其祖先s节点的平衡因子变为2)回溯到根节点(上图所示)才能停止。 如上图所示我们在t的右子树插入一个节点t的平衡因子变为1t作为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 subRLsubR- _left parentsubRL- _parent parentsubR- _parent parent- _parent parent- _parent subRpparent- _left subR使subR作为新子数的根节点parent作为t较低左子树的根节点再连接父节点指针即可(要注意此时subRL有可能为空当parent为根节点时pparent为空)此时 t 和 s 的平衡因子为0。 这是对于这个s节点的左单旋那有没有可以概括整个左单旋的模型呢
在这个模型中我们可能会疑惑为什么abc的高度都为h呢这是因为如果当b c ha h-1那么此时 parent的平衡因子已经失衡且无论我们怎么旋转都不能解决失衡问题再如果b h-1c a h此时如果新增节点在b上parent的平衡因子不会改变如果新增节点在c上,subR的平衡因子就会先失衡。所以abc的高度都要相当。 这样我们依据左单旋的模型就可以清晰的写出左单旋的代码但不要忘记我们的节点还有一个父指针要连接父子指针。
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 subLRsubL-_right parentsubRL-_parent parentsubL-_parent parent-_parentparent-_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;}右左双旋(新增节点在较高右子树的左子树上)
这里我们先上用例再上模型。 如下图如果我们在ikmo节点下新增一个节点都会发生右左双旋。 我们新增节点为m节点的左子节点m的平衡因子变为-1n的平衡因子变为-1…p的平衡因子变为-1h的平衡因子变为2。此时h的平衡因子失衡(新增节点位于h节点较高右子树中新增节点又位于p节点的左子树中)。我们需要先对p节点右单旋再对h节点左单旋。
这样我们就可以完成右左双旋的操作。如果我们将新增节点加在i节点的左子节点上那么虽然该树依据需要进行右左双旋的操作h 和 p节点的平衡因子会发生改变。 因此我们不仅需要两个指针parent(指向h节点左单旋)subR(指向p节点右单旋)还需要一个变量记录l节点的平衡因子。当l的平衡因子为1时h的平衡因子为-1p的平衡因子为0。当l的平衡因子为-1时h的平衡因子为0p的平衡因子为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
那么修改后父节点的平衡因子会有三种情况。
父节点的平衡因子本身是0修改后变成正负1此时该子树高度不变不需要向上回溯。 如上图删除o节点对于以n为根节点的子树而言高度不变不需要向上回溯调整平衡因子。父节点的平衡因子本身不为0删除较高子树的节点修改后变成0此时该子树高度发生改变需要向上回溯调节祖先节点的平衡因子 如上图删除t节点s节点的平衡因子变为0对于以s节点为根节点的子树而言其高度减少需要向上回溯p节点的平衡因子变为-1对于以p节点为根节点的子树而言其高度不变不需要向上回溯。父节点的平衡因子本身不为0删除较低子树的节点修改后平衡因子变成正负2此时该子树失衡需要旋转。我们现将parent(父节点)的较高子节点记录为sub。此时我们又可以分成三种情况。 sub的平衡因子为0此时我们只需要单旋处理即可不需要向上调整平衡因子。 如果我们是连续删除egf节点那么b节点作为d节点中较高节点(左子节点)的平衡因子为0需要右单旋来完成平衡。 2.sub的平衡因子不为0prev(父节点)的平衡因子与sub(父节点的子节点中较高子节点)平衡因子同号只需要一个单旋来完成平衡但该子树的高度发生改变需要向上回溯调节祖先节点的平衡因子。 如上图我们删除节点q此时r节点的平衡因子为2s节点的平衡因子为1我们需要左单旋来完成平衡但新的以s节点为根的子树高度变低了我们需要向上回溯调整p节点的平衡因子此时p的平衡因子为-1。对于模型中sub的左子树部分可能有人会疑惑为什么高度为h-1而不是h如果sub左子树部分高度为h该模型不就是情况1的模型。 3.sub的平衡因子不为0prev的平衡因子与sub的平衡因子异号此时需要执行双旋来完成平衡且完成双旋后高度降低需要向上回溯调节祖先节点的平衡因子。 如上图我们连续删除acegt节点此时h节点的平衡因子为2p节点的平衡因子为-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 stringusing namespace std;templateclass 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;
};templateclass T
class AVLTree
{
public:typedef AVLTreeNodeT 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.hvoid test1()
{//vectorint nums({ 16,3,7,11,9,26,18,14,15 });vectorint nums({ 4,2,6,1,3,5,15,7,16,14 });AVLTreeint 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;vectorint v(N);srand(time(0));for (int i 0; i N; i){v[i] rand();cout v[i] endl;}AVLTreeint 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);AVLTreechar 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()
{AVLTreeint 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插入和删除的理解。感谢支持
