一、前言AVL樹又稱為平衡二叉樹它基于二叉搜索樹并通過平衡而得到。在前面的學(xué)習(xí)中我們提到二叉搜索樹可以提高搜索數(shù)據(jù)的效率但在數(shù)據(jù)有序的情況下會(huì)退化為單支樹此時(shí)在樹中查找元素就得遍歷一整個(gè)分支時(shí)間復(fù)雜度也會(huì)退化至O(N)。如果有一種算法可以使二叉搜索樹時(shí)刻保持左右子樹的平衡就可以避免這種最壞情況。二、AVL樹的性質(zhì)當(dāng)我們向二叉搜索樹中插入新節(jié)點(diǎn)時(shí)如果能用某種方法時(shí)刻保證樹中每個(gè)節(jié)點(diǎn)的左右子樹高度之差不超過1就可以降低整棵樹的高度保證每條分支的平衡AVL樹的性質(zhì)如下AVL樹可以是空樹一顆AVL樹的左右子樹都是AVL樹一顆AVL樹的左右子樹高度差不超過1三、AVL樹節(jié)點(diǎn)的定義AVL樹的左右子樹高度差不能超過1但是如何便捷的去檢測該性質(zhì)是否被打破呢我們可以在節(jié)點(diǎn)中定義一個(gè)平衡因子如果左子樹比右子樹高一層那么平衡因子就為-1如果左右子樹一樣高平衡因子就為0如果右子樹比左子樹高一層那么平衡因子就為1這三種情況下AVL樹的性質(zhì)都沒有被打破。按照這個(gè)規(guī)則如果平衡因子為-2、2或其他值則說明左右子樹已經(jīng)失衡性質(zhì)被打破。在調(diào)整失衡的AVL樹時(shí)我們需要頻繁的訪問父節(jié)點(diǎn)所以在AVL樹中我們需要使用三叉鏈因此AVL樹的節(jié)點(diǎn)除了包含左右子節(jié)點(diǎn)的指針還需要一個(gè)指向父節(jié)點(diǎn)的指針另外需要說明一下本文中我們使用key/value模型的AVL樹AVL樹節(jié)點(diǎn)的定義如下這里簡單介紹一下pairpair可以將兩個(gè)數(shù)據(jù)組成一組元素因此對(duì)于key/value模型這種需要用到兩個(gè)數(shù)據(jù)為一組的元素時(shí)就可以使用內(nèi)部的成員變量為first和second其主要使用方法為pairT1, T2 p1(v1, v2); //輸入兩個(gè)數(shù)據(jù)創(chuàng)建pair類型變量 make_pair(v1, v2); //輸入兩個(gè)數(shù)據(jù)通過函數(shù)創(chuàng)建pair類型變量 p1.first //訪問p1的第一個(gè)數(shù)據(jù) p1.second //訪問p1的第二個(gè)數(shù)據(jù)四、AVL樹的插入及更新平衡因子向AVL樹中插入節(jié)點(diǎn)與向二叉搜索樹中插入節(jié)點(diǎn)的過程基本相同唯一的區(qū)別就是AVL樹在插入節(jié)點(diǎn)后可能存在失衡的情況需要調(diào)整。我們先按照二叉搜索樹的規(guī)則將節(jié)點(diǎn)插入到AVL樹中并判斷插入的節(jié)點(diǎn)在父節(jié)點(diǎn)的左邊還是右邊.按照平衡因子的規(guī)則如果新節(jié)點(diǎn)插入到了父節(jié)點(diǎn)的左側(cè)那么父節(jié)點(diǎn)的平衡因子-1如果新節(jié)點(diǎn)插入到了父節(jié)點(diǎn)的右側(cè)那么父節(jié)點(diǎn)的平衡因子1以上便是新增節(jié)點(diǎn)的父節(jié)點(diǎn)平衡因子可能的變化情況。但是插入一個(gè)節(jié)點(diǎn)不但會(huì)影響父節(jié)點(diǎn)還可能會(huì)影響到祖先節(jié)點(diǎn)。我們觀察上面的四種可能其中左邊的兩種情況下插入節(jié)點(diǎn)后以父節(jié)點(diǎn)為根的子樹高度發(fā)生了變化在右邊的兩種情況下插入節(jié)點(diǎn)后以父節(jié)點(diǎn)為根的子樹高度沒有發(fā)生變化。觀察過后可以發(fā)現(xiàn)當(dāng)父節(jié)點(diǎn)的平衡因子從0變?yōu)?/-1后子樹高度發(fā)生變化當(dāng)父節(jié)點(diǎn)的平衡因子從1/-1變?yōu)?后子樹高度不發(fā)生變化如果以父節(jié)點(diǎn)為根的子樹高度沒有發(fā)生變化那么就不會(huì)影響到祖先節(jié)點(diǎn)的平衡因子如果高度變了就會(huì)繼續(xù)向上影響到祖先節(jié)點(diǎn)的平衡因子因此我們可以通過判斷節(jié)點(diǎn)的插入位置來計(jì)算父節(jié)點(diǎn)的平衡因子進(jìn)而判斷子樹高度是否發(fā)生變化再進(jìn)一步計(jì)算對(duì)祖先節(jié)點(diǎn)平衡因子的影響來判斷AVL樹是否失衡。至此我們已經(jīng)可以開始寫插入新節(jié)點(diǎn)和更新平衡因子的代碼了// AVL樹的結(jié)構(gòu)定義 templateclass K, class V class AVLtree { typedef AVLnodeK, V Node; // 定義節(jié)點(diǎn)類型別名 public: // 插入函數(shù)向AVL樹中插入一個(gè)鍵值對(duì) bool insert(const pairK, V kv) { // 情況1空樹直接創(chuàng)建根節(jié)點(diǎn) if (_root nullptr) { _root new Node(kv); // 創(chuàng)建新節(jié)點(diǎn)作為根節(jié)點(diǎn) return true; // 插入成功 } // 初始化指針parent用于記錄當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)cur用于遍歷樹 Node* parent nullptr; Node* cur _root; // 步驟1按照二叉搜索樹的規(guī)則找到插入位置 while (cur) { if (cur-_kv.first kv.first) // 當(dāng)前節(jié)點(diǎn)的key小于插入key向右子樹查找 { parent cur; // 更新父節(jié)點(diǎn) cur cur-_right; // 移動(dòng)到右子樹 } else if (cur-_kv.first kv.first) // 當(dāng)前節(jié)點(diǎn)的key大于插入key向左子樹查找 { parent cur; // 更新父節(jié)點(diǎn) cur cur-_left; // 移動(dòng)到左子樹 } else // 找到相同key插入失敗不允許重復(fù)key { return false; } } // 步驟2創(chuàng)建新節(jié)點(diǎn)并插入到正確位置 // 此時(shí)cur為nullptrparent是待插入位置的父節(jié)點(diǎn) cur new Node(kv); // 創(chuàng)建新節(jié)點(diǎn) // 判斷新節(jié)點(diǎn)應(yīng)該插入到父節(jié)點(diǎn)的左側(cè)還是右側(cè) if (parent-_kv.first cur-_kv.first) // 父節(jié)點(diǎn)的key小于新節(jié)點(diǎn)的key parent-_right cur; // 插入到右子樹 else parent-_left cur; // 插入到左子樹 // 設(shè)置新節(jié)點(diǎn)的父指針 cur-_parent parent; // 步驟3更新平衡因子并檢查是否需要旋轉(zhuǎn) // 從插入點(diǎn)的父節(jié)點(diǎn)開始向上更新平衡因子直到根節(jié)點(diǎn)或平衡因子變?yōu)? while (parent) { // 根據(jù)新節(jié)點(diǎn)插入的位置更新父節(jié)點(diǎn)的平衡因子 if (parent-_left cur) // 新節(jié)點(diǎn)插入在父節(jié)點(diǎn)的左側(cè) parent-ph--; // 左子樹高度增加平衡因子減1 else // 新節(jié)點(diǎn)插入在父節(jié)點(diǎn)的右側(cè) parent-ph; // 右子樹高度增加平衡因子加1 // 檢查更新后的平衡因子 if (parent-ph 0) // 平衡因子變?yōu)?說明以parent為根的子樹高度不變 { // 子樹高度沒有變化不會(huì)影響更上層的平衡因子更新結(jié)束 break; } else if (parent-ph 1 || parent-ph -1) // 平衡因子為1或-1子樹高度發(fā)生變化 { // 子樹高度變化需要繼續(xù)向上更新祖先節(jié)點(diǎn)的平衡因子 cur parent; // 當(dāng)前節(jié)點(diǎn)上移 parent parent-_parent; // 父節(jié)點(diǎn)上移 } // 當(dāng)平衡因子是-2或2時(shí)說明以parent為根的子樹已經(jīng)失衡需要進(jìn)行旋轉(zhuǎn)調(diào)整 else if (parent-ph 2 || parent-ph -2) { // 根據(jù)cur和parent的平衡因子判斷失衡類型選擇相應(yīng)的旋轉(zhuǎn)方式 // 情況1右單旋 - 新節(jié)點(diǎn)插入在較高左子樹的左側(cè) if (cur-ph -1 parent-ph -2) rotateR(parent); // 調(diào)用右單旋函數(shù) // 情況2左單旋 - 新節(jié)點(diǎn)插入在較高右子樹的右側(cè) else if (cur-ph 1 parent-ph 2) rotateL(parent); // 調(diào)用左單旋函數(shù) // 情況3左右雙旋 - 新節(jié)點(diǎn)插入在較高左子樹的右側(cè) else if (cur-ph 1 parent-ph -2) rotateLR(parent); // 調(diào)用左右雙旋函數(shù) // 情況4右左雙旋 - 新節(jié)點(diǎn)插入在較高右子樹的左側(cè) else if (cur-ph -1 parent-ph 2) rotateRL(parent); // 調(diào)用右左雙旋函數(shù) else assert(false); // 不應(yīng)該出現(xiàn)其他情況如果出現(xiàn)則程序終止 // 旋轉(zhuǎn)完成后以parent為根的子樹已經(jīng)重新平衡更新結(jié)束 break; } else { // 平衡因子出現(xiàn)異常值既不是0、±1、±2程序終止 assert(false); } } return true; // 插入成功 } Node* _root nullptr; // AVL樹的根節(jié)點(diǎn)指針 };五、AVL樹的平衡調(diào)整附動(dòng)圖如果在一顆原本平衡的AVL樹中插入一個(gè)新節(jié)點(diǎn)可能會(huì)造成失衡此時(shí)需要調(diào)整樹的結(jié)構(gòu)使之重新平衡這種調(diào)整方法稱為旋轉(zhuǎn)。根據(jù)樹的原本結(jié)構(gòu)和節(jié)點(diǎn)插入位置的不同分為四種情況和四種旋轉(zhuǎn)方式1新節(jié)點(diǎn)插入較高左子樹的左側(cè)右單旋問題來了如何判斷插入的新節(jié)點(diǎn)的方位呢很簡單以上面的情況為例插入新節(jié)點(diǎn)后60的平衡因子變成-2說明左子樹更高而30的平衡因子變成-1說明新節(jié)點(diǎn)插入到了30的左子樹。后面左單旋以及雙旋中都同理我們使用平衡因子就可以判斷新節(jié)點(diǎn)插入的位置右單旋代碼如下//右旋 void rotateR(Node* parent) { // 1. 保存相關(guān)節(jié)點(diǎn)指針 Node* subL parent-_left; // parent的左子樹較高左子樹 Node* subLR subL-_right; // subL的右子樹 Node* Pparent parent-_parent; // parent的父節(jié)點(diǎn)用于連接旋轉(zhuǎn)后的新子樹 // 2. 處理subLR的重新連接 parent-_left subLR; // 將subLR作為parent的新左孩子 if (subLR) // 如果subLR存在更新其父指針 { subLR-_parent parent; } // 3. 旋轉(zhuǎn)核心subL成為新的根parent成為subL的右子樹 subL-_right parent; // parent成為subL的右孩子 parent-_parent subL; // 更新parent的父指針指向subL // 4. 處理旋轉(zhuǎn)后新子樹與上層樹的連接 if (parent _root) // 如果parent是整棵樹的根節(jié)點(diǎn) { _root subL; // 更新根節(jié)點(diǎn)為subL subL-_parent nullptr; // 根節(jié)點(diǎn)的父指針置空 } else // parent不是根節(jié)點(diǎn) { // 判斷parent原來是其父節(jié)點(diǎn)的左孩子還是右孩子 if (Pparent-_left parent) { Pparent-_left subL; // 將subL連接到原parent的位置 } else { Pparent-_right subL; } subL-_parent Pparent; // 更新subL的父指針 } // 5. 更新平衡因子旋轉(zhuǎn)后parent和subL的高度都變?yōu)槠胶?parent-ph 0; // parent現(xiàn)在左右子樹高度相同 subL-ph 0; // subL現(xiàn)在左右子樹高度相同 }2新節(jié)點(diǎn)插入較高右子樹的右側(cè)左單旋因?yàn)樽髥涡脑砗陀覇涡穷愃频闹灰斫饬擞覇涡由蟿?dòng)圖的配合左單旋和后面的雙旋都是很好理解的左單旋代碼如下//左旋 void rotateL(Node* parent) { // 1. 保存相關(guān)節(jié)點(diǎn)指針 Node* subR parent-_right; // parent的右子樹較高右子樹 Node* subRL subR-_left; // subR的左子樹 Node* Pparent parent-_parent; // parent的父節(jié)點(diǎn)用于連接旋轉(zhuǎn)后的新子樹 // 2. 處理subRL的重新連接 parent-_right subRL; // 將subRL作為parent的新右孩子 if (subRL) // 如果subRL存在更新其父指針 { subRL-_parent parent; } // 3. 旋轉(zhuǎn)核心subR成為新的根parent成為subR的左子樹 subR-_left parent; // parent成為subR的左孩子 parent-_parent subR; // 更新parent的父指針指向subR // 4. 處理旋轉(zhuǎn)后新子樹與上層樹的連接 if (parent _root) // 如果parent是整棵樹的根節(jié)點(diǎn) { _root subR; // 更新根節(jié)點(diǎn)為subR subR-_parent nullptr; // 根節(jié)點(diǎn)的父指針置空 } else // parent不是根節(jié)點(diǎn) { // 判斷parent原來是其父節(jié)點(diǎn)的左孩子還是右孩子 if (Pparent-_left parent) { Pparent-_left subR; // 將subR連接到原parent的位置 } else { Pparent-_right subR; } subR-_parent Pparent; // 更新subR的父指針 } // 5. 更新平衡因子旋轉(zhuǎn)后parent和subR的高度都變?yōu)槠胶?parent-ph 0; // parent現(xiàn)在左右子樹高度相同 subR-ph 0; // subR現(xiàn)在左右子樹高度相同 }3新節(jié)點(diǎn)插入較高左子樹的右側(cè)先左單旋再右單旋左右雙旋這種情況又可以分為兩種情況不過這兩種情況都屬于在較高左子樹的右側(cè)插入處理方式都是相同的唯一的區(qū)別在于最后旋轉(zhuǎn)完成后更新平衡因子時(shí)的值不同。接下來我們以上面的那個(gè)情況為例展示左右雙旋的過程而下面的情況和上面的情況唯一的區(qū)別在于最后更新的平衡因子不同如何去決定每個(gè)節(jié)點(diǎn)更新后的平衡因子呢可以看到這兩種情況中如果在b下面插入新節(jié)點(diǎn)那么旋轉(zhuǎn)過后30和60的平衡因子更新成090的平衡因子更新成1如果在c下面插入新節(jié)點(diǎn)則是60和90的平衡因子更新成030的平衡因子更新成-1而新節(jié)點(diǎn)究竟插入到了b下面還是在c下面我們可以通過插入節(jié)點(diǎn)后60的平衡因子來判斷左右雙旋代碼如下//左右旋轉(zhuǎn) void rotateLR(Node* parent) { // 1. 記錄相關(guān)節(jié)點(diǎn)指針 Node* subL parent-_left; // parent的左子樹 Node* subLR subL-_right; // subL的右子樹新節(jié)點(diǎn)插入的位置 // 2. 記錄subLR的平衡因子用于判斷新節(jié)點(diǎn)插入的具體位置 int p subLR-ph; // 保存旋轉(zhuǎn)前的平衡因子 // 3. 雙旋操作先對(duì)subL進(jìn)行左旋再對(duì)parent進(jìn)行右旋 rotateL(parent-_left); // 對(duì)parent的左子樹進(jìn)行左單旋 rotateR(parent); // 對(duì)parent進(jìn)行右單旋 // 4. 根據(jù)subLR原來的平衡因子更新旋轉(zhuǎn)后的平衡因子 if (p 0) // 情況1subLR本身就是新插入的節(jié)點(diǎn) { subL-ph 0; // subL平衡 subLR-ph 0; // subLR平衡 parent-ph 0; // parent平衡 } else if (p 1) // 情況2新節(jié)點(diǎn)插入在subLR的右子樹 { subLR-ph 0; // subLR平衡 subL-ph -1; // subL左子樹比右子樹高1層 parent-ph 0; // parent平衡 } else if (p -1) // 情況3新節(jié)點(diǎn)插入在subLR的左子樹 { subLR-ph 0; // subLR平衡 subL-ph 0; // subL平衡 parent-ph 1; // parent右子樹比左子樹高1層 } else { assert(false); // 平衡因子異常程序終止 } }4新節(jié)點(diǎn)插入較高右子樹的左側(cè)先右單旋再左單旋右左雙旋這種情況和左右雙旋的情況原理一樣我們直接上動(dòng)圖和代碼右左雙旋的代碼如下//右左旋轉(zhuǎn) void rotateRL(Node* parent) { // 1. 記錄相關(guān)節(jié)點(diǎn)指針 Node* subR parent-_right; // parent的右子樹 Node* subRL subR-_left; // subR的左子樹新節(jié)點(diǎn)插入的位置 // 2. 記錄subRL的平衡因子用于判斷新節(jié)點(diǎn)插入的具體位置 int p subRL-ph; // 保存旋轉(zhuǎn)前的平衡因子 // 3. 雙旋操作先對(duì)subR進(jìn)行右旋再對(duì)parent進(jìn)行左旋 rotateR(parent-_right); // 對(duì)parent的右子樹進(jìn)行右單旋 rotateL(parent); // 對(duì)parent進(jìn)行左單旋 // 4. 根據(jù)subRL原來的平衡因子更新旋轉(zhuǎn)后的平衡因子 if (p 0) // 情況1subRL本身就是新插入的節(jié)點(diǎn) { subRL-ph 0; // subRL平衡 subR-ph 0; // subR平衡 parent-ph 0; // parent平衡 } else if (p -1) // 情況2新節(jié)點(diǎn)插入在subRL的左子樹 { subRL-ph 0; // subRL平衡 subR-ph 0; // subR平衡 parent-ph -1; // parent左子樹比右子樹高1層 } else if (p 1) // 情況3新節(jié)點(diǎn)插入在subRL的右子樹 { subRL-ph 0; // subRL平衡 subR-ph 1; // subR右子樹比左子樹高1層 parent-ph 0; // parent平衡 } else { assert(false); // 平衡因子異常程序終止 } }六、AVL樹的查找實(shí)現(xiàn)AVL樹的查找操作與普通二叉搜索樹完全相同因?yàn)锳VL樹本質(zhì)上是一棵平衡的二叉搜索樹保持了二叉搜索樹的性質(zhì)。查找的時(shí)間復(fù)雜度為 O(log N)其中N是樹中節(jié)點(diǎn)的數(shù)量。查找操作的實(shí)現(xiàn)如下// AVL樹的查找函數(shù) Node* Find(const K key) { Node* cur _root; // 從根節(jié)點(diǎn)開始查找 while (cur) { if (cur-_kv.first key) // 當(dāng)前節(jié)點(diǎn)的key小于目標(biāo)key向右子樹查找 { cur cur-_right; } else if (cur-_kv.first key) // 當(dāng)前節(jié)點(diǎn)的key大于目標(biāo)key向左子樹查找 { cur cur-_left; } else // 找到目標(biāo)節(jié)點(diǎn) { return cur; } } return nullptr; // 未找到目標(biāo)節(jié)點(diǎn) }查找操作的原理很簡單從根節(jié)點(diǎn)開始比較目標(biāo)key與當(dāng)前節(jié)點(diǎn)的key如果目標(biāo)key更大則向右子樹繼續(xù)查找如果目標(biāo)key更小則向左子樹繼續(xù)查找如果相等則找到目標(biāo)節(jié)點(diǎn)如果遍歷到空節(jié)點(diǎn)仍未找到則返回nullptr由于AVL樹保持了平衡查找操作的最壞時(shí)間復(fù)雜度為 O(log N)這比普通二叉搜索樹在最壞情況下的 O(N) 要好得多。七、AVL樹的平衡檢測為了驗(yàn)證我們實(shí)現(xiàn)的AVL樹是否正確我們需要編寫一個(gè)平衡檢測函數(shù)。這個(gè)函數(shù)有兩個(gè)主要作用檢查每個(gè)節(jié)點(diǎn)的左右子樹高度差是否不超過1AVL樹的基本性質(zhì)驗(yàn)證每個(gè)節(jié)點(diǎn)的平衡因子是否正確更新首先我們需要一個(gè)計(jì)算樹高度的輔助函數(shù)// 計(jì)算樹的高度遞歸實(shí)現(xiàn) int _Height(Node* root) { if (root nullptr) // 空樹高度為0 return 0; // 遞歸計(jì)算左右子樹的高度 int leftHeight _Height(root-_left); int rightHeight _Height(root-_right); // 返回較高的子樹高度加1當(dāng)前節(jié)點(diǎn)自身的高度 return leftHeight rightHeight ? leftHeight 1 : rightHeight 1; }接下來是平衡檢測的核心函數(shù)// 檢查AVL樹是否平衡遞歸實(shí)現(xiàn) bool _IsBalanceTree(Node* root) { // 空樹也是AVL樹 if (nullptr root) return true; // 計(jì)算當(dāng)前節(jié)點(diǎn)左右子樹的高度差 int leftHeight _Height(root-_left); int rightHeight _Height(root-_right); int diff rightHeight - leftHeight; // 實(shí)際計(jì)算的高度差 // 檢查高度差是否超過1絕對(duì)值大于等于2 if (abs(diff) 2) { cout root-_kv.first 節(jié)點(diǎn)高度差異常 endl; return false; } // 檢查平衡因子是否正確存儲(chǔ)的平衡因子應(yīng)與實(shí)際高度差一致 if (root-_bf ! diff) { cout root-_kv.first 節(jié)點(diǎn)平衡因子異常 endl; return false; } // 遞歸檢查左右子樹是否都是AVL樹 return _IsBalanceTree(root-_left) _IsBalanceTree(root-_right); } // 提供給外部的平衡檢測接口 bool IsBalanceTree() { return _IsBalanceTree(_root); }這個(gè)檢測函數(shù)的工作原理對(duì)于每個(gè)節(jié)點(diǎn)計(jì)算其左右子樹的實(shí)際高度差檢查高度差的絕對(duì)值是否超過1如果超過說明不平衡檢查節(jié)點(diǎn)存儲(chǔ)的平衡因子是否與實(shí)際高度差一致如果不一致說明平衡因子更新有誤遞歸檢查所有子樹八、AVL樹的測試為了驗(yàn)證AVL樹的正確性和性能我們可以編寫測試代碼。以下是兩個(gè)常用的測試用例8.1 基礎(chǔ)功能測試// 測試AVL樹的基本功能 void TestAVLTree1() { AVLTreeint, int t; // 測試用例1常規(guī)測試數(shù)據(jù) // int a[] { 16, 3, 7, 11, 9, 26, 18, 14, 15 }; // 測試用例2包含雙旋場景的特殊數(shù)據(jù) int a[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 }; // 插入所有測試數(shù)據(jù) for (auto e : a) { t.Insert({ e, e }); } // 中序遍歷輸出驗(yàn)證二叉搜索樹性質(zhì) t.InOrder(); // 檢查樹是否平衡 cout t.IsBalanceTree() endl; }8.2 性能和大數(shù)據(jù)量測試// 測試AVL樹的性能和大量數(shù)據(jù)插入 void TestAVLTree2() { const int N 100000; // 測試數(shù)據(jù)量 vectorint v; v.reserve(N); // 預(yù)分配空間 // 生成隨機(jī)數(shù) srand(time(0)); for (size_t i 0; i N; i) { v.push_back(rand() i); // 避免重復(fù) } // 測試插入性能 size_t begin2 clock(); AVLTreeint, int t; for (auto e : v) { t.Insert(make_pair(e, e)); } size_t end2 clock(); cout 插入 N 個(gè)節(jié)點(diǎn)耗時(shí) end2 - begin2 ms endl; // 驗(yàn)證平衡性 cout 樹是否平衡 t.IsBalanceTree() endl; cout 樹的高度 t.Height() endl; cout 樹的大小 t.Size() endl; // 測試查找性能 size_t begin1 clock(); // 查找所有存在的值 for (auto e : v) { t.Find(e); } size_t end1 clock(); cout 查找 N 個(gè)節(jié)點(diǎn)耗時(shí) end1 - begin1 ms endl; }性能測試的意義插入性能測試驗(yàn)證在大數(shù)據(jù)量下AVL樹仍能保持 O(log N) 的插入時(shí)間復(fù)雜度平衡性驗(yàn)證確保插入大量隨機(jī)數(shù)據(jù)后樹仍然保持平衡高度驗(yàn)證驗(yàn)證樹的高度確實(shí)在 O(log N) 范圍內(nèi)查找性能測試驗(yàn)證查找操作的時(shí)間復(fù)雜度為 O(log N)九、總結(jié)AVL樹是一種嚴(yán)格平衡的二叉搜索樹通過引入平衡因子和四種旋轉(zhuǎn)操作右單旋、左單旋、左右雙旋、右左雙旋來保持樹的平衡。其主要特點(diǎn)包括平衡性保證任何節(jié)點(diǎn)的左右子樹高度差不超過1時(shí)間復(fù)雜度增刪查改操作的時(shí)間復(fù)雜度均為 O(log N)適用場景適合查找頻繁、插入刪除相對(duì)較少的場景實(shí)現(xiàn)復(fù)雜度實(shí)現(xiàn)相對(duì)復(fù)雜需要維護(hù)平衡因子和進(jìn)行旋轉(zhuǎn)操作AVL樹的優(yōu)缺點(diǎn)優(yōu)點(diǎn)嚴(yán)格的平衡保證了最壞情況下的性能查找效率穩(wěn)定在 O(log N)適合內(nèi)存中的有序數(shù)據(jù)存儲(chǔ)缺點(diǎn)插入和刪除操作可能需要多次旋轉(zhuǎn)實(shí)現(xiàn)相對(duì)復(fù)雜平衡因子的維護(hù)增加了開銷在實(shí)際應(yīng)用中如果需要更簡單的實(shí)現(xiàn)可以考慮紅黑樹Red-Black Tree它在保持較好平衡性的同時(shí)旋轉(zhuǎn)操作更少實(shí)現(xiàn)相對(duì)簡單。但AVL樹作為平衡二叉搜索樹的經(jīng)典實(shí)現(xiàn)理解其原理對(duì)于學(xué)習(xí)更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)非常有幫助。