黑糖不苦还做网站么,建设征婚网站,旅游电子商务网站设计,站长网站统计目录 AVL的概念#xff1a;
AVL树的实现#xff1a;
AVL树的结构#xff1a;
AVL树的插⼊#xff1a;
平衡因⼦更新#xff1a;
旋转#xff1a;
AVL树的其他功能:
AVL树平衡检测:
测试代码*2:
源代码#xff1a;
KV结构#xff1a;
源代码#xff1a; AVL…目录 AVL的概念
AVL树的实现
AVL树的结构
AVL树的插⼊
平衡因⼦更新
旋转
AVL树的其他功能:
AVL树平衡检测:
测试代码*2:
源代码
KV结构
源代码 AVL的概念 AVL树是最先发明的⾃平衡⼆叉查找树AVL是⼀颗空树或者具备下列性质的⼆叉搜索树它的 左右⼦树都是AV树且左右⼦树的⾼度差的绝对值不超过1。AVL树是⼀颗⾼度平衡搜索⼆叉树 通过控制⾼度差去控制平衡。 AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis是两个前苏联的科学家他们在1962 年的论⽂《An algorithm for the organization of information》中发表了它。 AVL树实现这⾥我们引⼊⼀个平衡因⼦(balance factor)的概念每个结点都有⼀个平衡因⼦任何结点的平衡因⼦等于右⼦树的⾼度减去左⼦树的⾼度也就是说任何结点的平衡因⼦等于0/1/-1 AVL树并不是必须要平衡因⼦但是有了平衡因⼦可以更⽅便我们去进⾏观察和控制树是否平衡 就像⼀个⻛向标⼀样。 思考⼀下为什么AVL树是⾼度平衡搜索⼆叉树要求⾼度差不超过1⽽不是⾼度差是0呢0不是更好的平衡吗画画图分析我们发现不是不想这样设计⽽是有些情况是做不到⾼度差是0的。⽐如⼀棵树是2个结点4个结点等情况下⾼度差最好就是1⽆法作为⾼度差是0 AVL树整体结点数量和分布和完全⼆叉树类似⾼度可以控制在 那么增删查改的效率也可 以控制在 相⽐⼆叉搜索树有了本质的提升。 AVL树的实现 AVL树的结构 AVL树的插⼊ 插⼊⼀个值按⼆叉搜索树规则进⾏插⼊。 新增结点以后只会影响祖先结点的⾼度也就是可能会影响部分祖先结点的平衡因⼦所以更新 从新增结点-根结点路径上的平衡因⼦实际中最坏情况下要更新到根有些情况更新到中间就可以停⽌了。更新平衡因⼦过程中没有出现问题则插⼊结束 更新平衡因⼦过程中出现不平衡对不平衡⼦树旋转旋转后本质调平衡的同时本质降低了⼦树 的⾼度不会再影响上⼀层所以插⼊结束。 平衡因⼦更新 更新原则 平衡因⼦ 右⼦树⾼度-左⼦树⾼度 只有⼦树⾼度变化才会影响当前结点平衡因⼦。 插⼊结点会增加⾼度所以新增结点在parent的右⼦树parent的平衡因⼦新增结点在 parent的左⼦树parent平衡因⼦- - parent所在⼦树的⾼度是否变化决定了是否会继续往上更新 更新停⽌条件 更新后parent的平衡因⼦等于0更新中parent的平衡因⼦变化为-1——0 或者 1——0说明更新前 parent⼦树⼀边⾼⼀边低新增的结点插⼊在低的那边插⼊后parent所在的⼦树⾼度不变不会 影响parent的⽗亲结点的平衡因⼦更新结束。 更新后parent的平衡因⼦等于1 或 -1更新前更新中parent的平衡因⼦变化为0——1 或者 0——-1说 明更新前parent⼦树两边⼀样⾼新增的插⼊结点后parent所在的⼦树⼀边⾼⼀边低parent所 在的⼦树符合平衡要求但是⾼度增加了1会影响arent的⽗亲结点的平衡因⼦所以要继续向上更新。 更新后parent的平衡因⼦等于2 或 -2更新前更新中parent的平衡因⼦变化为1——2 或者 -1——-2说 明更新前parent⼦树⼀边⾼⼀边低新增的插⼊结点在⾼的那边parent所在的⼦树⾼的那边更⾼ 了破坏了平衡parent所在的⼦树不符合平衡要求需要旋转处理旋转的⽬标有两个 把 parent⼦树旋转平衡。降低parent⼦树的⾼度恢复到插⼊结点以前的⾼度。所以旋转后也不 需要继续往上更新插⼊结束。 例子 更新到10结点平衡因⼦为210所在的⼦树已经不平衡需要旋转处理 更新到中间结点3为根的⼦树⾼度不变不会影响上⼀层更新结束 最坏更新到根停⽌ 旋转 当树平衡时进行旋转来让AVL平衡是重点 旋转的原则 保持搜索树的规则 让旋转的树从不满⾜变平衡其次降低旋转树的⾼度旋转总共分为四种左单旋/右单旋/左右双旋/右左双旋。 说明下⾯的图中有些结点我们给的是具体值如10和5等结点这⾥是为了⽅便讲解实际中是什么值都可以只要⼤⼩关系符合搜索树的规则即可 右单旋 本图展⽰的是10为根的树有a/b/c抽象为三棵⾼度为h的⼦树(h0)a/b/c均符合AVL树的要 求。10可能是整棵树的根也可能是⼀个整棵树中局部的⼦树的根。这⾥a/b/c是⾼度为h的⼦树 是⼀种概括抽象表⽰他代表了所有右单旋的场景实际右单旋形态有很多种具体图2/图3/图4/ 图5进⾏了详细描述。 在a⼦树中插⼊⼀个新结点导致a⼦树的⾼度从h变成h1不断向上更新平衡因⼦导致10的平 衡因⼦从-1变成-210为根的树左右⾼度差超过1违反平衡规则。10为根的树左边太⾼了需要 往右边旋转控制两棵树的平衡。 旋转核⼼步骤因为5 b⼦树的值 10将b变成10的左⼦树10变成5的右⼦树5变成这棵树新的根符合搜索树的规则控制了平衡同时这棵的⾼度恢复到了插⼊之前的h2符合旋转原 则。如果插⼊之前10整棵树的⼀个局部⼦树旋转后不会再影响上⼀层插⼊结束了。 parent有可能是整棵树的根也可能是局部的⼦树 左单旋 本图展⽰的是10为根的树有a/b/c抽象为三棵⾼度为h的⼦树(h0)a/b/c均符合AVL树的要 求。10可能是整棵树的根也可能是⼀个整棵树中局部的⼦树的根。这⾥a/b/c是⾼度为h的⼦树 是⼀种概括抽象表⽰他代表了所有右单旋的场景实际右单旋形态有很多种具体跟上⾯左旋类 似。 在a⼦树中插⼊⼀个新结点导致a⼦树的⾼度从h变成h1不断向上更新平衡因⼦导致10的平 衡因⼦从1变成210为根的树左右⾼度差超过1违反平衡规则。10为根的树右边太⾼了需要往 左边旋转控制两棵树的平衡。 旋转核⼼步骤因为10 b⼦树的值 15将b变成10的右⼦树10变成15的左⼦树15变成这棵 树新的根符合搜索树的规则控制了平衡同时这棵的⾼度恢复到了插⼊之前的h2符合旋转 原则。如果插⼊之前10整棵树的⼀个局部⼦树旋转后不会再影响上⼀层插⼊结束了。 左右双旋 通过下面的图可以看到左边⾼时如果插⼊位置不是在a⼦树⽽是插⼊在b⼦树b⼦树⾼度h变成h1引发旋转右单旋⽆法解决问题右单旋后我们的树依旧不平衡。右单旋解决的纯的左边⾼但是插⼊在b⼦树中10为跟的⼦树不再是单纯的左边⾼对于10是左边⾼但是对于5是右边⾼需要⽤两次旋转才能解决以5为旋转点进⾏⼀个左单旋以10为旋转点进⾏⼀个右单旋这棵树这棵树就平衡了。 分别为左右双旋中h0和h1具体场景分析下⾯我们将a/b/c⼦树抽象为⾼度h的AVL ⼦树进⾏分析另外我们需要把b⼦树的细节进⼀步展开为8和左⼦树⾼度为h-1的e和f⼦树因为我们要对b的⽗亲5为旋转点进⾏左单旋左单旋需要动b树中的左⼦树。b⼦树中新增结点的位置不同平衡因⼦更新的细节也不同通过观察8的平衡因⼦不同这⾥我们要分三个场景讨论。 场景1h 1时新增结点插⼊在e⼦树e⼦树⾼度从h-1并为h并不断更新8-5-10平衡因⼦ 引发旋转其中8的平衡因⼦为-1旋转后8和5平衡因⼦为010平衡因⼦为1。 场景2h 1时新增结点插⼊在f⼦树f⼦树⾼度从h-1变为h并不断更新8-5-10平衡因⼦引 发旋转其中8的平衡因⼦为1旋转后8和10平衡因⼦为05平衡因⼦为-1。 场景3h 0时a/b/c都是空树b⾃⼰就是⼀个新增结点不断更新5-10平衡因⼦引发旋转其中8的平衡因⼦为0旋转后8和10和5平衡因⼦均为0。 右左双旋: 跟左右双旋类似下⾯我们将a/b/c⼦树抽象为⾼度h的AVL⼦树进⾏分析另外我们需要把b⼦树的 细节进⼀步展开为12和左⼦树⾼度为h-1的e和f⼦树因为我们要对b的⽗亲15为旋转点进⾏右单 旋右单旋需要动b树中的右⼦树。b⼦树中新增结点的位置不同平衡因⼦更新的细节也不同通 过观察12的平衡因⼦不同这⾥我们要分三个场景讨论。 场景1h 1时新增结点插⼊在e⼦树e⼦树⾼度从h-1变为h并不断更新12-15-10平衡因 ⼦引发旋转其中12的平衡因⼦为-1旋转后10和12平衡因⼦为015平衡因⼦为1。 场景2h 1时新增结点插⼊在f⼦树f⼦树⾼度从h-1变为h并不断更新12-15-10平衡因⼦ 引发旋转其中12的平衡因⼦为1旋转后15和12平衡因⼦为010平衡因⼦为-1。 场景3h 0时a/b/c都是空树b⾃⼰就是⼀个新增结点不断更新15-10平衡因⼦引发旋转其中12的平衡因⼦为0旋转后10和12和15平衡因⼦均为0。 旋转逻辑 AVL树的其他功能: 查找 ⼆叉搜索树逻辑实现即可搜索效率为 O ( logN ) 输出 计算高度 计算大小 删除 AVL树的删除本章节不做讲解有兴趣可参考《殷⼈昆 数据结构⽤⾯向对象⽅法与C语⾔描述》中讲解。 AVL树平衡检测: 我们实现的AVL树是否合格我们通过检查左右⼦树⾼度差的的程序进⾏反向验证同时检查⼀下结点的平衡因⼦更新是否出现了问题。 测试代码*2: 源代码 AVL.h #pragma once
#define CRT_SECURE_NO_WARNINGS
#include iostreamusing namespace std;templateclass T
struct AVLTreeNode
{AVLTreeNode(const T data T()): _Left(nullptr), _Right(nullptr), _Parent(nullptr), _data(data), _bf(0){}AVLTreeNodeT* _Left;AVLTreeNodeT* _Right;AVLTreeNodeT* _Parent;T _data;int _bf; // 节点的平衡因子
};// AVL: 二叉搜索树 平衡因子的限制
templateclass T
class AVLTree
{typedef AVLTreeNodeT Node;public:AVLTree(): _Root(nullptr){}void RotateR(Node* parent) //右单旋{//cout endl 右单旋 parent-_data endl;Node* subL parent-_Left;Node* subLR subL-_Right;Node* parentParent parent-_Parent;parent-_Left subLR;if (subLR)subLR-_Parent parent;subL-_Right parent;parent-_Parent subL;// parent有可能是整棵树的根也可能是局部的⼦树// 如果是整棵树的根要修改_rootif (parentParent nullptr){_Root subL;subL-_Parent nullptr;}//如果是局部的指针要跟上⼀层链接else{if (parent parentParent-_Left){parentParent-_Left subL;}else{parentParent-_Right subL;}subL-_Parent parentParent;}parent-_bf subL-_bf 0;}void RotateL(Node* parent) //左单旋{//cout endl 左单旋 parent-_data endl;Node* subR parent-_Right;Node* subRL subR-_Left;Node* parentParent parent-_Parent;parent-_Right subRL;if (subRL)subRL-_Parent parent;subR-_Left parent;parent-_Parent subR;// parent有可能是整棵树的根也可能是局部的⼦树// 如果是整棵树的根要修改_rootif (parentParent nullptr){_Root subR;subR-_Parent nullptr;}//如果是局部的指针要跟上⼀层链接else{if (parent parentParent-_Left){parentParent-_Left subR;}else{parentParent-_Right subR;}subR-_Parent parentParent;}parent-_bf subR-_bf 0;}void RotateLR(Node* parent) //左右双旋{//cout endl 左右双旋 parent-_data endl;Node* subL parent-_Left;Node* subLR subL-_Right;int bf subLR-_bf;RotateL(parent-_Left);RotateR(parent);if (bf 0){subL-_bf 0;subLR-_bf 0;parent-_bf 0;}else if (bf -1){subL-_bf 0;subLR-_bf 0;parent-_bf 1;}else if (bf 1){subL-_bf -1;subLR-_bf 0;parent-_bf 0;}else{//assert(false);}}void RotateRL(Node* parent) //右左双旋{//cout endl 右左双旋 parent-_data endl;Node* subR parent-_Right;Node* subRL subR-_Left;int bf subRL-_bf;RotateR(parent-_Right);RotateL(parent);if (bf 0){subR-_bf 0;subRL-_bf 0;parent-_bf 0;}else if (bf 1){subR-_bf 0;subRL-_bf 0;parent-_bf -1;}else if (bf -1){subR-_bf 1;subRL-_bf 0;parent-_bf 0;}else{//assert(false);}}// 在AVL树中插入值为data的节点bool Insert(const T data){//cout 插入: data ;if (_Root nullptr) //插入树为空的情况{_Root new Node(data);return true;} else //插入树不空的情况{Node* cur _Root;Node* cur_parent nullptr;while (cur ! nullptr) //找到插入位置{if (cur-_data data){cur_parent cur;cur cur-_Left;}else if(cur-_data data){cur_parent cur;curcur-_Right;}else{return false;}}cur new Node(data);if (cur_parent-_data cur-_data) //链接插入节点{cur_parent-_Left cur;cur-_Parent cur_parent;}else{cur_parent-_Right cur;cur-_Parent cur_parent;}while (cur_parent) //更新平衡因子{if (cur_parent-_Left cur)--cur_parent-_bf;elsecur_parent-_bf;if (cur_parent-_bf 0){//更新停止break;}else if (cur_parent-_bf 1 || cur_parent-_bf -1){//继续向上更新cur cur_parent;cur_parent cur_parent-_Parent;}else if (cur_parent-_bf -2 || cur_parent-_bf 2){//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!不平衡了需要进行旋转处理!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!if (cur_parent-_bf -2 cur-_bf -1){RotateR(cur_parent);}else if (cur_parent-_bf 2 cur-_bf 1){RotateL(cur_parent);}else if (cur_parent-_bf -2 cur-_bf 1){RotateLR(cur_parent);}else if (cur_parent-_bf 2 cur-_bf -1){RotateRL(cur_parent);}else{//assert(false);}break;}}}return true;};//------------------------------------------------------------------------------------------------------------Node* Find(const T data) //查找{Node* cur _Root;while (cur){if (cur-_data data){cur cur-_Right;}else if (cur-_data data){cur cur-_Left;}else{return cur;}}return nullptr;}void InOrder() //输出{_InOrder(_Root);cout endl;}int Height(){return _Height(_Root);}int Size(){return _Size(_Root);}bool IsBalanceTree(){return _IsBalanceTree(_Root);}private:Node* _Root;void _InOrder(Node* root){if (root nullptr){return;}_InOrder(root-_Left);cout root-_data endl;_InOrder(root-_Right);}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;}int _Size(Node* root){if (root nullptr)return 0;return _Size(root-_left) _Size(root-_right) 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-_data 高度差异常 endl;return false;}if (root-_bf ! diff){cout root-_data 平衡因子异常 endl;return false;}// pRoot的左和右如果都是AVL树则该树一定是AVL树return _IsBalanceTree(root-_Left) _IsBalanceTree(root-_Right);}
}; AVL_test.cpp #include AVL_Tree.h
#include vector;-----------------------------检查----------------------------------------------------------
//
//
----------------------------------------------------------------------------
// // 测试代码
void TestAVLTree1()
{AVLTreeint t;// 常规的测试用例//int a[] { 16, 3, 7, 11, 9, 26, 18, 14, 15 };// 特殊的带有双旋场景的测试用例int a[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto e : a){t.Insert(e);}cout endl endl endl;t.InOrder();cout t.IsBalanceTree() endl;
}// 插⼊⼀堆随机值测试平衡顺便测试⼀下⾼度和性能等
void TestAVLTree2()
{const int N 100000;vectorint v;v.reserve(N);srand(time(0));for (size_t i 0; i N; i){v.push_back(rand() i);}size_t begin2 clock();AVLTreeint t;for (auto e : v){t.Insert(e);}size_t end2 clock();cout Insert: end2 - begin2 endl;cout t.IsBalanceTree() endl;cout Height: t.Height() endl;//cout Size: Size(t) endl;size_t begin1 clock();// 确定在的值//for (auto e : v)//{// if (t.Find(e) nullptr)cout err_of_find;//}//随机值for (size_t i 0; i N; i){t.Find((rand() i));}size_t end1 clock();cout Find: end1 - begin1 endl;
}
//
------------------------------------------------------------------------------------int main()
{//TestAVLTree1();TestAVLTree2();return 0;
} KV结构 将data改为pair K , V 类型并且做一些改动即可 源代码 . h #pragma once#includeiostream
#includeassert.h
using namespace std;templateclass K, class V
struct AVLTreeNode
{// 需要parent指针后续更新平衡因子可以看到pairK, V _kv;AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;int _bf; // balance factorAVLTreeNode(const pairK, V kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0){}
};templateclass K, class V
class AVLTree
{typedef AVLTreeNodeK, V Node;
public:bool Insert(const pairK, 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{return false;}}cur new Node(kv);if (parent-_kv.first kv.first){parent-_right cur;}else{parent-_left 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){cur parent;parent parent-_parent;}else if (parent-_bf 2 || parent-_bf -2){if (parent-_bf -2 cur-_bf -1){RotateR(parent);}else if (parent-_bf 2 cur-_bf 1){RotateL(parent);}else if (parent-_bf -2 cur-_bf 1){RotateLR(parent);}else if (parent-_bf 2 cur-_bf -1){RotateRL(parent);}else{assert(false);}break;}else{assert(false);}}return true;}void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if(subLR)subLR-_parent parent;Node* pParent parent-_parent;subL-_right parent;parent-_parent subL;if (parent _root){_root subL;subL-_parent nullptr;}else{if (pParent-_left parent){pParent-_left subL;}else{pParent-_right subL;}subL-_parent pParent;}subL-_bf 0;parent-_bf 0;}void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL)subRL-_parent parent;Node* parentParent parent-_parent;subR-_left parent;parent-_parent subR;if (parentParent nullptr){_root subR;subR-_parent nullptr;}else{if (parent parentParent-_left){parentParent-_left subR;}else{parentParent-_right subR;}subR-_parent parentParent;}parent-_bf subR-_bf 0;}void RotateLR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;RotateL(parent-_left);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 RotateRL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;int bf subRL-_bf;RotateR(parent-_right);RotateL(parent);if (bf 0){subR-_bf 0;subRL-_bf 0;parent-_bf 0;}else if (bf 1){subR-_bf 0;subRL-_bf 0;parent-_bf -1;}else if (bf -1){subR-_bf 1;subRL-_bf 0;parent-_bf 0;}else{assert(false);}}void InOrder(){_InOrder(_root);cout endl;}int Height(){return _Height(_root);}int Size(){return _Size(_root);}bool IsBalanceTree(){return _IsBalanceTree(_root);}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;}else{return cur;}}return nullptr;}private:void _InOrder(Node* root){if (root nullptr){return;}_InOrder(root-_left);cout root-_kv.first : root-_kv.second endl;_InOrder(root-_right);}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;}int _Size(Node* root){if (root nullptr)return 0;return _Size(root-_left) _Size(root-_right) 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);}
private:Node* _root nullptr;
}; . cpp #define _CRT_SECURE_NO_WARNINGS 1
#includevector
#includeAVLTree.hvoid TestAVLTree1()
{AVLTreeint, int t;// 常规的测试用例int a[] { 16, 3, 7, 11, 9, 26, 18, 14, 15 };// 特殊的带有双旋场景的测试用例//int a[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto e : a){t.Insert({ e, e });}t.InOrder();cout t.IsBalanceTree() endl;
}// 插入一堆随机值测试平衡顺便测试一下高度和性能等
void TestAVLTree2()
{const int N 1000000;vectorint v;v.reserve(N);srand(time(0));for (size_t i 0; i N; i){v.push_back(rand() i);}size_t begin2 clock();AVLTreeint, int t;for (auto e : v){t.Insert(make_pair(e, e));}size_t end2 clock();cout Insert: end2 - begin2 endl;cout t.IsBalanceTree() endl;cout Height: t.Height() endl;cout Size: t.Size() endl;size_t begin1 clock();// 确定在的值for (auto e : v){t.Find(e);}// 随机值/*for (size_t i 0; i N; i){t.Find((rand() i));}*/size_t end1 clock();cout Find: end1 - begin1 endl;
}int main()
{TestAVLTree2();return 0;
}
