C++-AVL樹

一、AVL樹的概念

1.二叉搜索樹

二叉搜索樹（BST，Binary Search Tree），也稱二叉排序樹或二叉查找樹。
二叉搜索樹：一棵二叉樹，可以為空；如果不為空，滿足以下性質：

  1. 非空左子樹的所有鍵值小于其根結點的鍵值。
  2. 非空右子樹的所有鍵值大于其根結點的鍵值。
  3. 左、右子樹都是二叉搜索樹。

二叉搜索樹的性能：

  • 最優情況下，二叉搜索樹為完全二叉樹(或者接近完全二叉樹)，其平均比較次數為：logN
  • 最差情況下，二叉搜索樹退化為單支樹(或者類似單支)，其平均比較次數為：N

在最壞情況下，二叉搜索樹的性能就失去了，為了在最壞情況下也能發揮二叉搜索樹的性能，VAL樹和紅黑樹的出現就解決了這個問題。

2.AVL樹

平衡二叉樹 全稱叫做平衡二叉搜索(排序)樹，簡稱 AVL樹。AVL 是大學教授G.M. Adelson-Velsky 和E.M. Landis名稱的縮寫，他們提出的平衡二叉樹的概念，為了紀念他們，將平衡二叉樹稱為 AVL樹。

方法：當向二叉搜索樹中插入新結點后，如果能保證每個結點的左右子樹高度之差的絕對值不超過1（需要對樹中的結點進行調整），即可降低樹的高度，從而減少平均搜索長度。

AVL樹可以是一棵空樹，也可以是具有以下性質的一棵二叉搜索樹：

  • 樹的左右子樹都是AVL樹。
  • 樹的左右子樹高度之差（簡稱平衡因子）的絕對值不超過1。

如果一棵二叉搜索樹的高度是平衡的，它就是AVL樹。如果它有n個結點，其高度可保持在LogN，搜索時間復雜度也是LogN。

二、AVL樹的定義

這里實現的是KV模型的AVL樹，因為set和map的底層是KV模型。

template<class K, class V>
struct AVLTreeNode
{//三叉鏈AVLTreeNode<K, V>* _left;   //左子樹AVLTreeNode<K, V>* _right;  //右子樹AVLTreeNode<K, V>* _parent; //自己的父親//存儲的鍵值對pair<K, V> _kv;//平衡因子(balance factor)int _bf; //右子樹高度-左子樹高度//構造函數AVLTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0){}
};

三、AVL樹的插入

AVL樹插入結點時有以下三個步驟：

  • 按照二叉搜索樹的插入方法(如果要插入的值比當前節點小，就往左子樹找；如果比當前節點大，就往右子樹找)，找到待插入位置。
  • 找到待插入位置后，將待插入結點插入到樹中。
  • 更新平衡因子，如果出現不平衡，則需要進行旋轉。

由于一個結點的平衡因子是否需要更新，是取決于該結點的左右子樹的高度是否發生了變化，因此插入一個結點后，該結點的祖先結點的平衡因子可能需要更新。

?我們插入結點后需要倒著往上更新平衡因子，更新規則如下：

  1. 新增結點在parent的右邊，parent的平衡因子+ +?
  2. 新增結點在parent的左邊，parent的平衡因子? ??

每更新完一個結點的平衡因子后，都需要進行以下判斷：

  • 如果parent的平衡因子等于-1或者1，表明還需要繼續往上更新平衡因子。
  • 如果parent的平衡因子等于0，表明無需繼續往上更新平衡因子了。
  • 如果parent的平衡因子等于-2或者2，表明此時以parent結點為根結點的子樹已經不平衡了，需要進行旋轉處理。

1.左單旋

新節點插入較高的右子樹的右側(右右)：左單旋

我們可以看到，插入9以后，parent的平衡因子已經發生改變，所以需要向左旋轉。

左單旋的步驟如下：

  1. 讓subR的左子樹作為parent的右子樹。
  2. 讓parent作為subR的左子樹。
  3. 讓subR作為整個子樹的根。
  4. 更新平衡因子。

/左單旋
void RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;Node* parentParent = parent->_parent; //parent的父親節點//1、建立subR和parent之間的關系parent->_parent = subR;subR->_left = parent;//2、建立parent和subRL之間的關系parent->_right = subRL;if (subRL)subRL->_parent = parent;//3、建立parentParent和subR之間的關系if (parentParent == nullptr)            //說明parent是根節點，不需要再向上調整{_root = subR;subR->_parent = nullptr; //subR的_parent指向需改變}else{if (parent == parentParent->_left)  //說明parent不是根節點，并且是他的父節點的左子樹{parentParent->_left = subR;}else //parent == parentParent->_right //說明parent不是根節點，并且是他的父節點的右子樹{parentParent->_right = subR;}subR->_parent = parentParent;}//4、更新平衡因子subR->_bf = parent->_bf = 0;
}

2.右單旋

新節點插入較高的左子樹的左側(左左)：右單旋

我們可以看到，插入1以后，parent的平衡因子已經發生改變，所以需要向右旋轉。

右單旋的步驟如下：

  1. 讓subL的右子樹作為parent的左子樹。
  2. 讓parent作為subL的右子樹。
  3. 讓subL作為整個子樹的根。
  4. 更新平衡因子。

//右單旋
void RotateR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;Node* parentParent = parent->_parent;  //parent的父親節點//1、建立subL和parent之間的關系subL->_right = parent;parent->_parent = subL;//2、建立parent和subLR之間的關系parent->_left = subLR;if (subLR)subLR->_parent = parent;//3、建立parentParent和subL之間的關系if (parentParent == nullptr)    //說明parent是根節點，不需要再向上調整{_root = subL;_root->_parent = nullptr;}else{if (parent == parentParent->_left)  //說明parent不是根節點，并且是他的父節點的左子樹{parentParent->_left = subL;}else //parent == parentParent->_right  //說明parent不是根節點，并且是他的父節點的右子樹{parentParent->_right = subL;}subL->_parent = parentParent;}//4、更新平衡因子subL->_bf = parent->_bf = 0;
}

3.左右雙旋

新節點插入較高左子樹的右側(左右)：先左單旋再右單旋

左右雙旋的步驟如下：

  1. 以subL為旋轉點進行左單旋。
  2. 以parent為旋轉點進行右單旋。
  3. 更新平衡因子。

subLR的平衡因子又分為三種情況:

  • 當subLR原始平衡因子是-1時，左右雙旋后parent、subL、subLR的平衡因子分別更新為1、0、0。

  • 當subLR原始平衡因子是1時，左右雙旋后parent、subL、subLR的平衡因子分別更新為0、-1、0。

  • 當subLR原始平衡因子是0時，左右雙旋后parent、subL、subLR的平衡因子分別更新為0、0、0。

//左右雙旋
void RotateLR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf; //subLR不可能為nullptr，因為subL的平衡因子是1//1、以subL為旋轉點進行左單旋RotateL(subL);//2、以parent為旋轉點進行右單旋RotateR(parent);//3、更新平衡因子if (bf == 1){subLR->_bf = 0;subL->_bf = -1;parent->_bf = 0;}else if (bf == -1){subLR->_bf = 0;subL->_bf = 0;parent->_bf = 1;}else if (bf == 0){subLR->_bf = 0;subL->_bf = 0;parent->_bf = 0;}else{assert(false); //在旋轉前樹的平衡因子就有問題}
}

4.右左雙旋

新節點插入較高右子樹的左側(左右)：先右單旋再左單旋

右左雙旋的步驟如下：

  1. 以subR為旋轉點進行右單旋。
  2. 以parent為旋轉點進行左單旋。
  3. 更新平衡因子。

subRL的平衡因子又分為三種情況:

  • 當subRL原始平衡因子是1時，左右雙旋后parent、subR、subRL的平衡因子分別更新為-1、0、0。

  • 當subRL原始平衡因子是-1時，左右雙旋后parent、subR、subRL的平衡因子分別更新為0、1、0。

  • 當subRL原始平衡因子是0時，左右雙旋后parent、subR、subRL的平衡因子分別更新為0、0、0。

//右左雙旋
void RotateRL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;//1、以subR為軸進行右單旋RotateR(subR);//2、以parent為軸進行左單旋RotateL(parent);//3、更新平衡因子if (bf == 1){subRL->_bf = 0;parent->_bf = -1;subR->_bf = 0;}else if (bf == -1){subRL->_bf = 0;parent->_bf = 0;subR->_bf = 1;}else if (bf == 0){subRL->_bf = 0;parent->_bf = 0;subR->_bf = 0;}else{assert(false); //在旋轉前樹的平衡因子就有問題}
}

5.整體代碼

//插入函數
bool Insert(const pair<K, V>& kv)
{if (_root == nullptr) //若AVL樹為空樹，則插入結點直接作為根結點{_root = new Node(kv);return true;}//1、按照二叉搜索樹的插入方法，找到待插入位置Node* cur = _root;Node* parent = nullptr;while (cur){if (kv.first < cur->_kv.first) //待插入結點的key值小于當前結點的key值{//往該結點的左子樹走parent = cur;cur = cur->_left;}else if (kv.first > cur->_kv.first) //待插入結點的key值大于當前結點的key值{//往該結點的右子樹走parent = cur;cur = cur->_right;}else //待插入結點的key值等于當前結點的key值{//插入失敗（不允許key值冗余）return false;}}//2、將待插入結點插入到樹中cur = new Node(kv); //根據所給值構造一個新結點if (kv.first < parent->_kv.first) //新結點的key值小于parent的key值{//插入到parent的左邊parent->_left = cur;cur->_parent = parent;}else //新結點的key值大于parent的key值{//插入到parent的右邊parent->_right = cur;cur->_parent = parent;}//3、更新平衡因子，如果出現不平衡，則需要進行旋轉while (cur != _root) //最壞一路更新到根結點{if (cur == parent->_left) //parent的左子樹增高{parent->_bf--; //parent的平衡因子--}else if (cur == parent->_right) //parent的右子樹增高{parent->_bf++; //parent的平衡因子++}//判斷是否更新結束或需要進行旋轉if (parent->_bf == 0) //更新結束（新增結點把parent左右子樹矮的那一邊增高了，此時左右高度一致）{break; //parent樹的高度沒有發生變化，不會影響其父結點及以上結點的平衡因子}else if (parent->_bf == -1 || parent->_bf == 1) //需要繼續往上更新平衡因子{//parent樹的高度變化，會影響其父結點的平衡因子，需要繼續往上更新平衡因子cur = parent;parent = parent->_parent;}else if (parent->_bf == -2 || parent->_bf == 2) //需要進行旋轉（此時parent樹已經不平衡了）{if (parent->_bf == -2){if (cur->_bf == -1){RotateR(parent); //右單旋}else //cur->_bf == 1{RotateLR(parent); //左右雙旋}}else //parent->_bf == 2{if (cur->_bf == -1){RotateRL(parent); //右左雙旋}else //cur->_bf == 1{RotateL(parent); //左單旋}}break; //旋轉后就一定平衡了，無需繼續往上更新平衡因子(旋轉后樹高度變為插入之前了)}else{assert(false); //在插入前樹的平衡因子就有問題}}return true; //插入成功
}

四、AVL樹的驗證

因為AVL樹的本質是二叉搜索樹，左子樹<根節點<右子樹,所以用中序遍歷的方法即可判斷。

但中序有序只能證明是二叉搜索樹，要證明二叉樹是AVL樹還需驗證二叉樹的平衡性，在該過程中我們可以順便檢查每個結點當中平衡因子是否正確。

采用后序遍歷，變量步驟如下：

  1. 從葉子結點處開始計算每課子樹的高度。（每棵子樹的高度 = 左右子樹中高度的較大值 + 1）
  2. 先判斷左子樹是否是平衡二叉樹。
  3. 再判斷右子樹是否是平衡二叉樹。
  4. 若左右子樹均為平衡二叉樹，則返回當前子樹的高度給上一層，繼續判斷上一層的子樹是否是平衡二叉樹，直到判斷到根為止。（若判斷過程中，某一棵子樹不是平衡二叉樹，則該樹也就不是平衡二叉樹了）
//判斷是否為AVL樹
bool IsAVLTree()
{int hight = 0; //輸出型參數return _IsBalanced(_root, hight);
}
//檢測二叉樹是否平衡
bool _IsBalanced(Node* root, int& hight)
{if (root == nullptr) //空樹是平衡二叉樹{hight = 0; //空樹的高度為0return true;}//先判斷左子樹int leftHight = 0;if (_IsBalanced(root->_left, leftHight) == false)return false;//再判斷右子樹int rightHight = 0;if (_IsBalanced(root->_right, rightHight) == false)return false;//檢查該結點的平衡因子if (rightHight - leftHight != root->_bf){cout << "平衡因子設置異常：" << root->_kv.first << endl;}//把左右子樹的高度中的較大值+1作為當前樹的高度返回給上一層hight = max(leftHight, rightHight) + 1;return abs(rightHight - leftHight) < 2; //平衡二叉樹的條件
}

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

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

相關文章

【網絡安全 | 漏洞挖掘】后端接受非預期參數的故事

【網絡安全 | 漏洞挖掘】后端接受非預期參數的故事

未經許可，不得轉載。 文章目錄 正文正文 在對某項目進行測試時，我遵循了一套系統化的方法論，以確保全面理解其安全性。 首先，我創建了一個賬戶，并從用戶的角度探索主域及其各項功能。此階段，我避免使用 Burp Suite 或其他工具，而是嘗試真正理解該應用的設計邏輯與交互…
閱讀更多...
01.01、判定字符是否唯一

01.01、判定字符是否唯一

01.01、[簡單] 判定字符是否唯一 1、題目描述 實現一個算法&#xff0c;確定一個字符串 s 的所有字符是否全都不同。 在這一題中&#xff0c;我們的任務是判斷一個字符串 s 中的所有字符是否全都不同。我們將討論兩種不同的方法來解決這個問題&#xff0c;并詳細解釋每種方法…
閱讀更多...
w208基于spring boot物流管理系統設計與實現

w208基于spring boot物流管理系統設計與實現

&#x1f64a;作者簡介&#xff1a;多年一線開發工作經驗&#xff0c;原創團隊&#xff0c;分享技術代碼幫助學生學習&#xff0c;獨立完成自己的網站項目。 代碼可以查看文章末尾??聯系方式獲取&#xff0c;記得注明來意哦~&#x1f339;贈送計算機畢業設計600個選題excel文…
閱讀更多...
《剛剛問世》系列初窺篇-Java+Playwright自動化測試-22- 操作鼠標拖拽 - 下篇（詳細教程）

《剛剛問世》系列初窺篇-Java+Playwright自動化測試-22- 操作鼠標拖拽 - 下篇（詳細教程）

1.簡介 上一篇中&#xff0c;宏哥說的宏哥在最后提到網站的反爬蟲機制&#xff0c;那么宏哥在自己本地做一個網頁&#xff0c;沒有那個反爬蟲的機制&#xff0c;谷歌瀏覽器是不是就可以驗證成功了&#xff0c;宏哥就想驗證一下自己想法&#xff0c;其次有人私信宏哥說是有那種…
閱讀更多...
神經網絡常見激活函數 8-SELU函數

神經網絡常見激活函數 8-SELU函數

SELU 縮放指數線性單元&#xff1a;SELU&#xff08;Scaled Exponential Linear Unit&#xff09; 函數導函數 SELU函數 S E L U ( x ) { λ x x > 0 λ α ( e x ? 1 ) x ≤ 0 \rm SELU(x) \left\{ \begin{array}{} \lambda x \quad & x > 0 \\ \lambda \alph…
閱讀更多...
【Elasticsearch】多字段查詢方式匯總

【Elasticsearch】多字段查詢方式匯總

在 Elasticsearch 中&#xff0c;實現多字段查詢的常見方式有以下幾種&#xff0c;每種方式適用于不同的場景&#xff1a; --- ### 1. **multi_match 查詢** - **用途**&#xff1a;在多個字段中執行同一查詢&#xff0c;支持多種匹配策略。 - **關鍵參數**&#xff1a…
閱讀更多...
多線之旅：wait 與 notify

多線之旅：wait 與 notify

今天小編繼續來分享下多線程中的一些內容。 在多線程環境下&#xff0c;由于線程調度的不確定性&#xff0c;所以我們有時候無法很好的去保證其線程的執行順序。 但是呢&#xff0c;我們又要實現這個順序執行&#xff0c;所以我們可以使用到這兩個方法&#xff0c;wait 和 no…
閱讀更多...
批量修改mysql字符串字段子字符串

批量修改mysql字符串字段子字符串

替換子字符串 使用 REPLACE 函數替換字段中的特定子字符串。 示例&#xff1a; 將 table_name 表中 column_name 字段的所有 old_value 替換為 new_value。 UPDATE table_name SET column_name REPLACE(column_name, old_value, new_value) WHERE column_name LIKE %old_val…
閱讀更多...
達夢：AWR 生成

達夢：AWR 生成

目錄標題 AWR 性能診斷與報告生成1. 檢查 AWR 系統狀態2. 查看數據庫中的所有表空間3. 查看現有的 AWR 快照4. 設置 AWR 快照的時間間隔5. 創建 AWR 快照6. 查看最新的 AWR 快照7. 生成 AWR HTML 報告8. 將 AWR 報告保存到指定文件鏈接總結 自動工作集負載信息庫 AWR 報告解析指…
閱讀更多...
股票數據接口API實例代碼python、JAVA等多種語言演示免費獲取實時數據、歷史數據、CDMA、KDJ等指標數據配有API說明文檔

股票數據接口API實例代碼python、JAVA等多種語言演示免費獲取實時數據、歷史數據、CDMA、KDJ等指標數據配有API說明文檔

? 本文中所有接口均可直接在瀏覽器打開獲取數據&#xff0c;為了便于大家驗證有效性&#xff0c;已經做好了超鏈接&#xff0c;直接點擊即可&#xff01; 滬深兩市股票列表 API接口鏈接&#xff08;可點擊驗證&#xff09;&#xff1a;https://api.mairui.club/hslt/list/b…
閱讀更多...
深入理解DOM：22個核心知識點與代碼示例

深入理解DOM：22個核心知識點與代碼示例

本文系統介紹DOM相關的22個核心概念&#xff0c;每個知識點均提供代碼示例及簡要說明&#xff0c;幫助開發者全面掌握DOM操作技巧。 一、DOM基礎概念 1. DOM概念 DOM&#xff08;Document Object Model&#xff09;是HTML/XML的編程接口&#xff0c;通過JavaScript可動態修改…
閱讀更多...
【Map vs Set】：Java數據存儲的“雙子星”對決

【Map vs Set】：Java數據存儲的“雙子星”對決

個人主頁&#xff1a;?喜歡做夢 歡迎 &#x1f44d;點贊 ?關注 ??收藏 &#x1f4ac;評論 目錄 &#x1f370;一、搜索 &#x1f36e;1.概念 &#x1f36e;2.模型 &#x1f370;二、Map &#x1f368;1.什么是Map&#xff1f; &#x1f368;2.Map的實例化 &…
閱讀更多...
【C語言 】C語言 桌游開發數字競拍（源碼）【獨一無二】

【C語言 】C語言 桌游開發數字競拍（源碼）【獨一無二】

&#x1f449;博__主&#x1f448;&#xff1a;米碼收割機 &#x1f449;技__能&#x1f448;&#xff1a;C/Python語言 &#x1f449;專__注&#x1f448;&#xff1a;專注主流機器人、人工智能等相關領域的開發、測試技術。 【C語言 】C語言 桌游開發數字競拍&#xff08;源碼…
閱讀更多...
Reinforcement Learning Heats Up 強化學習持續升溫

Reinforcement Learning Heats Up 強化學習持續升溫

Reinforcement Learning Heats Up 強化學習持續升溫 核心觀點&#xff1a;強化學習正成為構建具有高級推理能力大語言模型&#xff08;LLMs&#xff09;的重要途徑。 最新進展 模型示例&#xff1a;近期出現了如DeepSeek - R1及其變體&#xff08;DeepSeek - R1 - Zero&#xf…
閱讀更多...
Whisper+T5-translate實現python實時語音翻譯

Whisper+T5-translate實現python實時語音翻譯

1.首先下載模型&#xff0c;加載模型 import torch import numpy as np import webrtcvad import pyaudio import queue import threading from datetime import datetime from faster_whisper import WhisperModel from transformers import AutoTokenizer, AutoModelForSeq2…
閱讀更多...
湖倉分析｜浙江霖梓基于 Doris + Paimon 打造實時/離線一體化湖倉架構

湖倉分析｜浙江霖梓基于 Doris + Paimon 打造實時/離線一體化湖倉架構

導讀&#xff1a;浙江霖梓早期使用 CDH 產品套件搭建了大數據系統&#xff0c;面臨業務邏輯冗余、查詢效率低下等問題&#xff0c;基于 Apache Doris 進行整體架構與表結構的重構&#xff0c;并基于湖倉一體和查詢加速展開深度探索與實踐&#xff0c;打造了 Doris Paimon 的實…
閱讀更多...
git bash在github的庫中上傳或更新本地文件

git bash在github的庫中上傳或更新本地文件

一、將本地文件上傳到 GitHub 倉庫 1. 創建 GitHub 倉庫 如果你還沒有在 GitHub 上創建倉庫&#xff0c;首先需要創建一個新的倉庫&#xff1a; 登錄到 GitHub。點擊右上角的 按鈕&#xff0c;選擇 New repository。給你的倉庫起個名字&#xff0c;并選擇 Public 或 Privat…
閱讀更多...
Jmeter壓測怎么控制TPS

Jmeter壓測怎么控制TPS

壓測固定TPS的接口 有些任務需要我們控制接口的TPS&#xff0c;例如每秒請求一次。 TPS定時器 然后1個并發持續運行 壓測結果 需要注意TPS在1.0/s左右&#xff0c;有時可能是1.2、1.3&#xff0c;定時器會自動調整壓力&#xff0c;讓TPS保持在1.0左右。
閱讀更多...
ArcGISPro 新建shp+數據結構

ArcGISPro 新建shp+數據結構

import arcpy# 設置工作空間和 Shapefile 存放路徑 shp_path r"C:\path\to\your\folder\PolygonZY.shp" # Shapefile 存放路徑 fields [("CHBH", "TEXT", 20),("ZCMC", "TEXT", 100),("ZCLX", "TEXT"…
閱讀更多...
理解WebGPU 中的 GPUAdapter ：連接瀏覽器與 GPU 的橋梁

理解WebGPU 中的 GPUAdapter ：連接瀏覽器與 GPU 的橋梁

在 WebGPU 開發中&#xff0c; GPUAdapter 是一個至關重要的對象&#xff0c;它作為瀏覽器與 GPU 之間的橋梁&#xff0c;為開發者提供了請求 GPU 設備、查詢 GPU 特性以及獲取適配器信息的能力。本文將詳細介紹 GPUAdapter 的核心屬性和方法&#xff0c;并通過實際代碼…
閱讀更多...
最新文章

Copyright @ 2022~2023