【C++】第十九節—一文萬字詳解 | AVL樹實現

好久不見，我是云邊有個稻草人，偶爾中二博主與你分享C++領域專業知識^(*￣(oo)￣)^

《C++》—本篇文章所屬專欄—持續更新中—歡迎訂閱~喔

目錄

一、AVL的概念

二、AVL樹的實現

2.1 AVL樹的結構

2.2?AVL樹的插入

【AVL樹插入?個值的大概過程】

【平衡因?更新】

【插?結點及更新平衡因?的代碼實現】?

2.3 旋轉

【旋轉的原則】

【右單旋+兩個坑+代碼實現】

【左單旋+代碼實現】

【左右雙旋+代碼實現】

【右左雙旋+代碼實現】

2.4?AVL樹的查找

2.5?AVL樹平衡檢測

2.6?AVL樹的刪除

三、完整代碼

AVLTree.h

test.cpp?

正文開始——

一、AVL的概念

  • AVL樹是最先發明的?平衡?叉查找樹，AVL是?顆空樹，或者具備下列性質的?叉搜索樹：它的 左右?樹都是AVL樹，且左右?樹的?度差的絕對值不超過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樹整體結點數量和分布和完全?叉樹類似，?度可以控制在logN，那么增刪查改的效率也可 以控制在O(logN) ，相??叉搜索樹有了本質的提升

二、AVL樹的實現

2.1 AVL樹的結構
template<class K,class V>
struct AVLTreeNode
{//相比于二叉搜索樹多了parent和平衡因子pair<K, V> _kv;AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;int _bf;//balance factorAVLTreeNode(const pair<K, V> pair):_kv(pair),_left(nullptr),_right(nullptr),_parent(nullptr)_bf(0){ }
};template<class K, class V>
class AVLTree
{typedef AVLTreeNode<K, V> Node;
public://......
private:Node* _root = nullptr;
};
2.2?AVL樹的插入
【AVL樹插入?個值的大概過程】
  1. 插入?個值按?叉搜索樹規則進行插?。
  2. 新增結點以后，只會影響祖先結點的?度，也就是可能會影響部分祖先結點的平衡因?，所以更新 從新增結點->根結點路徑上的平衡因?，實際中最壞情況下要更新到根，有些情況更新到中間就可 以停?了，具體情況我們下?再詳細分析。
  3. 更新平衡因?過程中沒有出現問題，則插?結束
  4. 更新平衡因?過程中出現不平衡，對不平衡?樹旋轉，旋轉后本質調平衡的同時，本質降低了?樹的?度，不會再影響上?層，所以插?結束。
【平衡因?更新】

更新原則：

  • 平衡因? = 右?樹?度-左?樹?度
  • 只有?樹?度變化才會影響當前結點平衡因?。
  • 插?結點，會增加?度，所以新增結點在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，會影響parent的?親結點的平衡因?，所以要繼續向 上更新。
  • 更新后parent的平衡因?等于2 或 -2，更新前更新中parent的平衡因?變化為1->2 或者 -1->-2，說 明更新前parent?樹?邊??邊低，新增的插?結點在?的那邊，parent所在的?樹?的那邊更高了，破壞了平衡，parent所在的?樹不符合平衡要求，需要旋轉處理，旋轉的?標有兩個：1、把 parent子樹旋轉平衡。2、降低parent?樹的?度，恢復到插?結點以前的?度。所以旋轉后也不 需要繼續往上更新，插?結束。
  • 不斷更新，更新到根，跟的平衡因子是1或-1也停止了。

根據上面的更新規則和更新停止的條件思考一下下面的實際場景：

【插?結點及更新平衡因?的代碼實現】?
bool Insert(const pair<K,V>& kv)
{// 1.找到空位置插入新結點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->_left;}else if(cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else{return false;}}cur = new Node(kv);if (parent->_kv.first > kv.first){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;// 2.更新平衡因子while (parent){if (cur == parent->_left){parent->_bf--;}else if (cur == parent->_right){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){//旋轉break;}else{assert(false);}}return true;
}
2.3 旋轉
【旋轉的原則】
  1. 保持搜索樹的規則
  2. 讓旋轉的樹從不滿足變平衡，其次降低旋轉樹的高度旋轉總共分為四種，左單旋/右單旋/左右雙旋/右左雙旋。 說明：下面的圖中，有些結點我們給的是具體值，如10和5等結點，這?是為了方便講解，實際中是什么值都可以，只要大小關系符合搜索樹的性質即可。
【右單旋+兩個坑+代碼實現】
  • 本圖1展?的是10為根的樹，有a/b/c抽象為三棵高度為h的子樹(h>=0)，a/b/c均符合AVL樹的要求。10可能是整棵樹的根，也可能是?個整棵樹中局部的?樹的根。這?a/b/c是?度為h的?樹，是?種概括抽象表示，他代表了所有右單旋的場景，實際右單旋形態有很多種，具體圖2/圖3/圖4/ 圖5進?了詳細描述。
  • 在a?樹中插??個新結點，導致a?樹的?度從h變成h+1，不斷向上更新平衡因?，導致10的平衡因?從-1變成-2，10為根的樹左右?度差超過1，違反平衡規則。10為根的樹左邊太?了，需要往右邊旋轉，控制兩棵樹的平衡。
  • 旋轉核?步驟，因為5 < b?樹的值 < 10，將b變成10的左?樹，10變成5的右?樹，5變成這棵樹新 的根，符合搜索樹的規則，控制了平衡，同時這棵的?度恢復到了插?之前的h+2，符合旋轉原則。如果插?之前10整棵樹的?個局部?樹，旋轉后不會再影響上?層，插?結束了。

形象的描述

看著下面的圖一，左邊高，那就想象著把10節點往右邊按下去，把b作為10的左子樹，10一整棵作為5的右子樹，5作為一整棵樹的根節點，完美~

兩個坑：

代碼實現：

先把上面的旋轉過程想清楚，再思考遇到的兩個坑，下面的右單旋代碼就不難實現。

節點相互指來指去可能會比較繞，要自己靜下心來好好想清楚，按照心里思考之后正確的順序去改變指向。也就是改變了四個指向

void RotateR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;//subLR可能為空，也就是h高度為0時if (subLR)subLR->_parent = parent;//保存這里根節點的parentNode* ppNode = parent->_parent;parent->_parent = subL;subL->_right = parent;//有兩種判斷是否是根節點的方法//if(ppNode == nullptr)if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}subL->_bf = 0;parent->_bf = 0;
}
【左單旋+代碼實現】
  • 本圖展?的是10為根的樹，有a/b/c抽象為三棵?度為h的?樹(h>=0)，a/b/c均符合AVL樹的要 求。10可能是整棵樹的根，也可能是?個整棵樹中局部的?樹的根。這?a/b/c是?度為h的?樹， 是?種概括抽象表?，他代表了所有右單旋的場景，實際右單旋形態有很多種，具體跟上?左旋類 似。
  • 在a?樹中插??個新結點，導致a?樹的?度從h變成h+1，不斷向上更新平衡因?，導致10的平 衡因?從1變成2，10為根的樹左右?度差超過1，違反平衡規則。10為根的樹右邊太?了，需要往 左邊旋轉，控制兩棵樹的平衡。
  • 旋轉核?步驟，因為10 < b?樹的值 < 15，將b變成10的右?樹，10變成15的左?樹，15變成這棵 樹新的根，符合搜索樹的規則，控制了平衡，同時這棵的?度恢復到了插?之前的h+2，符合旋轉 原則。如果插?之前10整棵樹的?個局部?樹，旋轉后不會再影響上?層，插?結束了。

代碼實現：

會了上面的右單旋的兩個坑和代碼的實現，這里的左單旋一樣的過程，也是小case啦，嘗試自己寫一下

void RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;Node* ppNode = parent->_parent;parent->_parent = subR;if (ppNode == nullptr){_root = subR;subR->_parent = nullptr;}else{subR->parent = ppNode;if (parent == ppNode->_left){ppNode->_left = subR;}else{ppNode->_right = subR;}}subR->_bf = parent->_bf = 0;
}

看了上面的圖發現，右單旋或者左單旋都是純粹的左邊高或者右邊高，那如果不是純粹的左邊高或者右邊高該怎么辦？雙旋！

【左右雙旋+代碼實現】

通過圖7和圖8可以看到，左邊?時，如果插?位置不是在a?樹，?是插?在b?樹，b?樹?度從h變 成h+1，引發旋轉，右單旋?法解決問題，右單旋后，我們的樹依舊不平衡。右單旋解決的純粹的左邊?，但是插?在b?樹中，10為跟的?樹不再是單純的左邊?，對于10是左邊?，但是對于5是右邊高，需要?兩次旋轉才能解決，以5為旋轉點進??個左單旋，以10為旋轉點進??個右單旋，這棵樹 這棵樹就平衡了。

（默默地吐槽一句，qq的長截圖是咋回事的嘛，老是拼接中斷。回答我，look my eyes！）

（回到正題）?

  • 圖7和圖8分別為左右雙旋中h==0和h==1具體場景分析，下?我們將a/b/c?樹抽象為?度h的AVL?樹進?分析，另外我們需要把b?樹的細節進?步展開為8和左?樹?度為h-1的e和f?樹，因為 我們要對b的?親5為旋轉點進?左單旋，左單旋需要動b樹中的左?樹。b?樹中新增結點的位置 不同，平衡因?更新的細節也不同，通過觀察8的平衡因?不同，這?我們要分三個場景討論。
  • 場景1：h >= 1時，新增結點插?在e?樹，e?樹?度從h-1并為h并不斷更新8->5->10平衡因?，引發旋轉，其中8的平衡因?為-1，旋轉后8和5平衡因?為0，10平衡因?為1。
  • 場景2：h >= 1時，新增結點插?在f?樹，f?樹?度從h-1變為h并不斷更新8->5->10平衡因?，引發旋轉，其中8的平衡因?為1，旋轉后8和10平衡因?為0，5平衡因?為-1。
  • 場景3：h == 0時，a/b/c都是空樹，b??就是?個新增結點，不斷更新5->10平衡因?，引發旋 轉，其中8的平衡因?為0，旋轉后8和10和5平衡因?均為0。

代碼實現：

void RotateLR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;//先進行左單旋RotateL(subL);//再進行右單旋RotateR(parent);//根據bf分情況來更新平衡因子if (bf == -1){subL->_bf = 0;parent->_bf = 1;subLR->_bf = 0;}else if (bf == 1){subL->_bf = -1;parent->_bf = 0;subLR->_bf = 0;}else if (bf == 0){subL->_bf = 0;parent->_bf = 0;subLR->_bf = 0;}else{assert(false);}
}
【右左雙旋+代碼實現】
  • 跟左右雙旋類似，下?我們將a/b/c?樹抽象為?度h的AVL?樹進?分析，另外我們需要把b?樹的 細節進?步展開為12和左?樹?度為h-1的e和f?樹，因為我們要對b的?親15為旋轉點進?右單 旋，右單旋需要動b樹中的右?樹。b?樹中新增結點的位置不同，平衡因?更新的細節也不同，通 過觀察12的平衡因?不同，這?我們要分三個場景討論。
  • 場景1：h >= 1時，新增結點插?在e?樹，e?樹?度從h-1變為h并不斷更新12->15->10平衡因 ?，引發旋轉，其中12的平衡因?為-1，旋轉后10和12平衡因?為0，15平衡因?為1。
  • 場景2：h >= 1時，新增結點插?在f?樹，f?樹?度從h-1變為h并不斷更新12->15->10平衡因?， 引發旋轉，其中12的平衡因?為1，旋轉后15和12平衡因?為0，10平衡因?為-1。
  • 場景3：h == 0時，a/b/c都是空樹，b??就是?個新增結點，不斷更新15->10平衡因?，引發旋 轉，其中12的平衡因?為0，旋轉后10和12和15平衡因?均為0。

代碼實現：

	void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;//先進行右單旋RotateR(subR);//再進行左單旋RotateL(parent);//更新平衡因子if (bf == -1){subRL->_bf = 0;subR->_bf = 1;parent->_bf = 0;}else if (bf == 1){subRL->_bf = 0;subR->_bf = 0;parent->_bf = -1;}else if(bf == 0){subRL->_bf = 0;subR->_bf = 0;parent->_bf = 0;}else{assert(false);}}
2.4?AVL樹的查找

那?叉搜索樹邏輯實現即可，搜索效率為 O(logN)

	//AVL樹的查找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;}
2.5?AVL樹平衡檢測

怎么去檢測AVL樹是否合格呢？檢查每個結點的平衡因子？那如果每個結點里面存儲的平衡因子本身就是錯的怎么辦？所以這種辦法不可行

判斷實現的AVL樹是否合格，可以通過檢查左右?樹?度差的程序進?反向驗證，同時檢查?下結點的平衡因?更新是否出現了問題。

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 TestAVLTree1()
{AVLTree<int, 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 = 100000;vector<int> v;v.reserve(N);srand(time(0));for (size_t i = 0; i < N; i++){v.push_back(rand() + i);}size_t begin2 = clock();AVLTree<int, 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;
}
2.6?AVL樹的刪除

AVL樹的刪除本章節不做講解，有興趣的同學可參考：《殷?昆 數據結構：??向對象?法與C++語 ?描述》中講解。

三、完整代碼

AVLTree.h
#pragma once
#include<iostream>
#include<assert.h>
#include<vector>using namespace std;template<class K, class V>
struct AVLTreeNode
{// 需要parent指針，后續更新平衡因子可以看到pair<K, V> _kv;AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;int _bf; // balance factorAVLTreeNode(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;
public:bool Insert(const pair<K, 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->_right){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){// 旋轉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 InOrder(){_InOrder(_root);cout << endl;}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;}int Height(){return _Height(_root);}int Size(){return _Size(_root);}
private: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);}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;}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* ppNode = parent->_parent;subL->_right = parent;parent->_parent = subL;//if (ppNode == nullptr)if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}parent->_bf = 0;subL->_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){subL->_bf = 0;parent->_bf = 1;subLR->_bf = 0;}else if (bf == 1){subL->_bf = -1;parent->_bf = 0;subLR->_bf = 0;}else if (bf == 0){subL->_bf = 0;parent->_bf = 0;subLR->_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);}}
private:Node* _root = nullptr;
};// 測試代碼
void TestAVLTree1()
{AVLTree<int, 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){//這里是一個調試打斷點的技巧(類似于條件斷點，斷點不能打在空語句，寫一句無關緊要的代碼停一下即可)/*if (e == 14){int x = 0;}*/t.Insert({ e, e });cout << "Insert:" << e << "->";cout << t.IsBalanceTree() << endl;}t.InOrder();cout << t.IsBalanceTree() << 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 begin2 = clock();AVLTree<int, int> t;for (auto e : v){t.Insert(make_pair(e, e));}size_t end2 = clock();cout << t.IsBalanceTree() << endl;cout << "Insert:" << end2 - begin2 << 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;
}
test.cpp?
#include"AVLTree.h"int main()
{//TestAVLTree1();TestAVLTree2();return 0;
}

跟著文章把知識和代碼邏輯順一遍

博主也是懶，斷斷續續終于寫完了......

看看今天能不能繼續更（對了，要是忽然想到尷尬的事情，死去的回憶開始攻擊我怎么辦，尷尬的原地攥緊兩個拳頭開始齜牙咧嘴）

完——

Call You Tonight

至此結束——

我是云邊有個稻草人

期待與你的下一次相遇......

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/916714.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/916714.shtml
英文地址，請注明出處：http://en.pswp.cn/news/916714.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

【Delphi】快速理解泛型（Generics）

【Delphi】快速理解泛型（Generics）

Delphi的泛型&#xff08;generics&#xff09;是一項強大的特性&#xff0c;它使得代碼更加靈活、類型安全&#xff0c;并且可以實現各種通用的數據結構和算法。下面我將為你詳細介紹Delphi中的泛型&#xff0c;包括基本概念、語法、常用實例&#xff0c;以及使用建議。Delphi…
閱讀更多...
Java Stream流的使用

Java Stream流的使用

獲取Stream流 單列集合直接使用stream()方法 List<String> list Arrays.asList("a", "b", "c"); Stream<String> stream list.stream(); // 獲取順序流數組使用靜態方法Arrays.stream() String[] array {"a", "b&…
閱讀更多...
前端實現添加水印，兩種方式

前端實現添加水印，兩種方式

一、自定義指令的方式/*需求&#xff1a;給整個頁面添加背景水印。思路&#xff1a;1、使用 canvas 特性生成 base64 格式的圖片文件&#xff0c;設置其字體大小&#xff0c;顏色等。2、將其設置為背景圖片&#xff0c;從而實現頁面或組件水印效果使用&#xff1a;設置水印文案…
閱讀更多...
使用LangChain構建法庭預定智能體：結合vLLM部署的Qwen3-32B模型

使用LangChain構建法庭預定智能體：結合vLLM部署的Qwen3-32B模型

文章目錄 技術架構概述 核心實現步驟 1. 配置vLLM與Qwen3-32B模型 2. 定義工具（Tools） 3. 構建Agent系統 4. 運行與交互 關鍵技術亮點 1. 工具調用自動化 2. Hermes解析器優勢 3. 對話記憶管理 實際運行效果 性能優化建議 擴展應用場景 總結 在人工智能應用開發中，如何讓大語…
閱讀更多...
vscode開發微信小程序

vscode開發微信小程序

下載插件 插件下載位置 1.微信小程序開發工具 2.vscode weapp api 3.vscode wxml 4.vscode-wechat 創建項目 終端運行命令 cd 到要創建項目的目錄執行命令&#xff1a;vue create -p dcloudio/uni-preset-vue test test就是項目名稱 選擇默認模板&#xff0c;回車 出現下圖這…
閱讀更多...
板凳-------Mysql cookbook學習 （十二--------3_3)

板凳-------Mysql cookbook學習 （十二--------3_3)

https://cloud.tencent.com/developer/article/1454690 侯哥的Python分享 # 創建節點 class Node(object):def __init__(self,item):self.element itemself.next None# 創建單鏈表類 class SingleLinkList(object):def __init__(self):self.header Noneself.length 0# 1、判…
閱讀更多...
Flutter開發實戰之CI/CD與發布流程

Flutter開發實戰之CI/CD與發布流程

第12章：CI/CD與發布流程 在前面的章節中，我們學習了Flutter應用開發的各個方面，從基礎UI構建到復雜的狀態管理，從網絡請求到本地存儲。現在，我們將探討一個同樣重要但常被忽視的話題：如何將我們精心開發的應用高效、可靠地發布到各大應用商店。 想象一下，你花費了數月…
閱讀更多...
ElasticSearch 的3種數據遷移方案

ElasticSearch 的3種數據遷移方案

在實際工作中&#xff0c;我們經常會遇到需要將自建的 Elasticsearch 遷移上云&#xff0c;或者遷移到其他 ES 集群的情況。這時&#xff0c;選擇合適的數據遷移方案就顯得尤為重要啦。今天就來給大家介紹三種常用的遷移方案&#xff0c;分別是 COS 快照、logstash 和 elastics…
閱讀更多...
MySQL 中的“雙路排序”與“單路排序”：原理、判別與實戰調優

MySQL 中的“雙路排序”與“單路排序”：原理、判別與實戰調優

一句話導讀 ORDER BY 不能走索引時&#xff0c;MySQL 會在 Server 層做一次 filesort。內部實現分 單路&#xff08;全字段&#xff09; 與 雙路&#xff08;rowid&#xff09; 兩種&#xff1b;了解它們的觸發條件、判別方法與調優思路&#xff0c;是 SQL 性能優化的必修課。一…
閱讀更多...
OpenLayers 綜合案例-信息窗體-彈窗

OpenLayers 綜合案例-信息窗體-彈窗

看過的知識不等于學會。唯有用心總結、系統記錄&#xff0c;并通過溫故知新反復實踐&#xff0c;才能真正掌握一二 作為一名摸爬滾打三年的前端開發&#xff0c;開源社區給了我飯碗&#xff0c;我也將所學的知識體系回饋給大家&#xff0c;助你少走彎路&#xff01; OpenLayers…
閱讀更多...
GaussDB 開發基本規范

GaussDB 開發基本規范

1 集中式1.1數據庫價值特性推薦特性分類特性列表說明表類型PARTITION表數據分區存儲引擎行存儲按行順序存儲表&#xff0c;建議點查&#xff0c;增刪改操作較多場景下使用事務事務塊顯式啟動事務單語句事務不顯式啟動事務&#xff0c;單語句即為事務擴容在線擴容擴節點和數據重…
閱讀更多...
工作中使用git可能遇到的場景

工作中使用git可能遇到的場景

1.main歷史發布版本出問題需要查看&#xff0c;怎么切換歷史發布版本&#xff1f;git reset --hard commitid 更新本地庫和代碼2.A分支的代碼已經做過一些功能&#xff0c;想遷移到B分支當前在A分支git checkout B &#xff08;切換到B分支&#xff09;git cherry-pick A的com…
閱讀更多...
【Spring AI】本地大型語言模型工具-Ollama

【Spring AI】本地大型語言模型工具-Ollama

Ollama 是一個專注于在本地運行大型語言模型&#xff08;LLM&#xff09;的工具&#xff0c;支持多種開源模型&#xff08;如 Llama 3、Mistral、Gemma 等&#xff09;&#xff0c;提供簡單的命令行和 API 接口。<dependency><groupId>org.springframework.ai</…
閱讀更多...
電機S加減速

電機S加減速

STM32步進電機S型加減速算法_stm32___build__-2048 AI社區 以上&#xff0c;電機加減速說的非常清楚&#xff0c;收藏點贊&#xff01;
閱讀更多...
一、初識 Linux 與基本命令

一、初識 Linux 與基本命令

作者&#xff1a;IvanCodes 日期&#xff1a;2025年7月28日 專欄&#xff1a;Linux教程 思維導圖 一、Linux 簡介 1.1 什么是 Linux? Linux 是一種自由、開源的類Unix操作系統內核&#xff0c;由林納斯托瓦茲 (Linus Torvalds) 在1991年首次發布。我們通常所說的 “Linux 系統…
閱讀更多...
解決angular與jetty websocket 每30s自動斷連的問題

解決angular與jetty websocket 每30s自動斷連的問題

背景&#xff1a;前端&#xff1a;angular 12&#xff0c;websocket接口由lib.dom.d.ts提供后端&#xff1a;java&#xff0c;websocket接口由jetty 12提供問題現象&#xff1a;前端連上server后&#xff0c;每隔30s就會斷開&#xff0c;由于長時間空閑&#xff0c;會導致webso…
閱讀更多...
【機器學習深度學習】模型私有化部署與微調訓練：賦能特定問題處理能力

【機器學習深度學習】模型私有化部署與微調訓練：賦能特定問題處理能力

目錄 前言 一、私有化部署的背景&#xff1a;通用能力 ≠ 企業實用 暴露問題 二、微調訓練的核心目的 2.1 動作一&#xff1a;私有化部署&#xff08;Private Deployment&#xff09; 2.2 動作二&#xff1a;領域微調&#xff08;Domain Fine-Tuning&#xff09; 2.3 微…
閱讀更多...
Seq2Seq學習筆記

Seq2Seq學習筆記

Seq2Seq模型概述Seq2Seq&#xff08;Sequence-to-Sequence&#xff09;是一種基于深度學習的序列生成模型&#xff0c;主要用于處理輸入和輸出均為序列的任務&#xff0c;如機器翻譯、文本摘要、對話生成等。其核心思想是將可變長度的輸入序列映射為另一個可變長度的輸出序列。…
閱讀更多...
react useId

react useId

useId useId 是 React 18 引入的一個內置 Hook&#xff0c;用于生成唯一且穩定的 ID &#xff0c; 主要用于&#xff0c;解決在客戶端和服務器端渲染&#xff08;SSR&#xff09;時&#xff0c;動態生成 ID 可能導致的沖突問題&#xff1b; 特別適合用于&#xff0c;需要關聯 H…
閱讀更多...
排水管網實時監測筑牢城市安全防線

排水管網實時監測筑牢城市安全防線

排水管網的實時監測工作&#xff0c;強調其對于保障城市安全的重要作用。“排水管網”明確了具體的關注對象&#xff0c;它是城市基礎設施的重要組成部分&#xff0c;承擔著雨水、污水排放等關鍵功能。“實時監測”突出了監測的及時性和持續性&#xff0c;意味著能夠隨時獲取排…
閱讀更多...
最新文章

Copyright @ 2022~2023