數據結構：探秘AVL樹

本節重點

  • 理解AVL樹的概念
  • 掌握AVL樹正確的插入方法
  • 利用_parent指針正確更新平衡因子
  • 掌握并理解四種旋轉方式：左單旋，右單旋，左右雙旋，右左雙旋

一、AVL樹的概念

AVL樹得名于它的發明者G. M. Adelson-Velsky和E. M. Landis，他們在1962年的論文《An algorithm for the organization of information》中發表了它。

AVL樹最先發明自平衡二叉搜索樹，AVL是一顆空樹，或者具備下列性質的二叉搜索樹：它的左右子樹都是AVL樹，且左右子樹的高度差的絕對值不超過1。AVL樹是一顆高度平衡搜索二叉樹，通過控制高度差去控制平衡。

AVL樹的實現引入一個平衡因子的概念（balance factor）的概念，每個節點都有一個平衡因子，任何節點的平衡因子等于右子樹高度減去左子樹高度，也就是說任何節點的平衡因子等于0/1/-1，AVL樹并不是必須要平衡因子，但是有了平衡因子可以更方便我們去進行觀察和控制樹是否平衡，就像一個風向標一樣。

AVL樹整體的節點數量和分布和完全二叉樹類似，但是AVL樹高度可以控制在logN，所以增刪查改的效率也可以控制在O(logN)，相比二叉搜索樹有了本質的提升。

如圖，每個節點上方的小數字表示該節點的平衡因子，平衡因子只能為-1/1/0當為2/-2時我們要通過旋轉將左右子樹重新達到平衡狀態。?

二、AVL樹的實現

2.1 AVL樹的結構

AVL樹我們分成兩部分來實現，一部分是單個節點的定義，一部分是AVL樹。并且用兩個類進行封裝：

template<class K>
struct AVLTNode//AVL樹節點的定義
{K _key;struct AVLTNode<K>* _left;struct AVLTNode<K>* _right;struct AVLTNode<K>* _parent;//引入parent方便我們快速向上更新平衡因子int _bf;//平衡因子（balance factor）//構造函數：AVLTNode(K key):_key(key), _left(nullptr), _right(nullptr), _parent(nullptr),_bf(0){}
};//AVL樹的定義
template<class K>
class AVLTree
{typedef struct AVLTNode<K> Node;
public:
private:Node* root = nullptr;
};

2.2 AVL樹的插入

AVL樹插入的步驟：

  1. 插入一個值按照二叉搜索樹的規則插入
  2. 新增節點后，只會影響祖先節點的高度，也就是可能會影響部分祖先節點的平衡因子，所以更新從新增節點->根節點路徑上的平衡因子，實際最壞情況下更新到根，有些情況更新到中間就停止了。
  3. 更新平衡因子過程中沒有出現問題，則插入結束
  4. 更新平衡因子的過程中出現不平衡，對不平衡子樹旋轉，旋轉后降低了子樹的高度，不會再影響上一層，所以插入結束

2.2.1 先按照搜索二叉樹規則插入

在插入之前，我們需要判斷該AVL樹是否為空，若為空直接在_root 新增節點并返回，若不為空說明AVL樹中已經存在節點，這時我們需要從根節點開始依次按照搜索樹的規則尋找插入位置，找到之后創建新節點并鏈入到AVL樹中。

代碼示例：

bool Insert(const K& key){if (_root == nullptr){//AVL是一顆空樹_root=new Node(key)return 1;}else{Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{assert(false);}}//鏈接新節點：cur = new Node(key);if (cur->_key > parent->_key){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;}

2.2.2 判斷并更新平衡因子

更新規則：

平衡因子=右子樹高度-左子樹高度

插入節點會增加子樹高度，影響當前節點平衡因子因為一次只能插入一個節點所以平衡因子要么++要么--：

插入在右子樹平衡因子++；插入在左子樹平衡因子--。

平衡因子的三種情況：（0，-1/1，-2/2）

1、更新后parent節點平衡因子為0

說明更新之前parent節點平衡因子為1或-1也就是左右子樹一邊高一邊低，節點插入在低的一邊，插入后左右平衡不會影響上一級節點的平衡因子。

2、更新后parent節點平衡因子為1/-1

說明更新之前parent節點平衡因子為0，插入后左右子樹一邊高一邊低會影響上一級節點的平衡因子，所以要繼續向上更新。

3、更新后parent節點平衡因子為2/-2

說明更新之前parent節點平衡因子為1/-1也就是左右子樹一邊高一邊低，節點插入在高的一邊

代碼示例：?

while (parent)
{if (parent->_right == cur){parent->_bf++;}else{parent->_bf--;}if (parent->_bf == 0){//說明新增節點在低的一邊，插入后左右子樹平衡//不會影響祖先節點的 _bf直接breakbreak;}else if(parent->_bf==1||parent->_bf==-1){//新增節點之后為1或-1說明之前為0（左右子樹平衡）//此時需要更新依次更新祖先節點的 _bf直到更新到根節點或某一祖先節點_bf==0cur = parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2){if (parent->_bf == 2 && cur->_bf == 1){//單純右邊高，左旋RotateL(parent);}else if (parent->_bf == -2 && cur->_bf == -1){//單純左邊高，右旋RotateR(parent);}else if (parent->_bf == 2 && cur->_bf == -1){//先左后右，右左雙旋RotateRL(parent);}else if (parent->_bf == -2 && cur->_bf == 1){//先右后左，左右雙旋RotateLR(parent);}else{assert(false);}break;}else{assert(false);}
}

2.2.3 （不平衡）旋轉子樹

旋轉的原則：

  • 保持搜索樹的規則
  • 讓旋轉的樹從不滿足變為平衡，其次降低樹的高度

首先我們需要明白的是旋轉操作分為兩部分，一是調整節點之間的鏈接關系，二是更新平衡因子? ? ?_bf

左單旋(RotateL)

當parent的平衡因子為2，且cur的平衡因子為1時AVL樹會呈現右子樹一邊高的形式，這時我們需要進行左旋操作，需要注意的是滿足 parent->_bf==2 && cur->_bf==1 條件的AVL樹的形式可能有多種：

為了便于理解，我們可以選擇一種簡單的情況進行分析并寫出相應代碼：

代碼示例：

void RotateL(Node* parent){Node* SubR = parent->_right;Node* SubRL = SubR->_left;Node* pparent = parent->_parent;if (SubRL){SubRL->_parent = parent;}parent->_right = SubRL;SubR->_left = parent;parent->_parent = SubR;if (parent == _root){_root = SubR;SubR->_parent = nullptr;}else{if (pparent->_right == parent){pparent->_right = SubR;}else{pparent->_left = SubR;}SubR->_parent = pparent;}//節點鏈接關系調整完成后更新平衡因子：SubR->_bf = 0;parent->_bf = 0;}
右單旋(RotateR)

類似的是，滿足 parent->_bf==-2 && cur->_bf==-1 條件的AVL樹的形式也可能有多種

我們也選擇其中一種簡單的情況進行分析和編寫代碼：

void RotateR(Node* parent){Node* SubL = parent->_left;Node* SubLR = SubL->_right;Node* pparent = parent->_parent;if (SubLR){SubLR->_parent = parent;}parent->_left = SubLR;SubL->_right = parent;parent->_parent = SubL;if (parent == _root){_root = SubL;SubL->_parent = nullptr;}else{if (pparent->_right == parent){pparent->_right = SubL;}else{pparent->_left = SubL;}SubR->_parent = pparent;}//節點鏈接關系調整完成后更新平衡因子：SubL->_bf = 0;parent->_bf = 0;}
左右雙旋(RotateLR)

與單旋不同的是，雙旋對應的AVL樹的結構不再是單純一邊高，我們由條件判斷很容易就可以看出來（parent->_bf == -2 && cur->_bf == 1 或 parent->_bf == 2 && cur->_bf == -1），此時我們發現AVL樹節點類似“折線形”排列，這時單純的單旋無法使二叉樹再次平衡，我們需要進行兩次單旋來解決。

類似的是滿足雙旋觸發條件時，AVL樹的結構要是拓展開來也有非常多種情況，我們可以選擇其中一種較為簡單的情況來分析并編寫相應代碼：

需要注意的是左右雙旋的時候對SubLR的_bf也要進行考慮，目的是確定SubLR是否存在單個的子樹，因為最終SubLR的子樹會鏈入SubL或者parent影響兩個節點的平衡因子。

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;parent->_bf = 0;SubL->_bf = -1;}else if (bf == 0){parent->_bf = 0;SubLR->_bf = 0;SubL->_bf = 0;}else{SubLR->_bf = 0;parent->_bf = 1;SubL->_bf = 0;}}
右左雙旋(RotateRL)

?

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 = -1;SubR->_bf = 0;}else if (bf == 0){parent->_bf = 0;SubLR->_bf = 0;SubL->_bf = 0;}else{SubRL->_bf = 0;parent->_bf = 0;SubR->_bf = 1;}}

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

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

相關文章

電源系統的熱設計與熱管理--以反激式充電器為例

電源系統的熱設計與熱管理--以反激式充電器為例

前言 反激電源常用于各種電子設備中&#xff0c;比如充電器、適配器等&#xff0c;它們通過變壓器進行能量轉換。高溫環境可能對電子元件造成影響&#xff0c;特別是像MOSFET、二極管、變壓器這樣的關鍵部件&#xff0c;導致效率變低&#xff0c;甚至可能導致功能失效。還有安…
閱讀更多...
linux課程學習二——緩存

linux課程學習二——緩存

一.文件io與標準io的一個區別 遇到死循環可以ctrl c結束進程 使用printf輸出&#xff0c;輸出沒有問題 用wirte輸出&#xff0c;參數1&#xff0c;可以理解為上面介紹的linux標準文件描述符的1&#xff08;STDOUT&#xff09;標準輸出&#xff0c;我們加上一個死循環while&…
閱讀更多...
Kafka中的消息如何分配給不同的消費者？

Kafka中的消息如何分配給不同的消費者？

大家好&#xff0c;我是鋒哥。今天分享關于【Kafka中的消息如何分配給不同的消費者&#xff1f;】面試題。希望對大家有幫助&#xff1b; Kafka中的消息如何分配給不同的消費者&#xff1f; 在 Kafka 中&#xff0c;消息是通過 主題&#xff08;Topic&#xff09; 進行組織的&…
閱讀更多...
Android的安全問題 - 在 Android 源碼的 system/sepolicy 目錄中，區分 public、private 和 vendor的目的

Android的安全問題 - 在 Android 源碼的 system/sepolicy 目錄中，區分 public、private 和 vendor的目的

參考&#xff1a;Google文檔 在 Android 8.0 及更高版本中自定義 SEPolicy 在 Android 源碼的 system/sepolicy 目錄中&#xff0c;區分 public、private 和 vendor 是為了模塊化 SELinux 策略&#xff0c;并明確不同部分的訪問權限和接口邊界。這種設計主要基于以下原因&…
閱讀更多...
Java NIO之FileChannel 詳解

Java NIO之FileChannel 詳解

關鍵點說明 文件打開選項&#xff1a; StandardOpenOption.CREATE - 文件不存在時創建 StandardOpenOption.READ/WRITE - 讀寫權限 StandardOpenOption.APPEND - 追加模式 StandardOpenOption.TRUNCATE_EXISTING - 清空已存在文件 緩沖區操作&#xff1a; ByteBuffer.wrap…
閱讀更多...
stock-pandas，一個易用的talib的替代開源庫。

stock-pandas，一個易用的talib的替代開源庫。

原創內容第841篇&#xff0c;專注智能量化投資、個人成長與財富自由。 介紹一個ta-lib的平替——我們來實現一下&#xff0c;最高價突破布林帶上軌&#xff0c;和最低價突破布林帶下軌的可視化效果&#xff1a; cross_up_upper stock[high].copy()# cross_up_upper 最高價突破…
閱讀更多...
JVM 面經

JVM 面經

1、什么是 JVM? JVM 就是 Java 虛擬機&#xff0c;它是 Java 實現跨平臺的基石。程序運行之前&#xff0c;需要先通過編譯器將 Java 源代碼文件編譯成 Java 字節碼文件&#xff1b;程序運行時&#xff0c;JVM 會對字節碼文件進行逐行解釋&#xff0c;翻譯成機器碼指令&#x…
閱讀更多...
【JavaScript】合體期功法——DOM（一）

【JavaScript】合體期功法——DOM（一）

目錄 DOMWeb API 基本概念作用和分類 什么是 DOMDOM 樹DOM 對象 獲取 DOM 元素根據 CSS 選擇器來獲取 DOM 元素選擇匹配的第一個元素選擇匹配的多個元素 其他獲取 DOM 元素方法 修改元素的內容對象.innerText 屬性對象.innerHTML 屬性案例&#xff1a;年會抽獎 修改元素屬性修改…
閱讀更多...
GAMMA數據處理（十）

GAMMA數據處理（十）

今天向別人請教了一個問題&#xff0c;剛無意中搜索到了一模一樣的問題 不知道這個怎么解決... ok 解決了 有一個GAMMA的命令可轉換 但是很奇怪 完全對不上 轉換出來的行列號 不知道為啥 再試試 是因為經緯度坐標的小數點位數 de as
閱讀更多...
Java入門知識總結——章節（二）

Java入門知識總結——章節（二）

ps&#xff1a;本章主要講數組、二維數組、變量 一、數組 數組是一個數據容器&#xff0c;可用來存儲一批同類型的數據 &#x1f511;&#xff1a;注意 類也可以是一個類的數組 public class Main {public static class Student {String name;int age; // 移除 unsignedint…
閱讀更多...
動態IP：網絡世界的“變色龍”如何改變你的在線體驗？

動態IP：網絡世界的“變色龍”如何改變你的在線體驗？

你知道嗎&#xff1f;有時候我覺得動態IP就像是網絡世界里的“變色龍”。它不像靜態IP那樣一成不變&#xff0c;而是隨時在變化&#xff0c;像是一個永遠在換衣服的演員。你永遠不知道它下一秒會變成什么樣子&#xff0c;但正是這種不確定性&#xff0c;讓它變得特別有趣。想象…
閱讀更多...
從24GHz到71GHz：Sivers半導體的廣泛頻率范圍5G毫米波產品解析

從24GHz到71GHz：Sivers半導體的廣泛頻率范圍5G毫米波產品解析

在5G技術的浪潮中&#xff0c;Sivers半導體推出了創新的毫米波無線產品&#xff0c;為通信行業帶來高效、可靠的解決方案。這些產品支持從24GHz到71GHz的頻率&#xff0c;覆蓋許可與非許可頻段&#xff0c;適應高速、低延遲的通信場景。 5G通信頻段的一點事兒及Sivers毫米波射頻…
閱讀更多...
aocache:AOCache 新增功能深度解析：從性能監控到靈活配置的全方位升級

aocache:AOCache 新增功能深度解析：從性能監控到靈活配置的全方位升級

最近對aocache 進行了重要升級&#xff0c;最新版本0.6.0增加了幾項新功能&#xff1a;性能分析日志&#xff0c;AOCache性能分析工具&#xff0c;切入點自定義配置&#xff0c;全局配置&#xff0c;本文詳細說明這幾項目新功能的作用和使用方式。 一、性能分析日志 需求背景…
閱讀更多...
Java EE 進階：MyBatis-plus

Java EE 進階：MyBatis-plus

MyBatis-plus的介紹 MyBatis-plus是MyBatis的增強工具&#xff0c;在MyBatis的基礎上做出加強&#xff0c;只要MyBatis有的功能MyBatis-plus都有。 MyBatis-plus的上手 添加依賴 在我們創建項目的時候&#xff0c;我們需要添加MyBatis-plus和mysql的依賴 MyBatis-plus的依賴…
閱讀更多...
GitHub和Gitee上的一些AI項目

GitHub和Gitee上的一些AI項目

以下是GitHub和Gitee上的一些AI項目&#xff1a; GitHub上的AI項目 TensorFlow&#xff1a;一個端到端開源機器學習平臺&#xff0c;包含大量工具和庫&#xff0c;廣泛應用于圖像識別、自然語言處理等領域。PyTorch&#xff1a;由Facebook開發的開源深度學習框架&#xff0c;…
閱讀更多...
JavaScript網頁設計高級案例：構建交互式圖片畫廊

JavaScript網頁設計高級案例：構建交互式圖片畫廊

JavaScript網頁設計高級案例&#xff1a;構建交互式圖片畫廊 在現代Web開發中&#xff0c;交互式元素已成為提升用戶體驗的關鍵因素。本文將通過一個高級案例 - 構建交互式圖片畫廊&#xff0c;展示如何結合HTML和JavaScript創建引人入勝的網頁應用。這個案例不僅涵蓋了基礎的…
閱讀更多...
Linux命令大全：從入門到高效運維

Linux命令大全：從入門到高效運維

適合人群&#xff1a;Linux新手 | 運維工程師 | 開發者 目錄 一、Linux常用命令&#xff08;每天必用&#xff09; 1. 文件與目錄操作 2. 文件內容查看與編輯 二、次常用命令&#xff08;按需使用&#xff09; 1. 系統管理與監控 2. 網絡與通信 3. 權限與用戶管理 三、…
閱讀更多...
Windows 10/11 使用 VSCode + SSH 免密遠程連接 Ubuntu 服務器（指定端口)

Windows 10/11 使用 VSCode + SSH 免密遠程連接 Ubuntu 服務器（指定端口)

摘要&#xff1a; 本文詳細介紹如何在 Windows 系統上通過 VSCode Remote-SSH 免密登錄遠程 Ubuntu 服務器&#xff08;SSH 端口 2202&#xff09;&#xff0c;避免每次輸入密碼的繁瑣操作&#xff0c;提高開發效率。 1. 環境準備 本地系統&#xff1a;Windows 10/11遠程服務…
閱讀更多...
一些需要學習的C++庫：CGAL和Eysshot

一些需要學習的C++庫：CGAL和Eysshot

寫在前面&#xff1a; 從開始工作到現在&#xff0c;去過多家公司&#xff0c;多個行業&#xff0c; 雖然大部分時間在通信業&#xff0c;但也有其它的行業的工作沒有做完&#xff0c;但也很感興趣。每次想要研究一下時&#xff0c;總是想不起來。 這里寫一些信息&#xff0c;…
閱讀更多...
藍橋杯16天刷題計劃一一Day01

藍橋杯16天刷題計劃一一Day01

藍橋杯16天刷題計劃一一Day01&#xff08;STL練習&#xff09; 作者&#xff1a;blue 時間&#xff1a;2025.3.26 文章目錄 藍橋杯16天刷題計劃一一Day01&#xff08;STL練習&#xff09;[P1540 [NOIP 2010 提高組\] 機器翻譯 - 洛谷 (luogu.com.cn)](https://www.luogu.com.…
閱讀更多...
最新文章

Copyright @ 2022~2023