1.AVL的概念

1. AVL樹是最先發(fā)明的自平衡?叉查找樹，AVL是?顆空樹，或者具備下列性質的?叉搜索樹：它的左右子樹都是AVL樹，且左右子樹的高度差的絕對值不超過1。AVL樹是一顆高度平衡搜索二叉樹， 通過控制高度差去控制平衡。
2. AVL樹得名于它的發(fā)明者G.M.Adelson-Velsky和E.M.Landis是兩個前蘇聯(lián)的科學家，他們在1962年的論文《An algorithm for the organization of information》中發(fā)表了它。
3. AVL樹實現(xiàn)這里我們引入一個平衡因子（balance factor）的概念，每個結點都有一個平衡因子，任何結點的平衡因子等于右子樹的高度減去左子樹的高度，也就是說任何結點的平衡因子等于0/1/-1，AVL樹并不是必須要平衡因子，但是有了平衡因子可以更方便我們去進行觀察和控制樹是否平衡，就像一個風向標一樣。
4. 思考一下為什么AVL樹是高度平衡?叉搜索樹，要求高度差不超過1，而不是高度差是0呢？0不是更好的平衡嗎？畫畫圖分析我們發(fā)現(xiàn)，不是不想這樣設計，而是有些情況是做不到高度差是0的。比如一棵樹是2個結點，4個結點等情況下，高度差最好就是1，無法做到高度差是0。
5. AVL樹整體結點數(shù)量和分布和完全?叉樹類似，高度可以控制在logN，那么增刪查改的效率也可以控制在O(logN)，相比?叉搜索樹有了本質的提升。

2.AVL樹的實現(xiàn)

1.AVL樹的結構

template<class k, class v>
struct AVLTreeNode
{	pair<k, v> _kv;  //鍵值對//需要parent指針，后序更新平衡因子可以看到AVLTreeNode<k, v>* _left;AVLTreeNode<k, v>* _right;AVLTreeNode<k, v>* _parent;int _bf = 0; //平衡因子AVLTreeNode(const pair<k, v>& kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0){}
};template<class K, class V>
class AVLTree
{typedef AVLTreeNode<K, V> Node;//using Node = AVLTreeNode<K, V>;public://...private:Node* _root = nullptr;
};

2.AVL樹的插入

1. 插入一個值按?叉搜索樹規(guī)則進行插入。
2. 新增結點以后，只會影響祖先結點的高度，也就是可能會影響部分祖先結點的平衡因子，所以需要更新從新增結點->根結點路徑上的平衡因子，實際中最壞情況下要更新到根，有些情況更新到中間就可以停止了，具體情況我們下面再詳細分析。
3. 更新平衡因子過程中沒有出現(xiàn)問題，則插入結束。
4. 更新平衡因子過程中出現(xiàn)不平衡，對不平衡子樹旋轉，旋轉后本質調平衡的同時，本質降低了子樹的高度，不會再影響上一層，插入結束。

1.更新平衡因子

平衡因子更新原則：

1. 平衡因子 = 右子樹高度 - 左子樹高度。
2. 只有子樹高度變化才會影響當前結點平衡因子。
3. 插入結點，會增加高度，所以新增結點在parent的右子樹，parent的平衡因子+1，新增結點在parent的左子樹，parent平衡因子-1。
4. parent所在子樹的高度是否變化決定了是否會繼續(xù)往上更新。

更新停止條件：

1. 更新后parent的平衡因子等于0，更新中parent的平衡因子變化為 -1->0 或者 1->0，說明更新前parent子樹一邊高一邊低，新增的結點插入在低的那邊，插入后parent所在的子樹高度不變，不會影響parent的父親結點的平衡因子，更新結束。
2. 更新后parent的平衡因子等于1或-1，更新前更新中parent的平衡因子變化為 0->1 或者 0->-1，說明更新前parent子樹兩邊一樣高，新增的插如結點后，parent所在的子樹一邊高一邊低，parent所在的子樹符合平衡要求，但是高度增加了1，會影響parent的父親結點的平衡因高，所以要繼續(xù)向上更新。
3. 更新后parent的平衡因子等于2或-2，更新前更新中parent的平衡因子變化為 1->2 或者 -1->-2，說明更新前parent子樹一邊高一邊低，新增的插入結點在高的那邊，parent所在的子樹高的那邊更高了，破壞了平衡，parent所在的子樹不符合平衡要求，需要旋轉處理，旋轉的目標有兩個：1、把parent子樹旋轉平衡。2、降低parent子樹的?度，恢復到插入結點以前的高度。所以旋轉后也不需要繼續(xù)往上更新，插入結束。
4. 不斷更新，更新到根，根的平衡因子是1或-1也停止了。

以下是三幅圖的平衡因子更新過程：

• 更新到10結點，平衡因子為2，10所在的子樹已經(jīng)不平衡，需要旋轉處理：
• 更新到中間結點，3為根的子樹高度不變，不會影響上一層，更新結束：
• 最壞更新到根停止：

bool Insert(const pair<K, V>& kv)
{//根節(jié)點為空時if (_root == nullptr){_root = new Node(kv);return true;}//根節(jié)點不為空時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;}}//插入新節(jié)點cur = new Node(kv);if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//更新平衡因子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 = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2){//4種旋轉情況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);}break;}else{assert(false);}}return true;
}

2.旋轉

1. 保持搜索樹的規(guī)則。
2. 讓旋轉的樹重新變回平衡狀態(tài)，其次降低旋轉樹的?度。
3. 旋轉總共分為四種，左單旋/右單旋/左右雙旋/右左雙旋。

1.右單旋

1. 下面的抽象圖展示的是10為根的樹，有a/b/c抽象為三棵高度為h的子樹(h>=0)，a/b/c均符合AVL樹的要求。10可能是整棵樹的根，也可能是一個整棵樹中局部的子樹的根。這里a/b/c是高度為h的子樹，是一種概括抽象表示，它代表了所有右單旋的場景，實際右單旋形態(tài)有很多種，具體下圖進行了詳細描述。
2. 在a子樹中插入一個新結點，導致a字樹的高度從h變成h+1，不斷向上更新平衡因子，導致10的平衡因子從-1變成-2，10為根的樹左右高度差超過1，違反平衡規(guī)則。10為根的樹左邊太高了，需要往右邊旋轉，控制兩棵樹的平衡。
3. 旋轉核心步驟，因為5<b子樹的值<10，將b變成10的左子樹，10變成5的右子樹，5變成這棵樹新的根，符合搜索樹的規(guī)則，控制了平衡，同時這棵的高度恢復到了插入之前的h+2，符合旋轉原則。如果插入之前10整棵樹的一個局部子樹，旋轉后不會再影響上一層，插入結束了。
   

下面給3幅圖觀察具體的旋轉過程：

void RotateR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if(subLR)subLR->_parent = parent;//記錄parent的父節(jié)點Node* pParent = parent->_parent; subL->_right = parent;parent->_parent = subL;//當parent是根節(jié)點時if (parent == _root){_root = subL;subL->_parent = nullptr;}else //當parent不是根節(jié)點時{subL->_parent = pParent;if (pParent->_left == parent)pParent->_left = subL;elsepParent->_right = subL;}//更新平衡因子subL->_bf = 0;parent->_bf = 0;
}

2.左單旋

1. 下圖展示的是10為根的樹，有a/b/c抽象為三棵高度為h的子樹(h>=0)，a/b/c均符合AVL樹的要求。10可能是整棵樹的根，也可能是一個整棵樹中局部的子樹的根。這里a/b/c是高度為h的子樹，是一種概括抽象表示，它代表了所有右單旋的場景，實際右單旋形態(tài)有很多種，具體跟下面右單旋類似。
2. 在a子樹中插入一個新結點，導致a子樹的高度從h變成h+1，不斷向上更新平衡因子，導致10的平衡因子從1變成2，10為根的樹左右高度差超過1，違反平衡規(guī)則。10為根的樹右邊太高了，需要往左邊旋轉，控制兩棵樹的平衡。
3. 旋轉核心步驟，因為10<b子樹的值<15，將b變成10的右子樹，10變成15的左子樹，15變成這棵樹新的根，符合搜索樹的規(guī)則，控制了平衡，同時這棵的高度恢復到了插入之前的h+2，符合旋轉原則。如果插入之前10整棵樹的一個局部子樹，旋轉后不會再影響上一層，插入結束了。
   

下面給3幅圖觀察具體的旋轉過程：

void RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if(subRL)subRL->_parent = parent;//記錄parent的父節(jié)點Node* pParent = parent->_parent;subR->_left = parent;parent->_parent = subR;//當parent是根節(jié)點時if (parent == _root){_root = subR;subR->_parent = nullptr;}else //當parent不是根節(jié)點時{subR->_parent = pParent;if (pParent->_left == parent)pParent->_left = subR;elsepParent->_right = subR;}//更新平衡因子parent->_bf = 0;subR->_bf = 0;
}

3.左右雙旋

• 先看一個例子：左邊高時，如果插入的位置在5的右子樹，以10為頂點采用右單旋無法解決問題，右單旋后，樹依舊不平衡。如下圖：
• 右單旋解決的純粹的左邊高，10為跟的子樹不再是單純的左邊高，對于10是左邊高，但是對于5是右邊高，需要用兩次旋轉才能解決，先以5為旋轉點進行一個左單旋，再以10為旋轉點進行一個右單旋，之后這棵樹就平衡了。如下圖：

• 再來看一個例子：左邊高時，如果插入的位置在8的左子樹，以10為頂點采用右單旋無法解決問題，右單旋后，樹依舊不平衡。
• 左右雙旋解決：先以5為旋轉點進行一個左單旋，再以10為旋轉點進行一個右單旋，之后這棵樹就平衡了。如下圖：

• 最后看一個例子：左邊高時，如果插入的位置在8的右子樹，以10為頂點采用右單旋無法解決問題，右單旋后，樹依舊不平衡。
• 左右雙旋解決：先以5為旋轉點進行一個左單旋，再以10為旋轉點進行一個右單旋，之后這棵樹就平衡了。如下圖：

不同的場景，平衡因子的更新規(guī)則也不相同。如下三幅圖：

• 場景一：5的右孩子8的平衡因子為0時：
• 場景二：5的右孩子8的平衡因子為-1時：
  
• 場景三：5的右孩子8的平衡因子為1時：
  

具體圖轉換為抽象圖如下：

1. 當h>=1時，新增結點插入在e子樹，e子樹高度從h-1變成h，并不斷更新8->5->10平衡因子，引發(fā)旋轉，其中8的平衡因子為-1。旋轉后8和5平衡因子為0，10平衡因子為1。
2. 當h>=1時，新增結點插入在f子樹，f子樹高度從h-1變?yōu)閔，并不斷更新8->5->10平衡因子，引發(fā)旋轉，其中8的平衡因子為1。旋轉后8和10平衡因子為0，5平衡因子為-1。
3. 當h==0時，a/b/c都是空樹，8自己就是一個新增結點，不斷更新5->10平衡因子，引發(fā)旋轉，其中8的平衡因子為0。旋轉后8和10和5平衡因子均為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);}
}

4.右左雙旋

• 先看一個例子：右邊高時，如果插入的位置在5的左子樹，以10為頂點采用右單旋無法解決問題，右單旋后，樹依舊不平衡。如下圖：
• 左單旋解決的純粹的右邊高，5為跟的子樹不再是單純的右邊高，對于5是右邊高，但是對于10是左邊高，需要用兩次旋轉才能解決，先以10為旋轉點進行一個右單旋，再以5為旋轉點進行一個左單旋，之后這棵樹就平衡了。如下圖：
  

• 再來看一個例子：右邊高時，如果插入的位置在8的左子樹，以5為頂點采用左單旋無法解決問題，左單旋后，樹依舊不平衡。如下圖：
• 右左雙旋解決：先以10為旋轉點進行一個右單旋，再以5為旋轉點進行一個左單旋，之后這棵樹就平衡了。如下圖：

• 最后看一個例子：右邊高時，如果插入的位置在8的右子樹，以5為頂點采用左單旋無法解決問題，左單旋后，樹依舊不平衡。如下圖：
• 右左雙旋解決：先以5為旋轉點進行一個右單旋，再以10為旋轉點進行一個左單旋，之后這棵樹就平衡了。如下圖：

不同的場景，平衡因子的更新規(guī)則也不相同。如下三幅圖：

• 場景一：10的左孩子8的平衡因子為0時：
• 場景二：10的左孩子8的平衡因子為-1時：
• 場景三：10的左孩子8的平衡因子為1時：

具體圖轉換為抽象圖如下：

1. 當h>=1時，新增結點插入在e子樹，e子樹高度從h-1變?yōu)閔，并不斷更新12->15->10平衡因子，引發(fā)旋轉，其中12的平衡因子為-1。旋轉后10和12平衡因子為0，15平衡因子為1。
2. 當h>=1時，新增結點插入在f子樹，f子樹高度從h-1變?yōu)閔，并不斷更新12->15->10平衡因子，引發(fā)旋轉，其中12的平衡因子為1。旋轉后15和12平衡因子為0，10平衡因子為-1。
3. 當h==0時，a/b/c都是空樹，12自己就是一個新增結點，不斷更新15->10平衡因子，引發(fā)旋轉，其中12的平衡因子為0，旋轉后10和12和15平衡因子均為0。

void RotateRL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);//更新平衡因子if (bf == -1){subRL->_bf = 0;parent->_bf = 0;subR->_bf = 1;}else if (bf == 1){subRL->_bf = 0;parent->_bf = -1;subR->_bf = 0;}else if (bf == 0){subRL->_bf = 0;parent->_bf = 0;subR->_bf = 0;}else{assert(false);}
}

3.AVL樹的查找

按照?叉搜索樹邏輯實現(xiàn)即可，搜索效率為O(logN)

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

4.AVL樹的平衡檢測

我們實現(xiàn)的AVL樹是否合格，可以通過檢查左右子樹高度差的的程序進行反向驗證，同時檢查?下結點的平衡因子更新是否出現(xiàn)了問題。

public:int Height(){return _Height(_root);}bool IsAVLTree(){return _IsAVLTree(_root);}private:int _Height(Node* root){if (root == nullptr) return 0;int leftHelght = _Height(root->_left);int rightHelght = _Height(root->_right);return max(leftHelght, rightHelght) + 1;}bool _IsAVLTree(Node* root){//空樹也是AVL樹if (root == nullptr) return true;//計算當前節(jié)點的平衡因子：即高度差int leftHelght = _Height(root->_left);int rightHelght = _Height(root->_right);int bf = rightHelght - leftHelght;//如果計算出來的平衡因子的絕對值大于1，則一定不是AVL樹if (abs(bf) > 2){cout << root->_kv.first << "高度差異常" << endl;return false;}//如果計算出來的平衡因子與root的平衡因子不相等時，則一定不是AVL樹if (bf != root->_bf){cout << root->_kv.first << "平衡因子異常" << endl;return false;}//只有左右子樹都是AVL樹時：該樹一定是AVL樹return _IsAVLTree(root->_left) && _IsAVLTree(root->_right);}

void TestAVLTree1()
{AVLTree<int, int> t;//常規(guī)的測試用例 //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 });}cout << t.IsAVLTree() << endl;
}

5.AVL樹的性能分析

public:void InOrder(){_InOrder(_root);cout << endl;}int Size(){return _Size(_root);}private:void _InOrder(Node* root){if (root == nullptr) return;_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}int _Size(Node* root){if (root == nullptr) return 0;return _Size(root->_left) + _Size(root->_right) + 1;}

void TestAVLTree2()
{const 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);}size_t begin1 = clock();AVLTree<int, int> t;for (auto e : v){t.Insert(make_pair(e, e));}size_t end1 = clock();cout << "Insert:" << end1 - begin1 << endl;cout << t.IsAVLTree() << endl;cout << t.Height() << endl;cout << t.Size() << endl;size_t begin2 = clock();//查找確定在的值 /*for (auto e : v){t.Find(e);}*///查找隨機值for (size_t i = 0; i < N; i++){t.Find((rand() + i));}size_t end2 = clock();cout << "Find:" << end2 - begin2 << endl;
}

6.AVL樹的刪除

刪除等待更新…

3.總代碼

1.AVLTree.h

#pragma once#include<iostream>
#include<assert.h>
using namespace std;template<class k, class v>
struct AVLTreeNode
{	pair<k, v> _kv;  //鍵值對//需要parent指針，后序更新平衡因子可以看到AVLTreeNode<k, v>* _left;AVLTreeNode<k, v>* _right;AVLTreeNode<k, v>* _parent;int _bf = 0; //平衡因子AVLTreeNode(const pair<k, v>& kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0){}
};template<class K, class V>
class AVLTree
{typedef AVLTreeNode<K, V> Node;//using Node = AVLTreeNode<K, V>;public:bool Insert(const pair<K, V>& kv){//根節(jié)點為空時if (_root == nullptr){_root = new Node(kv);return true;}//根節(jié)點不為空時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;}}//插入新節(jié)點cur = new Node(kv);if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//更新平衡因子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 = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2){//4種旋轉情況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);}break;}else{assert(false);}}return true;}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;}//右單旋void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if(subLR)subLR->_parent = parent;//記錄parent的父節(jié)點Node* pParent = parent->_parent; subL->_right = parent;parent->_parent = subL;//當parent是根節(jié)點時if (parent == _root){_root = subL;subL->_parent = nullptr;}else //當parent不是根節(jié)點時{subL->_parent = pParent;if (pParent->_left == parent)pParent->_left = subL;elsepParent->_right = subL;}//更新平衡因子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;//記錄parent的父節(jié)點Node* pParent = parent->_parent;subR->_left = parent;parent->_parent = subR;//當parent是根節(jié)點時if (parent == _root){_root = subR;subR->_parent = nullptr;}else //當parent不是根節(jié)點時{subR->_parent = pParent;if (pParent->_left == parent)pParent->_left = subR;elsepParent->_right = subR;}//更新平衡因子parent->_bf = 0;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 == -1){subRL->_bf = 0;parent->_bf = 0;subR->_bf = 1;}else if (bf == 1){subRL->_bf = 0;parent->_bf = -1;subR->_bf = 0;}else if (bf == 0){subRL->_bf = 0;parent->_bf = 0;subR->_bf = 0;}else{assert(false);}}void InOrder(){_InOrder(_root);cout << endl;}int Height(){return _Height(_root);}bool IsAVLTree(){return _IsAVLTree(_root);}int Size(){return _Size(_root);}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 leftHelght = _Height(root->_left);int rightHelght = _Height(root->_right);return max(leftHelght, rightHelght) + 1;}bool _IsAVLTree(Node* root){//空樹也是AVL樹if (root == nullptr) return true;//計算當前節(jié)點的平衡因子：即高度差int leftHelght = _Height(root->_left);int rightHelght = _Height(root->_right);int bf = rightHelght - leftHelght;//如果計算出來的平衡因子的絕對值大于1，則一定不是AVL樹if (abs(bf) > 2){cout << root->_kv.first << "高度差異常" << endl;return false;}//如果計算出來的平衡因子與root的平衡因子不相等時，則一定不是AVL樹if (bf != root->_bf){cout << root->_kv.first << "平衡因子異常" << endl;return false;}//只有左右子樹都是AVL樹時：該樹一定是AVL樹return _IsAVLTree(root->_left) && _IsAVLTree(root->_right);}int _Size(Node* root){if (root == nullptr) return 0;return _Size(root->_left) + _Size(root->_right) + 1;}private:Node* _root = nullptr;
};

2.Test.cpp

#define _CRT_SECURE_NO_WARNINGS 1#include<vector>#include"AVLTree.h"void TestAVLTree1()
{AVLTree<int, int> t;//常規(guī)的測試用例 //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.IsAVLTree() << endl;
}void TestAVLTree2()
{const 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);}size_t begin1 = clock();AVLTree<int, int> t;for (auto e : v){t.Insert(make_pair(e, e));}size_t end1 = clock();cout << "Insert:" << end1 - begin1 << endl;cout << t.IsAVLTree() << endl;cout << t.Height() << endl;cout << t.Size() << endl;size_t begin2 = clock();//查找確定在的值 /*for (auto e : v){t.Find(e);}*///查找隨機值for (size_t i = 0; i < N; i++){t.Find((rand() + i));}size_t end2 = clock();cout << "Find:" << end2 - begin2 << endl;
}int main()
{//TestAVLTree1();//TestAVLTree2();return 0;
}