到C++自平衡二叉搜索樹(shù)：原理、實(shí)現(xiàn)與面試高頻考點(diǎn))
1. 項(xiàng)目概述為什么我們需要AVL樹(shù)在C的STL容器里std::map和std::set是我們處理有序關(guān)聯(lián)數(shù)據(jù)時(shí)最常用的工具。它們底層通常由紅黑樹(shù)實(shí)現(xiàn)保證了元素的有序性和對(duì)數(shù)級(jí)別的查找、插入、刪除效率。但在我剛開(kāi)始學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)時(shí)紅黑樹(shù)的復(fù)雜規(guī)則紅黑節(jié)點(diǎn)、旋轉(zhuǎn)、叔叔節(jié)點(diǎn)一度讓我非常頭疼。實(shí)際上在紅黑樹(shù)被廣泛采用之前還有一種更“直觀”的自平衡二叉搜索樹(shù)BST——AVL樹(shù)它是我認(rèn)為理解平衡樹(shù)思想的最佳入門(mén)選擇。AVL樹(shù)得名于其發(fā)明者G. M. Adelson-Velsky和E. M. Landis。它的核心思想非常樸素對(duì)于樹(shù)中的任何一個(gè)節(jié)點(diǎn)其左子樹(shù)和右子樹(shù)的高度差平衡因子不能超過(guò)1。一旦在插入或刪除操作后破壞了這一平衡條件就通過(guò)一系列“旋轉(zhuǎn)”操作來(lái)恢復(fù)平衡。這種“嚴(yán)格平衡”的策略使得AVL樹(shù)在查找密集型操作上擁有近乎最優(yōu)的性能最壞情況下的時(shí)間復(fù)雜度也是O(log n)代價(jià)是插入和刪除時(shí)可能需要更多次的旋轉(zhuǎn)來(lái)維持平衡。那么為什么我們今天還要深入理解AVL樹(shù)呢首先它的平衡條件簡(jiǎn)單明了旋轉(zhuǎn)操作類(lèi)型固定四種是學(xué)習(xí)樹(shù)形結(jié)構(gòu)再平衡算法的絕佳模型。理解了AVL樹(shù)再去看紅黑樹(shù)、B樹(shù)、伸展樹(shù)等你會(huì)更容易抓住“通過(guò)局部調(diào)整維持全局性質(zhì)”這一核心思想。其次在一些對(duì)查找性能要求極端苛刻、而插入刪除相對(duì)較少的場(chǎng)景例如某些只構(gòu)建一次然后進(jìn)行海量查詢(xún)的字典或配置表手動(dòng)實(shí)現(xiàn)或使用AVL樹(shù)可能比紅黑樹(shù)有微弱的性能優(yōu)勢(shì)。對(duì)于正在準(zhǔn)備面試的C開(kāi)發(fā)者來(lái)說(shuō)AVL樹(shù)更是高頻考點(diǎn)手撕AVL樹(shù)的插入過(guò)程是檢驗(yàn)對(duì)指針、遞歸和數(shù)據(jù)結(jié)構(gòu)理解深度的試金石。2. AVL樹(shù)的核心原理與平衡因子要玩轉(zhuǎn)AVL樹(shù)必須吃透兩個(gè)核心概念平衡因子和旋轉(zhuǎn)。2.1 平衡因子樹(shù)的健康指標(biāo)平衡因子Balance Factor, BF是AVL樹(shù)用于量化“平衡度”的指標(biāo)。對(duì)于一個(gè)節(jié)點(diǎn)我們定義平衡因子(BF) 左子樹(shù)高度 - 右子樹(shù)高度這里的高度通常是指從該節(jié)點(diǎn)到其最遠(yuǎn)葉子節(jié)點(diǎn)的路徑上的邊數(shù)或節(jié)點(diǎn)數(shù)定義需統(tǒng)一。根據(jù)AVL樹(shù)的定義任何節(jié)點(diǎn)的平衡因子只能取 -1 0 1 這三個(gè)值。注意關(guān)于高度的定義必須前后一致。我習(xí)慣使用“節(jié)點(diǎn)數(shù)”定義即空節(jié)點(diǎn)nullptr高度為0葉子節(jié)點(diǎn)高度為1。這樣節(jié)點(diǎn)的高度計(jì)算為height max(left-height, right-height) 1。相應(yīng)的平衡因子計(jì)算為bf left-height - right-height。如果你采用“邊數(shù)”定義空節(jié)點(diǎn)高度為-1那么計(jì)算方式需要調(diào)整務(wù)必在代碼注釋中明確你的選擇。當(dāng)插入或刪除一個(gè)節(jié)點(diǎn)后我們需要從該節(jié)點(diǎn)的父節(jié)點(diǎn)開(kāi)始一路向上回溯到根節(jié)點(diǎn)更新沿途每個(gè)節(jié)點(diǎn)的高度并檢查其平衡因子是否被破壞即絕對(duì)值是否大于1。這個(gè)回溯檢查的過(guò)程是AVL樹(shù)操作區(qū)別于普通BST的關(guān)鍵。2.2 失衡的四種情況與旋轉(zhuǎn)策略插入節(jié)點(diǎn)后導(dǎo)致某個(gè)節(jié)點(diǎn)X的平衡因子變?yōu)?或-2我們就說(shuō)以X為根的子樹(shù)失衡了。失衡可以歸納為四種基本情況對(duì)應(yīng)四種旋轉(zhuǎn)操作LL型失衡左左在X的左孩子L的左子樹(shù)LL上插入新節(jié)點(diǎn)導(dǎo)致X的BF2且L的BF0通常為1或0。解決方法是右單旋。RR型失衡右右在X的右孩子R的右子樹(shù)RR上插入新節(jié)點(diǎn)導(dǎo)致X的BF-2且R的BF0通常為-1或0。解決方法是左單旋。LR型失衡左右在X的左孩子L的右子樹(shù)LR上插入新節(jié)點(diǎn)導(dǎo)致X的BF2且L的BF-1。解決方法是先左旋后右旋左右雙旋。RL型失衡右左在X的右孩子R的左子樹(shù)RL上插入新節(jié)點(diǎn)導(dǎo)致X的BF-2且R的BF1。解決方法是先右旋后左旋右左雙旋。記憶口訣失衡看X插入看子。LL右旋RR左旋LR則左右RL則右左。這里的“左右”指先對(duì)左孩子做左旋再對(duì)X本身做右旋。3. 節(jié)點(diǎn)結(jié)構(gòu)設(shè)計(jì)與基礎(chǔ)接口在動(dòng)手實(shí)現(xiàn)旋轉(zhuǎn)之前我們先要設(shè)計(jì)好樹(shù)的節(jié)點(diǎn)。一個(gè)健壯的AVL樹(shù)節(jié)點(diǎn)需要包含數(shù)據(jù)、左右孩子指針、以及高度信息。templatetypename K, typename V // K為鍵類(lèi)型V為值類(lèi)型實(shí)現(xiàn)一個(gè)簡(jiǎn)單的KV映射 struct AVLTreeNode { std::pairconst K, V kv; // 存儲(chǔ)鍵值對(duì)const K保證鍵不可修改 AVLTreeNodeK, V* left; AVLTreeNodeK, V* right; int height; // 節(jié)點(diǎn)高度 AVLTreeNode(const K key, const V value) : kv(key, value), left(nullptr), right(nullptr), height(1) {} // 新節(jié)點(diǎn)高度初始為1 };接下來(lái)我們封裝一個(gè)AVLTree類(lèi)并實(shí)現(xiàn)幾個(gè)最基礎(chǔ)但至關(guān)重要的工具函數(shù)。templatetypename K, typename V class AVLTree { public: using Node AVLTreeNodeK, V; AVLTree() : root_(nullptr) {} // ... 后續(xù)插入、刪除、查找接口 private: Node* root_; // 工具函數(shù)1獲取節(jié)點(diǎn)高度處理空指針 int getHeight(Node* node) { return node ? node-height : 0; } // 工具函數(shù)2更新節(jié)點(diǎn)高度 void updateHeight(Node* node) { if (node) { node-height std::max(getHeight(node-left), getHeight(node-right)) 1; } } // 工具函數(shù)3計(jì)算平衡因子 int getBalanceFactor(Node* node) { if (!node) return 0; return getHeight(node-left) - getHeight(node-right); } // 工具函數(shù)4中序遍歷用于調(diào)試和驗(yàn)證 void inOrder(Node* node) { if (!node) return; inOrder(node-left); std::cout node-kv.first ; inOrder(node-right); } };實(shí)操心得getHeight函數(shù)一定要處理node為nullptr的情況這是遞歸計(jì)算高度的基礎(chǔ)安全保證。將高度更新和平衡因子計(jì)算封裝成函數(shù)能極大提高后續(xù)旋轉(zhuǎn)和插入刪除邏輯代碼的可讀性避免重復(fù)計(jì)算。4. 旋轉(zhuǎn)操作的詳解與實(shí)現(xiàn)旋轉(zhuǎn)是AVL樹(shù)的靈魂它通過(guò)改變局部節(jié)點(diǎn)的父子關(guān)系在保持二叉搜索樹(shù)性質(zhì)中序遍歷有序的前提下降低子樹(shù)的高度。4.1 右單旋LL型失衡場(chǎng)景節(jié)點(diǎn)X失衡BF2且其左孩子L的BF 0。 操作讓L成為新的根X成為L(zhǎng)的右孩子同時(shí)處理好L原本的右子樹(shù)掛到X的左孩子上。// X (BF2) L (BF0/1) // / \ / \ // (BF0) L Xr 右旋 Ll X // / \ / / \ // Ll Lr ... Lr Xr // / \ // ... ... private: Node* rotateRight(Node* x) { Node* l x-left; Node* lr l-right; // 執(zhí)行旋轉(zhuǎn) l-right x; x-left lr; // 更新高度必須先更新子節(jié)點(diǎn)x再更新父節(jié)點(diǎn)l updateHeight(x); updateHeight(l); // 返回新的子樹(shù)根節(jié)點(diǎn) return l; }4.2 左單旋RR型失衡場(chǎng)景節(jié)點(diǎn)X失衡BF-2且其右孩子R的BF 0。 操作與右單旋對(duì)稱(chēng)。讓R成為新的根X成為R的左孩子同時(shí)處理好R原本的左子樹(shù)。// X (BF-2) R (BF-1/0) // / \ / \ // Xl R (BF0) 左旋 X Rr // / \ / \ \ // Rl Rr Xl Rl ... // / \ // ... ... private: Node* rotateLeft(Node* x) { Node* r x-right; Node* rl r-left; // 執(zhí)行旋轉(zhuǎn) r-left x; x-right rl; // 更新高度 updateHeight(x); updateHeight(r); return r; }4.3 左右雙旋LR型失衡場(chǎng)景節(jié)點(diǎn)X失衡BF2且其左孩子L的BF -1。 操作先對(duì)L進(jìn)行左單旋將其轉(zhuǎn)換為L(zhǎng)L型再對(duì)X進(jìn)行右單旋。// X (BF2) X Lr // / \ / \ / \ // (BF-1)L Xr 先對(duì)L左旋 Lr Xr 再對(duì)X右旋 L X // / \ / \ / \ / \ // Ll Lr (BF0/1) L Lrr Ll Lrl Lrr Xr // / \ / \ // Lrl Lrr Ll Lrl private: Node* rotateLeftRight(Node* x) { x-left rotateLeft(x-left); // 第一步左旋左孩子 return rotateRight(x); // 第二步右旋自己 }4.4 右左雙旋RL型失衡場(chǎng)景節(jié)點(diǎn)X失衡BF-2且其右孩子R的BF 1。 操作先對(duì)R進(jìn)行右單旋將其轉(zhuǎn)換為RR型再對(duì)X進(jìn)行左單旋。// X (BF-2) X Rl // / \ / \ / \ // Xl R (BF1) 先對(duì)R右旋 Xl Rl 再對(duì)X左旋 X R // / \ / \ / \ / \ // (BF0/-1)Rl Rr Rll R Xl Rll Rlr Rr // / \ / \ // Rll Rlr Rlr Rr private: Node* rotateRightLeft(Node* x) { x-right rotateRight(x-right); // 第一步右旋右孩子 return rotateLeft(x); // 第二步左旋自己 }注意事項(xiàng)旋轉(zhuǎn)操作中指針的重新指向順序非常重要畫(huà)圖理解是最有效的方法。更新高度的順序也必須是從底向上的即先更新位置發(fā)生變化的原子樹(shù)根如x再更新新的子樹(shù)根如l或r。雙旋操作可以復(fù)用單旋函數(shù)使代碼更清晰。5. 插入操作的完整實(shí)現(xiàn)與回溯平衡有了旋轉(zhuǎn)函數(shù)插入操作就清晰了。它分為兩步1. 標(biāo)準(zhǔn)的BST遞歸插入2. 遞歸回溯更新高度并檢查平衡。public: bool Insert(const K key, const V value) { if (!root_) { root_ new Node(key, value); return true; } root_ _Insert(root_, key, value); return true; // 簡(jiǎn)化處理假設(shè)總是插入成功鍵不重復(fù) } private: Node* _Insert(Node* node, const K key, const V value) { // 1. 執(zhí)行標(biāo)準(zhǔn)的BST插入 if (!node) { return new Node(key, value); // 創(chuàng)建新節(jié)點(diǎn)并返回 } if (key node-kv.first) { node-left _Insert(node-left, key, value); // 遞歸插入左子樹(shù) } else if (key node-kv.first) { node-right _Insert(node-right, key, value); // 遞歸插入右子樹(shù) } else { // 鍵已存在處理策略可根據(jù)需求定如更新值、插入失敗等 // 此處簡(jiǎn)單返回不插入重復(fù)鍵 return node; } // 2. 遞歸回溯更新當(dāng)前節(jié)點(diǎn)高度 updateHeight(node); // 3. 檢查當(dāng)前節(jié)點(diǎn)是否失衡并進(jìn)行相應(yīng)的旋轉(zhuǎn) int bf getBalanceFactor(node); // LL 情況 if (bf 1 key node-left-kv.first) { return rotateRight(node); } // RR 情況 if (bf -1 key node-right-kv.first) { return rotateLeft(node); } // LR 情況 if (bf 1 key node-left-kv.first) { return rotateLeftRight(node); } // RL 情況 if (bf -1 key node-right-kv.first) { return rotateRightLeft(node); } // 當(dāng)前節(jié)點(diǎn)平衡直接返回 return node; }關(guān)鍵點(diǎn)解析_Insert函數(shù)返回的是以node為根的子樹(shù)在插入并平衡后的新根節(jié)點(diǎn)。因此遞歸調(diào)用后必須用node-left _Insert(...)這樣的形式接收返回值。失衡判斷條件中的key node-left-kv.first和key node-right-kv.first是用來(lái)判斷新節(jié)點(diǎn)插入在孫子節(jié)點(diǎn)的哪一側(cè)從而區(qū)分LL/LR和RR/RL。這是判斷失衡類(lèi)型的核心邏輯。整個(gè)插入過(guò)程的時(shí)間復(fù)雜度是O(log n)因?yàn)檫f歸的深度是樹(shù)高而旋轉(zhuǎn)操作是O(1)的。6. 刪除操作的難點(diǎn)與平衡策略刪除操作比插入更復(fù)雜因?yàn)閯h除節(jié)點(diǎn)可能發(fā)生在樹(shù)的任意位置葉子節(jié)點(diǎn)、單孩子節(jié)點(diǎn)、雙孩子節(jié)點(diǎn)并且刪除后回溯平衡的路徑上可能需要進(jìn)行不止一次的旋轉(zhuǎn)。6.1 刪除的三種情況假設(shè)我們要?jiǎng)h除節(jié)點(diǎn)node葉子節(jié)點(diǎn)直接刪除將其父節(jié)點(diǎn)對(duì)應(yīng)的指針置為nullptr。只有一個(gè)孩子用其唯一的孩子節(jié)點(diǎn)替代它。有兩個(gè)孩子這是最復(fù)雜的情況。需要找到node的中序遍歷直接后繼即右子樹(shù)中的最小節(jié)點(diǎn)或直接前驅(qū)左子樹(shù)中的最大節(jié)點(diǎn)。我們用這個(gè)后繼或前驅(qū)節(jié)點(diǎn)的值覆蓋node的值然后問(wèn)題轉(zhuǎn)化為在右子樹(shù)中刪除那個(gè)后繼節(jié)點(diǎn)它必定是情況1或2。6.2 刪除與平衡的實(shí)現(xiàn)public: bool Erase(const K key) { root_ _Erase(root_, key); return true; // 簡(jiǎn)化處理假設(shè)總能找到并刪除 } private: Node* _Erase(Node* node, const K key) { if (!node) return nullptr; // 未找到要?jiǎng)h除的節(jié)點(diǎn) // 1. 遞歸查找并刪除目標(biāo)節(jié)點(diǎn) if (key node-kv.first) { node-left _Erase(node-left, key); } else if (key node-kv.first) { node-right _Erase(node-right, key); } else { // 找到要?jiǎng)h除的節(jié)點(diǎn)node // 情況1 2: 節(jié)點(diǎn)是葉子或只有一個(gè)孩子 if (!node-left || !node-right) { Node* temp node-left ? node-left : node-right; if (!temp) { // 無(wú)孩子葉子節(jié)點(diǎn) temp node; node nullptr; } else { // 有一個(gè)孩子 // 用孩子節(jié)點(diǎn)內(nèi)容直接替換當(dāng)前節(jié)點(diǎn)偷懶且安全的方式 *node *temp; // 結(jié)構(gòu)體淺拷貝拷貝了kv, height, left, right // 注意這里拷貝了指針需要小心內(nèi)存管理。更穩(wěn)妥的做法是只交換數(shù)據(jù)然后刪除孩子節(jié)點(diǎn)。 } delete temp; // 釋放內(nèi)存 } else { // 情況3: 有兩個(gè)孩子 // 找到右子樹(shù)的最小節(jié)點(diǎn)中序后繼 Node* successor node-right; while (successor-left) { successor successor-left; } // 用后繼節(jié)點(diǎn)的值替換當(dāng)前節(jié)點(diǎn)的值 node-kv.first successor-kv.first; // 注意這里違反了const K實(shí)際中應(yīng)重新設(shè)計(jì)或使用mutable node-kv.second successor-kv.second; // 遞歸刪除右子樹(shù)中的那個(gè)后繼節(jié)點(diǎn) node-right _Erase(node-right, successor-kv.first); } } // 如果樹(shù)為空刪除了最后一個(gè)節(jié)點(diǎn)直接返回 if (!node) return nullptr; // 2. 遞歸回溯更新高度并重新平衡 updateHeight(node); int bf getBalanceFactor(node); // LL 情況 if (bf 1 getBalanceFactor(node-left) 0) { return rotateRight(node); } // LR 情況 if (bf 1 getBalanceFactor(node-left) 0) { return rotateLeftRight(node); } // RR 情況 if (bf -1 getBalanceFactor(node-right) 0) { return rotateLeft(node); } // RL 情況 if (bf -1 getBalanceFactor(node-right) 0) { return rotateRightLeft(node); } return node; }踩坑實(shí)錄刪除有兩個(gè)孩子的節(jié)點(diǎn)時(shí)我最初直接交換了節(jié)點(diǎn)指針導(dǎo)致父節(jié)點(diǎn)指針指向混亂樹(shù)結(jié)構(gòu)斷裂。正確做法是只交換節(jié)點(diǎn)內(nèi)存儲(chǔ)的數(shù)據(jù)鍵值對(duì)然后去刪除那個(gè)后繼節(jié)點(diǎn)。另外判斷失衡類(lèi)型的條件在刪除時(shí)與插入略有不同。插入時(shí)我們可以用key與孩子節(jié)點(diǎn)鍵比較來(lái)判斷插入方向。刪除時(shí)我們不知道刪除發(fā)生在哪一側(cè)所以需要通過(guò)當(dāng)前節(jié)點(diǎn)和孩子節(jié)點(diǎn)的平衡因子來(lái)判斷是哪種失衡類(lèi)型例如bf 1 getBalanceFactor(node-left) 0對(duì)應(yīng)LL型。7. 查找、遍歷與內(nèi)存管理查找操作與普通BST完全一致利用二叉搜索樹(shù)的性質(zhì)進(jìn)行遞歸或迭代即可。public: Node* Find(const K key) { Node* cur root_; while (cur) { if (key cur-kv.first) { cur cur-left; } else if (key cur-kv.first) { cur cur-right; } else { return cur; } } return nullptr; } // 中序遍歷按鍵升序輸出 void InOrder() { _InOrder(root_); std::cout std::endl; } private: void _InOrder(Node* node) { if (!node) return; _InOrder(node-left); std::cout [ node-kv.first : node-kv.second ] ; _InOrder(node-right); }內(nèi)存管理是手動(dòng)實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)時(shí)必須考慮的問(wèn)題。我們需要一個(gè)析構(gòu)函數(shù)來(lái)遞歸釋放所有節(jié)點(diǎn)內(nèi)存防止內(nèi)存泄漏。public: ~AVLTree() { _Destroy(root_); } private: void _Destroy(Node* node) { if (!node) return; _Destroy(node-left); _Destroy(node-right); delete node; }8. 測(cè)試、驗(yàn)證與常見(jiàn)問(wèn)題排查實(shí)現(xiàn)完成后必須進(jìn)行充分測(cè)試。我通常會(huì)編寫(xiě)一個(gè)簡(jiǎn)單的測(cè)試函數(shù)隨機(jī)插入和刪除大量數(shù)據(jù)并檢查樹(shù)是否始終保持有序和平衡。8.1 驗(yàn)證函數(shù)編寫(xiě)一個(gè)函數(shù)來(lái)驗(yàn)證樹(shù)是否滿足AVL樹(shù)和BST的所有條件。public: bool IsAVLTree() { return _IsAVLTree(root_); } private: bool _IsAVLTree(Node* node) { if (!node) return true; // 檢查當(dāng)前節(jié)點(diǎn)平衡因子 int bf getBalanceFactor(node); if (bf 1 || bf -1) { std::cout 平衡因子錯(cuò)誤在節(jié)點(diǎn): node-kv.first , bf bf std::endl; return false; } // 遞歸檢查左右子樹(shù) if (!_IsAVLTree(node-left) || !_IsAVLTree(node-right)) { return false; } // 檢查BST性質(zhì)左子樹(shù)所有節(jié)點(diǎn)鍵小于當(dāng)前節(jié)點(diǎn)右子樹(shù)所有節(jié)點(diǎn)鍵大于當(dāng)前節(jié)點(diǎn) // 一個(gè)簡(jiǎn)便方法是中序遍歷結(jié)果應(yīng)該嚴(yán)格遞增 return true; } // 輔助函數(shù)獲取中序遍歷序列 void _GetInOrderSeq(Node* node, std::vectorK seq) { if (!node) return; _GetInOrderSeq(node-left, seq); seq.push_back(node-kv.first); _GetInOrderSeq(node-right, seq); } bool IsBST() { std::vectorK seq; _GetInOrderSeq(root_, seq); for (size_t i 1; i seq.size(); i) { if (seq[i] seq[i-1]) { // 允許等于嗎對(duì)于map不允許 std::cout BST順序錯(cuò)誤在索引: i std::endl; return false; } } return true; }8.2 常見(jiàn)問(wèn)題排查表在調(diào)試AVL樹(shù)時(shí)我遇到過(guò)不少“坑”這里總結(jié)一下問(wèn)題現(xiàn)象可能原因排查方法插入后樹(shù)失去BST性質(zhì)中序遍歷無(wú)序旋轉(zhuǎn)操作中指針指向錯(cuò)誤破壞了左根右的關(guān)系。1. 對(duì)小規(guī)模數(shù)據(jù)如3個(gè)節(jié)點(diǎn)進(jìn)行插入畫(huà)出每一步的樹(shù)形圖。2. 單步調(diào)試觀察旋轉(zhuǎn)函數(shù)執(zhí)行前后相關(guān)節(jié)點(diǎn)的left和right指針變化。平衡因子計(jì)算永遠(yuǎn)正確但樹(shù)明顯傾斜updateHeight函數(shù)邏輯錯(cuò)誤或忘記調(diào)用。1. 在updateHeight和getBalanceFactor函數(shù)中加入調(diào)試輸出。2. 確認(rèn)高度計(jì)算方式一致空節(jié)點(diǎn)高度是0還是-1。刪除節(jié)點(diǎn)后程序崩潰訪問(wèn)非法內(nèi)存內(nèi)存管理錯(cuò)誤。刪除有兩個(gè)孩子的節(jié)點(diǎn)時(shí)直接delete了后繼節(jié)點(diǎn)但該節(jié)點(diǎn)的內(nèi)容已被復(fù)制到原節(jié)點(diǎn)導(dǎo)致重復(fù)刪除或指針懸掛。1. 使用valgrind等內(nèi)存檢測(cè)工具。2. 仔細(xì)檢查_(kāi)Erase函數(shù)中情況3的代碼邏輯確保只刪除了一次節(jié)點(diǎn)。雙旋后樹(shù)仍然不平衡雙旋操作順序錯(cuò)誤或旋轉(zhuǎn)后沒(méi)有正確更新受影響節(jié)點(diǎn)的高度。1. 記住雙旋是兩次單旋的組合先對(duì)孩子旋再對(duì)自己旋。2. 在rotateLeftRight和rotateRightLeft函數(shù)中確保兩次旋轉(zhuǎn)后都正確更新了高度單旋函數(shù)內(nèi)部已更新但中間節(jié)點(diǎn)的父節(jié)點(diǎn)高度可能需要再次更新實(shí)際上我們的實(shí)現(xiàn)是返回新根由上層遞歸更新。遞歸插入/刪除導(dǎo)致棧溢出樹(shù)極度不平衡但AVL樹(shù)本應(yīng)避免或遞歸函數(shù)邏輯錯(cuò)誤導(dǎo)致無(wú)限遞歸。1. 檢查遞歸終止條件是否完備。2. 對(duì)于極端大數(shù)據(jù)量考慮將遞歸改為迭代棧的寫(xiě)法面試中遞歸寫(xiě)法通常可接受。8.3 一個(gè)簡(jiǎn)單的測(cè)試用例int main() { AVLTreeint, std::string tree; std::vectorint keys {10, 20, 30, 40, 50, 25}; // 依次插入會(huì)導(dǎo)致RRLLRL等不同旋轉(zhuǎn) std::cout 插入順序: ; for (int key : keys) { std::cout key ; tree.Insert(key, value_ std::to_string(key)); // 每次插入后可以驗(yàn)證 if (!tree.IsAVLTree() || !tree.IsBST()) { std::cout \n插入 key 后樹(shù)的性質(zhì)被破壞 std::endl; return -1; } } std::cout \n插入完成。中序遍歷: ; tree.InOrder(); // 測(cè)試查找 auto node tree.Find(30); if (node) { std::cout 找到鍵30對(duì)應(yīng)值: node-kv.second std::endl; } // 測(cè)試刪除 std::cout \n刪除鍵20: ; tree.Erase(20); tree.InOrder(); if (!tree.IsAVLTree() || !tree.IsBST()) { std::cout 刪除后樹(shù)的性質(zhì)被破壞 std::endl; return -1; } std::cout \n所有測(cè)試通過(guò) std::endl; return 0; }通過(guò)這樣從簡(jiǎn)到繁的測(cè)試可以逐步建立對(duì)AVL樹(shù)實(shí)現(xiàn)正確性的信心。理解并實(shí)現(xiàn)AVL樹(shù)的過(guò)程是對(duì)指針操作、遞歸思維和數(shù)據(jù)結(jié)構(gòu)平衡理念的一次深度錘煉。雖然在實(shí)際項(xiàng)目中我們大多直接使用std::map但親手實(shí)現(xiàn)一遍AVL樹(shù)會(huì)讓你對(duì)“平衡”二字有刻骨銘心的認(rèn)識(shí)在遇到性能調(diào)優(yōu)或底層面試時(shí)這份理解會(huì)是你堅(jiān)實(shí)的底氣。 從AVL樹(shù)到C++自平衡二叉搜索樹(shù)：原理、實(shí)現(xiàn)與面試高頻考點(diǎn)
1. 項(xiàng)目概述為什么我們需要AVL樹(shù)在C的STL容器里std::map和std::set是我們處理有序關(guān)聯(lián)數(shù)據(jù)時(shí)最常用的工具。它們底層通常由紅黑樹(shù)實(shí)現(xiàn)保證了元素的有序性和對(duì)數(shù)級(jí)別的查找、插入、刪除效率。但在我剛開(kāi)始學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)時(shí)紅黑樹(shù)的復(fù)雜規(guī)則紅黑節(jié)點(diǎn)、旋轉(zhuǎn)、叔叔節(jié)點(diǎn)一度讓我非常頭疼。實(shí)際上在紅黑樹(shù)被廣泛采用之前還有一種更“直觀”的自平衡二叉搜索樹(shù)BST——AVL樹(shù)它是我認(rèn)為理解平衡樹(shù)思想的最佳入門(mén)選擇。AVL樹(shù)得名于其發(fā)明者G. M. Adelson-Velsky和E. M. Landis。它的核心思想非常樸素對(duì)于樹(shù)中的任何一個(gè)節(jié)點(diǎn)其左子樹(shù)和右子樹(shù)的高度差平衡因子不能超過(guò)1。一旦在插入或刪除操作后破壞了這一平衡條件就通過(guò)一系列“旋轉(zhuǎn)”操作來(lái)恢復(fù)平衡。這種“嚴(yán)格平衡”的策略使得AVL樹(shù)在查找密集型操作上擁有近乎最優(yōu)的性能最壞情況下的時(shí)間復(fù)雜度也是O(log n)代價(jià)是插入和刪除時(shí)可能需要更多次的旋轉(zhuǎn)來(lái)維持平衡。那么為什么我們今天還要深入理解AVL樹(shù)呢首先它的平衡條件簡(jiǎn)單明了旋轉(zhuǎn)操作類(lèi)型固定四種是學(xué)習(xí)樹(shù)形結(jié)構(gòu)再平衡算法的絕佳模型。理解了AVL樹(shù)再去看紅黑樹(shù)、B樹(shù)、伸展樹(shù)等你會(huì)更容易抓住“通過(guò)局部調(diào)整維持全局性質(zhì)”這一核心思想。其次在一些對(duì)查找性能要求極端苛刻、而插入刪除相對(duì)較少的場(chǎng)景例如某些只構(gòu)建一次然后進(jìn)行海量查詢(xún)的字典或配置表手動(dòng)實(shí)現(xiàn)或使用AVL樹(shù)可能比紅黑樹(shù)有微弱的性能優(yōu)勢(shì)。對(duì)于正在準(zhǔn)備面試的C開(kāi)發(fā)者來(lái)說(shuō)AVL樹(shù)更是高頻考點(diǎn)手撕AVL樹(shù)的插入過(guò)程是檢驗(yàn)對(duì)指針、遞歸和數(shù)據(jù)結(jié)構(gòu)理解深度的試金石。2. AVL樹(shù)的核心原理與平衡因子要玩轉(zhuǎn)AVL樹(shù)必須吃透兩個(gè)核心概念平衡因子和旋轉(zhuǎn)。2.1 平衡因子樹(shù)的健康指標(biāo)平衡因子Balance Factor, BF是AVL樹(shù)用于量化“平衡度”的指標(biāo)。對(duì)于一個(gè)節(jié)點(diǎn)我們定義平衡因子(BF) 左子樹(shù)高度 - 右子樹(shù)高度這里的高度通常是指從該節(jié)點(diǎn)到其最遠(yuǎn)葉子節(jié)點(diǎn)的路徑上的邊數(shù)或節(jié)點(diǎn)數(shù)定義需統(tǒng)一。根據(jù)AVL樹(shù)的定義任何節(jié)點(diǎn)的平衡因子只能取 -1 0 1 這三個(gè)值。注意關(guān)于高度的定義必須前后一致。我習(xí)慣使用“節(jié)點(diǎn)數(shù)”定義即空節(jié)點(diǎn)nullptr高度為0葉子節(jié)點(diǎn)高度為1。這樣節(jié)點(diǎn)的高度計(jì)算為height max(left-height, right-height) 1。相應(yīng)的平衡因子計(jì)算為bf left-height - right-height。如果你采用“邊數(shù)”定義空節(jié)點(diǎn)高度為-1那么計(jì)算方式需要調(diào)整務(wù)必在代碼注釋中明確你的選擇。當(dāng)插入或刪除一個(gè)節(jié)點(diǎn)后我們需要從該節(jié)點(diǎn)的父節(jié)點(diǎn)開(kāi)始一路向上回溯到根節(jié)點(diǎn)更新沿途每個(gè)節(jié)點(diǎn)的高度并檢查其平衡因子是否被破壞即絕對(duì)值是否大于1。這個(gè)回溯檢查的過(guò)程是AVL樹(shù)操作區(qū)別于普通BST的關(guān)鍵。2.2 失衡的四種情況與旋轉(zhuǎn)策略插入節(jié)點(diǎn)后導(dǎo)致某個(gè)節(jié)點(diǎn)X的平衡因子變?yōu)?或-2我們就說(shuō)以X為根的子樹(shù)失衡了。失衡可以歸納為四種基本情況對(duì)應(yīng)四種旋轉(zhuǎn)操作LL型失衡左左在X的左孩子L的左子樹(shù)LL上插入新節(jié)點(diǎn)導(dǎo)致X的BF2且L的BF0通常為1或0。解決方法是右單旋。RR型失衡右右在X的右孩子R的右子樹(shù)RR上插入新節(jié)點(diǎn)導(dǎo)致X的BF-2且R的BF0通常為-1或0。解決方法是左單旋。LR型失衡左右在X的左孩子L的右子樹(shù)LR上插入新節(jié)點(diǎn)導(dǎo)致X的BF2且L的BF-1。解決方法是先左旋后右旋左右雙旋。RL型失衡右左在X的右孩子R的左子樹(shù)RL上插入新節(jié)點(diǎn)導(dǎo)致X的BF-2且R的BF1。解決方法是先右旋后左旋右左雙旋。記憶口訣失衡看X插入看子。LL右旋RR左旋LR則左右RL則右左。這里的“左右”指先對(duì)左孩子做左旋再對(duì)X本身做右旋。3. 節(jié)點(diǎn)結(jié)構(gòu)設(shè)計(jì)與基礎(chǔ)接口在動(dòng)手實(shí)現(xiàn)旋轉(zhuǎn)之前我們先要設(shè)計(jì)好樹(shù)的節(jié)點(diǎn)。一個(gè)健壯的AVL樹(shù)節(jié)點(diǎn)需要包含數(shù)據(jù)、左右孩子指針、以及高度信息。templatetypename K, typename V // K為鍵類(lèi)型V為值類(lèi)型實(shí)現(xiàn)一個(gè)簡(jiǎn)單的KV映射 struct AVLTreeNode { std::pairconst K, V kv; // 存儲(chǔ)鍵值對(duì)const K保證鍵不可修改 AVLTreeNodeK, V* left; AVLTreeNodeK, V* right; int height; // 節(jié)點(diǎn)高度 AVLTreeNode(const K key, const V value) : kv(key, value), left(nullptr), right(nullptr), height(1) {} // 新節(jié)點(diǎn)高度初始為1 };接下來(lái)我們封裝一個(gè)AVLTree類(lèi)并實(shí)現(xiàn)幾個(gè)最基礎(chǔ)但至關(guān)重要的工具函數(shù)。templatetypename K, typename V class AVLTree { public: using Node AVLTreeNodeK, V; AVLTree() : root_(nullptr) {} // ... 后續(xù)插入、刪除、查找接口 private: Node* root_; // 工具函數(shù)1獲取節(jié)點(diǎn)高度處理空指針 int getHeight(Node* node) { return node ? node-height : 0; } // 工具函數(shù)2更新節(jié)點(diǎn)高度 void updateHeight(Node* node) { if (node) { node-height std::max(getHeight(node-left), getHeight(node-right)) 1; } } // 工具函數(shù)3計(jì)算平衡因子 int getBalanceFactor(Node* node) { if (!node) return 0; return getHeight(node-left) - getHeight(node-right); } // 工具函數(shù)4中序遍歷用于調(diào)試和驗(yàn)證 void inOrder(Node* node) { if (!node) return; inOrder(node-left); std::cout node-kv.first ; inOrder(node-right); } };實(shí)操心得getHeight函數(shù)一定要處理node為nullptr的情況這是遞歸計(jì)算高度的基礎(chǔ)安全保證。將高度更新和平衡因子計(jì)算封裝成函數(shù)能極大提高后續(xù)旋轉(zhuǎn)和插入刪除邏輯代碼的可讀性避免重復(fù)計(jì)算。4. 旋轉(zhuǎn)操作的詳解與實(shí)現(xiàn)旋轉(zhuǎn)是AVL樹(shù)的靈魂它通過(guò)改變局部節(jié)點(diǎn)的父子關(guān)系在保持二叉搜索樹(shù)性質(zhì)中序遍歷有序的前提下降低子樹(shù)的高度。4.1 右單旋LL型失衡場(chǎng)景節(jié)點(diǎn)X失衡BF2且其左孩子L的BF 0。 操作讓L成為新的根X成為L(zhǎng)的右孩子同時(shí)處理好L原本的右子樹(shù)掛到X的左孩子上。// X (BF2) L (BF0/1) // / \ / \ // (BF0) L Xr 右旋 Ll X // / \ / / \ // Ll Lr ... Lr Xr // / \ // ... ... private: Node* rotateRight(Node* x) { Node* l x-left; Node* lr l-right; // 執(zhí)行旋轉(zhuǎn) l-right x; x-left lr; // 更新高度必須先更新子節(jié)點(diǎn)x再更新父節(jié)點(diǎn)l updateHeight(x); updateHeight(l); // 返回新的子樹(shù)根節(jié)點(diǎn) return l; }4.2 左單旋RR型失衡場(chǎng)景節(jié)點(diǎn)X失衡BF-2且其右孩子R的BF 0。 操作與右單旋對(duì)稱(chēng)。讓R成為新的根X成為R的左孩子同時(shí)處理好R原本的左子樹(shù)。// X (BF-2) R (BF-1/0) // / \ / \ // Xl R (BF0) 左旋 X Rr // / \ / \ \ // Rl Rr Xl Rl ... // / \ // ... ... private: Node* rotateLeft(Node* x) { Node* r x-right; Node* rl r-left; // 執(zhí)行旋轉(zhuǎn) r-left x; x-right rl; // 更新高度 updateHeight(x); updateHeight(r); return r; }4.3 左右雙旋LR型失衡場(chǎng)景節(jié)點(diǎn)X失衡BF2且其左孩子L的BF -1。 操作先對(duì)L進(jìn)行左單旋將其轉(zhuǎn)換為L(zhǎng)L型再對(duì)X進(jìn)行右單旋。// X (BF2) X Lr // / \ / \ / \ // (BF-1)L Xr 先對(duì)L左旋 Lr Xr 再對(duì)X右旋 L X // / \ / \ / \ / \ // Ll Lr (BF0/1) L Lrr Ll Lrl Lrr Xr // / \ / \ // Lrl Lrr Ll Lrl private: Node* rotateLeftRight(Node* x) { x-left rotateLeft(x-left); // 第一步左旋左孩子 return rotateRight(x); // 第二步右旋自己 }4.4 右左雙旋RL型失衡場(chǎng)景節(jié)點(diǎn)X失衡BF-2且其右孩子R的BF 1。 操作先對(duì)R進(jìn)行右單旋將其轉(zhuǎn)換為RR型再對(duì)X進(jìn)行左單旋。// X (BF-2) X Rl // / \ / \ / \ // Xl R (BF1) 先對(duì)R右旋 Xl Rl 再對(duì)X左旋 X R // / \ / \ / \ / \ // (BF0/-1)Rl Rr Rll R Xl Rll Rlr Rr // / \ / \ // Rll Rlr Rlr Rr private: Node* rotateRightLeft(Node* x) { x-right rotateRight(x-right); // 第一步右旋右孩子 return rotateLeft(x); // 第二步左旋自己 }注意事項(xiàng)旋轉(zhuǎn)操作中指針的重新指向順序非常重要畫(huà)圖理解是最有效的方法。更新高度的順序也必須是從底向上的即先更新位置發(fā)生變化的原子樹(shù)根如x再更新新的子樹(shù)根如l或r。雙旋操作可以復(fù)用單旋函數(shù)使代碼更清晰。5. 插入操作的完整實(shí)現(xiàn)與回溯平衡有了旋轉(zhuǎn)函數(shù)插入操作就清晰了。它分為兩步1. 標(biāo)準(zhǔn)的BST遞歸插入2. 遞歸回溯更新高度并檢查平衡。public: bool Insert(const K key, const V value) { if (!root_) { root_ new Node(key, value); return true; } root_ _Insert(root_, key, value); return true; // 簡(jiǎn)化處理假設(shè)總是插入成功鍵不重復(fù) } private: Node* _Insert(Node* node, const K key, const V value) { // 1. 執(zhí)行標(biāo)準(zhǔn)的BST插入 if (!node) { return new Node(key, value); // 創(chuàng)建新節(jié)點(diǎn)并返回 } if (key node-kv.first) { node-left _Insert(node-left, key, value); // 遞歸插入左子樹(shù) } else if (key node-kv.first) { node-right _Insert(node-right, key, value); // 遞歸插入右子樹(shù) } else { // 鍵已存在處理策略可根據(jù)需求定如更新值、插入失敗等 // 此處簡(jiǎn)單返回不插入重復(fù)鍵 return node; } // 2. 遞歸回溯更新當(dāng)前節(jié)點(diǎn)高度 updateHeight(node); // 3. 檢查當(dāng)前節(jié)點(diǎn)是否失衡并進(jìn)行相應(yīng)的旋轉(zhuǎn) int bf getBalanceFactor(node); // LL 情況 if (bf 1 key node-left-kv.first) { return rotateRight(node); } // RR 情況 if (bf -1 key node-right-kv.first) { return rotateLeft(node); } // LR 情況 if (bf 1 key node-left-kv.first) { return rotateLeftRight(node); } // RL 情況 if (bf -1 key node-right-kv.first) { return rotateRightLeft(node); } // 當(dāng)前節(jié)點(diǎn)平衡直接返回 return node; }關(guān)鍵點(diǎn)解析_Insert函數(shù)返回的是以node為根的子樹(shù)在插入并平衡后的新根節(jié)點(diǎn)。因此遞歸調(diào)用后必須用node-left _Insert(...)這樣的形式接收返回值。失衡判斷條件中的key node-left-kv.first和key node-right-kv.first是用來(lái)判斷新節(jié)點(diǎn)插入在孫子節(jié)點(diǎn)的哪一側(cè)從而區(qū)分LL/LR和RR/RL。這是判斷失衡類(lèi)型的核心邏輯。整個(gè)插入過(guò)程的時(shí)間復(fù)雜度是O(log n)因?yàn)檫f歸的深度是樹(shù)高而旋轉(zhuǎn)操作是O(1)的。6. 刪除操作的難點(diǎn)與平衡策略刪除操作比插入更復(fù)雜因?yàn)閯h除節(jié)點(diǎn)可能發(fā)生在樹(shù)的任意位置葉子節(jié)點(diǎn)、單孩子節(jié)點(diǎn)、雙孩子節(jié)點(diǎn)并且刪除后回溯平衡的路徑上可能需要進(jìn)行不止一次的旋轉(zhuǎn)。6.1 刪除的三種情況假設(shè)我們要?jiǎng)h除節(jié)點(diǎn)node葉子節(jié)點(diǎn)直接刪除將其父節(jié)點(diǎn)對(duì)應(yīng)的指針置為nullptr。只有一個(gè)孩子用其唯一的孩子節(jié)點(diǎn)替代它。有兩個(gè)孩子這是最復(fù)雜的情況。需要找到node的中序遍歷直接后繼即右子樹(shù)中的最小節(jié)點(diǎn)或直接前驅(qū)左子樹(shù)中的最大節(jié)點(diǎn)。我們用這個(gè)后繼或前驅(qū)節(jié)點(diǎn)的值覆蓋node的值然后問(wèn)題轉(zhuǎn)化為在右子樹(shù)中刪除那個(gè)后繼節(jié)點(diǎn)它必定是情況1或2。6.2 刪除與平衡的實(shí)現(xiàn)public: bool Erase(const K key) { root_ _Erase(root_, key); return true; // 簡(jiǎn)化處理假設(shè)總能找到并刪除 } private: Node* _Erase(Node* node, const K key) { if (!node) return nullptr; // 未找到要?jiǎng)h除的節(jié)點(diǎn) // 1. 遞歸查找并刪除目標(biāo)節(jié)點(diǎn) if (key node-kv.first) { node-left _Erase(node-left, key); } else if (key node-kv.first) { node-right _Erase(node-right, key); } else { // 找到要?jiǎng)h除的節(jié)點(diǎn)node // 情況1 2: 節(jié)點(diǎn)是葉子或只有一個(gè)孩子 if (!node-left || !node-right) { Node* temp node-left ? node-left : node-right; if (!temp) { // 無(wú)孩子葉子節(jié)點(diǎn) temp node; node nullptr; } else { // 有一個(gè)孩子 // 用孩子節(jié)點(diǎn)內(nèi)容直接替換當(dāng)前節(jié)點(diǎn)偷懶且安全的方式 *node *temp; // 結(jié)構(gòu)體淺拷貝拷貝了kv, height, left, right // 注意這里拷貝了指針需要小心內(nèi)存管理。更穩(wěn)妥的做法是只交換數(shù)據(jù)然后刪除孩子節(jié)點(diǎn)。 } delete temp; // 釋放內(nèi)存 } else { // 情況3: 有兩個(gè)孩子 // 找到右子樹(shù)的最小節(jié)點(diǎn)中序后繼 Node* successor node-right; while (successor-left) { successor successor-left; } // 用后繼節(jié)點(diǎn)的值替換當(dāng)前節(jié)點(diǎn)的值 node-kv.first successor-kv.first; // 注意這里違反了const K實(shí)際中應(yīng)重新設(shè)計(jì)或使用mutable node-kv.second successor-kv.second; // 遞歸刪除右子樹(shù)中的那個(gè)后繼節(jié)點(diǎn) node-right _Erase(node-right, successor-kv.first); } } // 如果樹(shù)為空刪除了最后一個(gè)節(jié)點(diǎn)直接返回 if (!node) return nullptr; // 2. 遞歸回溯更新高度并重新平衡 updateHeight(node); int bf getBalanceFactor(node); // LL 情況 if (bf 1 getBalanceFactor(node-left) 0) { return rotateRight(node); } // LR 情況 if (bf 1 getBalanceFactor(node-left) 0) { return rotateLeftRight(node); } // RR 情況 if (bf -1 getBalanceFactor(node-right) 0) { return rotateLeft(node); } // RL 情況 if (bf -1 getBalanceFactor(node-right) 0) { return rotateRightLeft(node); } return node; }踩坑實(shí)錄刪除有兩個(gè)孩子的節(jié)點(diǎn)時(shí)我最初直接交換了節(jié)點(diǎn)指針導(dǎo)致父節(jié)點(diǎn)指針指向混亂樹(shù)結(jié)構(gòu)斷裂。正確做法是只交換節(jié)點(diǎn)內(nèi)存儲(chǔ)的數(shù)據(jù)鍵值對(duì)然后去刪除那個(gè)后繼節(jié)點(diǎn)。另外判斷失衡類(lèi)型的條件在刪除時(shí)與插入略有不同。插入時(shí)我們可以用key與孩子節(jié)點(diǎn)鍵比較來(lái)判斷插入方向。刪除時(shí)我們不知道刪除發(fā)生在哪一側(cè)所以需要通過(guò)當(dāng)前節(jié)點(diǎn)和孩子節(jié)點(diǎn)的平衡因子來(lái)判斷是哪種失衡類(lèi)型例如bf 1 getBalanceFactor(node-left) 0對(duì)應(yīng)LL型。7. 查找、遍歷與內(nèi)存管理查找操作與普通BST完全一致利用二叉搜索樹(shù)的性質(zhì)進(jìn)行遞歸或迭代即可。public: Node* Find(const K key) { Node* cur root_; while (cur) { if (key cur-kv.first) { cur cur-left; } else if (key cur-kv.first) { cur cur-right; } else { return cur; } } return nullptr; } // 中序遍歷按鍵升序輸出 void InOrder() { _InOrder(root_); std::cout std::endl; } private: void _InOrder(Node* node) { if (!node) return; _InOrder(node-left); std::cout [ node-kv.first : node-kv.second ] ; _InOrder(node-right); }內(nèi)存管理是手動(dòng)實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)時(shí)必須考慮的問(wèn)題。我們需要一個(gè)析構(gòu)函數(shù)來(lái)遞歸釋放所有節(jié)點(diǎn)內(nèi)存防止內(nèi)存泄漏。public: ~AVLTree() { _Destroy(root_); } private: void _Destroy(Node* node) { if (!node) return; _Destroy(node-left); _Destroy(node-right); delete node; }8. 測(cè)試、驗(yàn)證與常見(jiàn)問(wèn)題排查實(shí)現(xiàn)完成后必須進(jìn)行充分測(cè)試。我通常會(huì)編寫(xiě)一個(gè)簡(jiǎn)單的測(cè)試函數(shù)隨機(jī)插入和刪除大量數(shù)據(jù)并檢查樹(shù)是否始終保持有序和平衡。8.1 驗(yàn)證函數(shù)編寫(xiě)一個(gè)函數(shù)來(lái)驗(yàn)證樹(shù)是否滿足AVL樹(shù)和BST的所有條件。public: bool IsAVLTree() { return _IsAVLTree(root_); } private: bool _IsAVLTree(Node* node) { if (!node) return true; // 檢查當(dāng)前節(jié)點(diǎn)平衡因子 int bf getBalanceFactor(node); if (bf 1 || bf -1) { std::cout 平衡因子錯(cuò)誤在節(jié)點(diǎn): node-kv.first , bf bf std::endl; return false; } // 遞歸檢查左右子樹(shù) if (!_IsAVLTree(node-left) || !_IsAVLTree(node-right)) { return false; } // 檢查BST性質(zhì)左子樹(shù)所有節(jié)點(diǎn)鍵小于當(dāng)前節(jié)點(diǎn)右子樹(shù)所有節(jié)點(diǎn)鍵大于當(dāng)前節(jié)點(diǎn) // 一個(gè)簡(jiǎn)便方法是中序遍歷結(jié)果應(yīng)該嚴(yán)格遞增 return true; } // 輔助函數(shù)獲取中序遍歷序列 void _GetInOrderSeq(Node* node, std::vectorK seq) { if (!node) return; _GetInOrderSeq(node-left, seq); seq.push_back(node-kv.first); _GetInOrderSeq(node-right, seq); } bool IsBST() { std::vectorK seq; _GetInOrderSeq(root_, seq); for (size_t i 1; i seq.size(); i) { if (seq[i] seq[i-1]) { // 允許等于嗎對(duì)于map不允許 std::cout BST順序錯(cuò)誤在索引: i std::endl; return false; } } return true; }8.2 常見(jiàn)問(wèn)題排查表在調(diào)試AVL樹(shù)時(shí)我遇到過(guò)不少“坑”這里總結(jié)一下問(wèn)題現(xiàn)象可能原因排查方法插入后樹(shù)失去BST性質(zhì)中序遍歷無(wú)序旋轉(zhuǎn)操作中指針指向錯(cuò)誤破壞了左根右的關(guān)系。1. 對(duì)小規(guī)模數(shù)據(jù)如3個(gè)節(jié)點(diǎn)進(jìn)行插入畫(huà)出每一步的樹(shù)形圖。2. 單步調(diào)試觀察旋轉(zhuǎn)函數(shù)執(zhí)行前后相關(guān)節(jié)點(diǎn)的left和right指針變化。平衡因子計(jì)算永遠(yuǎn)正確但樹(shù)明顯傾斜updateHeight函數(shù)邏輯錯(cuò)誤或忘記調(diào)用。1. 在updateHeight和getBalanceFactor函數(shù)中加入調(diào)試輸出。2. 確認(rèn)高度計(jì)算方式一致空節(jié)點(diǎn)高度是0還是-1。刪除節(jié)點(diǎn)后程序崩潰訪問(wèn)非法內(nèi)存內(nèi)存管理錯(cuò)誤。刪除有兩個(gè)孩子的節(jié)點(diǎn)時(shí)直接delete了后繼節(jié)點(diǎn)但該節(jié)點(diǎn)的內(nèi)容已被復(fù)制到原節(jié)點(diǎn)導(dǎo)致重復(fù)刪除或指針懸掛。1. 使用valgrind等內(nèi)存檢測(cè)工具。2. 仔細(xì)檢查_(kāi)Erase函數(shù)中情況3的代碼邏輯確保只刪除了一次節(jié)點(diǎn)。雙旋后樹(shù)仍然不平衡雙旋操作順序錯(cuò)誤或旋轉(zhuǎn)后沒(méi)有正確更新受影響節(jié)點(diǎn)的高度。1. 記住雙旋是兩次單旋的組合先對(duì)孩子旋再對(duì)自己旋。2. 在rotateLeftRight和rotateRightLeft函數(shù)中確保兩次旋轉(zhuǎn)后都正確更新了高度單旋函數(shù)內(nèi)部已更新但中間節(jié)點(diǎn)的父節(jié)點(diǎn)高度可能需要再次更新實(shí)際上我們的實(shí)現(xiàn)是返回新根由上層遞歸更新。遞歸插入/刪除導(dǎo)致棧溢出樹(shù)極度不平衡但AVL樹(shù)本應(yīng)避免或遞歸函數(shù)邏輯錯(cuò)誤導(dǎo)致無(wú)限遞歸。1. 檢查遞歸終止條件是否完備。2. 對(duì)于極端大數(shù)據(jù)量考慮將遞歸改為迭代棧的寫(xiě)法面試中遞歸寫(xiě)法通常可接受。8.3 一個(gè)簡(jiǎn)單的測(cè)試用例int main() { AVLTreeint, std::string tree; std::vectorint keys {10, 20, 30, 40, 50, 25}; // 依次插入會(huì)導(dǎo)致RRLLRL等不同旋轉(zhuǎn) std::cout 插入順序: ; for (int key : keys) { std::cout key ; tree.Insert(key, value_ std::to_string(key)); // 每次插入后可以驗(yàn)證 if (!tree.IsAVLTree() || !tree.IsBST()) { std::cout \n插入 key 后樹(shù)的性質(zhì)被破壞 std::endl; return -1; } } std::cout \n插入完成。中序遍歷: ; tree.InOrder(); // 測(cè)試查找 auto node tree.Find(30); if (node) { std::cout 找到鍵30對(duì)應(yīng)值: node-kv.second std::endl; } // 測(cè)試刪除 std::cout \n刪除鍵20: ; tree.Erase(20); tree.InOrder(); if (!tree.IsAVLTree() || !tree.IsBST()) { std::cout 刪除后樹(shù)的性質(zhì)被破壞 std::endl; return -1; } std::cout \n所有測(cè)試通過(guò) std::endl; return 0; }通過(guò)這樣從簡(jiǎn)到繁的測(cè)試可以逐步建立對(duì)AVL樹(shù)實(shí)現(xiàn)正確性的信心。理解并實(shí)現(xiàn)AVL樹(shù)的過(guò)程是對(duì)指針操作、遞歸思維和數(shù)據(jù)結(jié)構(gòu)平衡理念的一次深度錘煉。雖然在實(shí)際項(xiàng)目中我們大多直接使用std::map但親手實(shí)現(xiàn)一遍AVL樹(shù)會(huì)讓你對(duì)“平衡”二字有刻骨銘心的認(rèn)識(shí)在遇到性能調(diào)優(yōu)或底層面試時(shí)這份理解會(huì)是你堅(jiān)實(shí)的底氣。