【C++高階(四)】紅黑樹深度剖析--手撕紅黑樹!

💓博主CSDN主頁:杭電碼農-NEO💓
?
?專欄分類:C++從入門到精通?
?
🚚代碼倉庫:NEO的學習日記🚚
?
🌹關注我🫵帶你學習C++
? 🔝🔝

在這里插入圖片描述

紅黑樹

  • 1. 前言
  • 2. 紅黑樹的概念以及性質
  • 3. 紅黑樹為什么更實用?
  • 4. 紅黑樹模擬實現代碼框架
  • 5. 紅黑樹的插入操作初步分析
  • 6. 紅黑樹的插入操作詳解(一)
  • 7. 紅黑樹的插入操作詳解(二)
  • 8. 紅黑樹的插入代碼實現
  • 9. 總結以及拓展

1. 前言

如果說發明AVL樹的人是天才,那么
發明紅黑樹的人可以稱為天才中的
精英!為什么AVL樹這么強大但是沒啥
人用呢?就是因為紅黑樹比你還好!

本章重點:

本篇文章著重講解紅黑樹的概念以及
性質,以及為了維護紅黑樹這種性質而
做的限制條件.最后模擬實現紅黑樹的
插入,帶大家熟悉變色和旋轉規則!

2. 紅黑樹的概念以及性質

紅黑樹的概念:

  • 首先紅黑樹是一顆二叉搜索樹
  • 每個節點都有顏色,紅色或黑色
  • 最長路徑最多是最短路徑的二倍

在這里插入圖片描述

紅黑樹的性質:

  1. 每個結點不是紅色就是黑色
  2. 根節點是黑色的
  3. 如果一個節點是紅色的
    則它的兩個孩子結點是黑色的
  4. 每條路徑上的黑色節點數相同
  5. 每個葉子結點都是黑色的
    (此處的葉子結點指的是空結點)
為啥滿足了以上性質的紅黑樹就一定
能做到最長路徑最多是最短路徑的二倍?
下面我畫一個極限情況來分析一下!

在這里插入圖片描述

3. 紅黑樹為什么更實用?

現在將AVL數和紅黑樹做一個對比:

  • AVL樹闡析:

AVL樹是一顆高度平衡二叉樹,
它的高度差不能大于1,所以AVL
樹的查找是妥妥的O(logn),但是
由于AVL樹嚴格的標準,使得在使用
AVL樹時會經常旋轉,反而增加了時間!

  • 紅黑樹闡析:

紅黑樹是一顆接近平衡的二叉樹
它最長路徑最多是最短路徑的二倍
所以查找的效率是:logn~2logn,
然而2logn和logn是一個量級的,
并且紅黑樹的規則沒有這么嚴格,
不會涉及到更多旋轉和變色!

綜上所述,紅黑樹的效率雖然比
AVL樹差一點,但是總體來說紅黑樹勝!

4. 紅黑樹模擬實現代碼框架

首先,每個節點都要存一個顏色,
這里我們使用枚舉enum來實現
并且和AVL一樣也是三叉鏈!
請看代碼:

enum Colour
{RED,BLACK
};
template<class K,class V>
struct RBTreeNode
{RBTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv),_col(RED){}RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;pair<K, V> _kv; Colour _col;
};template<class K, class V>
struct RBTree
{
typedef RBTreeNode<K, V> Node;
private:Node* _root = nullptr;
};

有了代碼框架后,現在來看看插入

5. 紅黑樹的插入操作初步分析

和AVL樹很相似,紅黑樹的插入
也是分為兩步走:

  1. 按照二叉搜索樹的規則插入值
  2. 插入后根據顏色或高度做旋轉或變色

眾所周知啊,第一步很簡單
甚至可以將之前的代碼抄過來:

bool insert(const pair<K, V>& kv)//第一步:按照二叉搜索樹的方式插入值
{if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}Node* cur = _root;Node* parent = nullptr;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;elseparent->_left = cur;//此時new出來的節點的parent還指向空cur->_parent = parent;///前面的過程和AVL樹一致
}

走到這步后,有個問題,新插入的節點
是選擇插入紅色還是黑色?

對于這個問題,我們要思考兩個點,
一是如果插入的是黑色節點,我們
可能會打破哪個規則?如果是插入
紅色節點又可能會打破哪個規則?

  • 插入黑色節點,打破規則四,很難辦
    因為每個路徑檢查起來很難!

  • 插入紅色節點,打破規則三,比打破
    四要好一些,因為只用看父親是否為紅

綜上所述,插入紅色更優!
換句話說,你犯錯肯定寧愿犯輕一點
的錯誤被媽媽打一頓,也不愿意犯很重
的錯直接被家族除名了對吧[doge]

6. 紅黑樹的插入操作詳解(一)

如果插入的節點的父親是黑色節點,
那么正是我們想看見的,不用管它了!

那么如果插入的節點的父親是紅色呢?
很明顯,這違反了規則三,有連續的紅色
節點,所以此時需要做處理了!

先來看一個最簡單的情況:

在這里插入圖片描述

其實紅黑樹插入節點后的變色和
旋轉規則主要是看叔叔,叔叔的情況
不同,那么對應的處理手段就不同,這里
只通過簡單變色手段就可以滿足規則了!
并且在上圖中,將爺爺變成紅色后可能會
出現問題,因為爺爺的父親不知道是紅色
還是黑色,所以要不斷向上做判斷

若不向上更新,可能會有這種情況:

在這里插入圖片描述

7. 紅黑樹的插入操作詳解(二)

當講解完最簡單的情況后,還剩下兩種
情況,這兩種情況內部又可細分出幾種
情況,請同學們耐心學習!

情況二:cur為紅.p為紅.g為黑.u不存在/為黑
(并且cur和p都是左或右)

在這里插入圖片描述
在這里插入圖片描述

p為g的左孩子,cur為p的左孩子,則右單旋
p為g的右孩子,cur為p的右孩子,則左單旋
p,g變色—p變黑，g變紅

情況三:cur為紅.p為紅.g為黑.u不存在/為黑
(并且若p是g的左,cur就是p的右)

在這里插入圖片描述

p為g的左孩子,cur為p的右孩子,則做左單旋
p為g的右孩子,cur為p的左孩子,則做右單旋
則轉換成了情況二

至此,紅黑樹的插入的所有情況都
講解完畢,接下來就是代碼實現了!

8. 紅黑樹的插入代碼實現

在整個大情況分類中,可以歸為兩類
一是叔叔為紅色,二是叔叔為黑色或者
叔叔不存在,我們圍繞著這兩個大方向寫!

//走到這一步后,就已經找到cur和parent了!
while (parent && parent->_col == RED)//當parent為黑就不用往上更新了
{if (parent == _root){_root->_col = BLACK;break;}Node* grandf = parent->_parent;assert(grandf);assert(grandf->_col == BLACK);Node* uncle = nullptr;if (parent == grandf->_left)//判斷叔叔在par的左還是右uncle = grandf->_right;else uncle = grandf->_left;if (uncle == nullptr || uncle->_col == BLACK)//uncle為空或為黑有四種情況來變色＋旋轉{if (parent == grandf->_left && cur == parent->_left)//左左->右旋＋變色{RotateR(grandf);parent->_col = BLACK;grandf->_col = RED;break;}else if (parent == grandf->_right && cur == parent->_right)//右右->左旋+變色{RotateL(grandf);parent->_col = BLACK;grandf->_col = RED;break;}else if (parent == grandf->_left && cur == parent->_right)//左右->先左旋再右旋再變色{RotateL(parent);RotateR(grandf);cur->_col = BLACK;grandf->_col = RED;break;}else if (parent == grandf->_right && cur == parent->_left)//右左->先右旋再左旋再變色{RotateR(parent);RotateL(grandf);cur->_col = BLACK;grandf->_col = RED;break;}}else if (uncle && uncle->_col == RED)//叔叔為紅,直接變色,不旋轉{parent->_col = BLACK;uncle->_col = BLACK;grandf->_col = RED;cur = grandf;parent = cur->_parent;//將parent更新后往上傳!}_root->_col = BLACK;
}

可以發現一個問題,只要是叔叔的顏色
是黑色或叔叔不存在的情況下,執行完
旋轉＋變色后都直接break了,這是因為
在這種情況下,父親節點都被變成了黑色,
也就沒必要繼續往上了!并且在紅黑樹的
左旋和右旋中,代碼其實和AVL樹的旋轉是
一模一樣的,所以直接copy一份就行了!

若你不清楚旋轉的代碼,請看這篇文章:

AVL樹模擬實現!

9. 總結以及拓展

AVL樹和紅黑樹的代碼實現都只講解
了插入操作,因為刪除操作太復雜了,
并且就算實現了刪除操作也沒有太大
的實際意義,所以只需要了解插入即可!

并不是需要你真正的會手撕!

拓展閱讀:

紅黑樹的刪除圖解

🔎 下期預告:哈希表,哈希桶 🔍

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

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

相關文章

計算機網絡之數據鏈路層

計算機網絡之數據鏈路層

一、概述 1.1概述 物理層發出去的信號需要通過數據鏈路層才知道是否到達目的地&#xff1b;才知道比特流的分界線 鏈路(Link)&#xff1a;從一個結點到相鄰結點的一段物理線路&#xff0c;中間沒有任何其他交換結點數據鏈路(Data Link)&#xff1a;把實現通信協議的硬件和軟件…
閱讀更多...
電商API接口|電商數據接入|拼多多平臺根據商品ID查商品詳情SKU和商品價格參數

電商API接口|電商數據接入|拼多多平臺根據商品ID查商品詳情SKU和商品價格參數

隨著科技的不斷進步&#xff0c;API開發領域也逐漸呈現出蓬勃發展的勢頭。今天我將向大家介紹API接口&#xff0c;電商API接口具備獨特的特點&#xff0c;使得數據獲取變得更加高效便捷。 快速獲取API數據——優化數據訪問速度 傳統的數據獲取方式可能需要經過多個中介環節&…
閱讀更多...
華大基因認知障礙基因檢測服務，助力認知障礙疾病防控

華大基因認知障礙基因檢測服務，助力認知障礙疾病防控

認知障礙是一種嚴重的神經系統疾病&#xff0c;對人類的腦健康產生了重大影響。據報告顯示&#xff0c;在我國65歲以上的人群中&#xff0c;存在輕度認知障礙的患者約為3,800萬&#xff0c;而中重度癡呆患者則約為1,500萬&#xff0c;患病人口數量龐大。這種疾病不僅會對患者的…
閱讀更多...
免費多域名SSL證書

免費多域名SSL證書

顧名思義&#xff0c;免費多域名SSL證書就是一種能夠為多個域名或子域提供HTTPS安全保護的證書。這意味著&#xff0c;如果您有三個域名——例如example.com、example.cn和company.com&#xff0c;您可以使用一個免費的多域名SSL證書為所有這些域名提供安全保障&#xff0c;而無…
閱讀更多...
TransFusionNet：JetsonTX2下肝腫瘤和血管分割的語義和空間特征融合框架

TransFusionNet：JetsonTX2下肝腫瘤和血管分割的語義和空間特征融合框架

TransFusionNet: Semantic and Spatial Features Fusion Framework for Liver Tumor and Vessel Segmentation Under JetsonTX2 TransFusionNet&#xff1a;JetsonTX2下肝腫瘤和血管分割的語義和空間特征融合框架背景貢獻實驗方法Transformer-Based Semantic Feature Extractio…
閱讀更多...
pyhton接口猜用戶登錄和密碼

pyhton接口猜用戶登錄和密碼

import requests import base64 NUM 0 # 讀取 URL 文件內容并生成 URL 列表 with open("urlall.txt", r) as file:urls [url.strip() for url in file.readlines() if url.strip()]# 讀取密碼文件內容并生成密碼列表 with open("password.txt", r) as fil…
閱讀更多...
前端下載多個文件鏈接整合為壓縮包

前端下載多個文件鏈接整合為壓縮包

前端下載多個文件鏈接整合為壓縮包 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>Document</ti…
閱讀更多...
AI寫代碼 可以代替人工嗎？

AI寫代碼 可以代替人工嗎？

近年AI技術非常火熱&#xff0c;有人就說&#xff0c;用AI寫代碼程序員不就都得下崗嗎&#xff1f;對此我的回答是否定的&#xff0c;因為AI雖然已經有了編寫代碼的能力&#xff0c;但它現在的水平大多還僅限于根據業務需求搭建框架&#xff0c;而具體的功能實現還尚且稚嫩&…
閱讀更多...
11.22 知識總結（cookie、 session相關知識點）

11.22 知識總結（cookie、 session相關知識點）

一、 Cookie和Session的發展史 一開始&#xff1a;只有一個頁面&#xff0c;沒有登錄功能&#xff0c;大家看到東西都一樣 新聞 時代發展&#xff0c;出現了需要登錄注冊的網站&#xff0c;要有一門技術存儲我們的登錄信息 京東、天貓 cookie 存儲形式&#xff1a;k:v鍵值對 …
閱讀更多...
【愚公系列】保姆級教程帶你實現HarmonyOS手語猜一猜元服務

【愚公系列】保姆級教程帶你實現HarmonyOS手語猜一猜元服務

&#x1f680;前言 最近HarmonyOS NEXT大火&#xff0c;這個純血鴻蒙吸引力了大家的關注。雖然現在還沒面向個人開發者開放&#xff0c;但我們可以基于最新的API9及開發工具來嘗試開發鴻蒙新的應用形態——元服務。來體驗下未來在HarmonyOS NEXT上實現的應用開發。 HarmonyOS…
閱讀更多...
什么是高防IP？有什么優勢?怎么選擇高防IP？

什么是高防IP？有什么優勢?怎么選擇高防IP？

在當今的互聯網環境中&#xff0c;分布式拒絕服務&#xff08;DDoS&#xff09;攻擊已經成為一種常見的安全威脅。這種攻擊通過向目標服務器發送大量的無效流量&#xff0c;使其無法處理正常的請求&#xff0c;從而達到迫使服務中斷的目的。作為一個用戶&#xff0c;你是否曾遇…
閱讀更多...
QGIS文章五——對遙感影像進行土地類型分類—監督分類（dzetsaka : classification tool）...

QGIS文章五——對遙感影像進行土地類型分類—監督分類（dzetsaka : classification tool）...

dzetsaka classification tool是QGIS的強大分類插件&#xff0c;目前主要提供了高斯混合模型分類器、Random Forest、KNN和SVM四種分類器模型&#xff0c;相比于SCP(Semi-Automatic Classification)&#xff0c;他的一個特點就是功能專一&#xff0c;操作簡單。 從十一月開始一…
閱讀更多...
Linux基礎命令3

Linux基礎命令3

移動&#xff0c;剪切文件 普通文件的移動剪切 現在在這兒 上圖中&#xff0c;mv y.x ./tmp的意思&#xff0c;就是將當前路徑下的y.x文件進行剪切&#xff0c;然后放到路徑為當前路徑下的tmp目錄文件夾里面 操作完成后可以cd tmp&#xff0c;ls看到y.x文件已經在里面了 現在…
閱讀更多...
facebook引流軟件需要具備什么功能

facebook引流軟件需要具備什么功能

facebook引流軟件需要具備什么功能 用戶信息批量修改&#xff1a;可批量修改已登錄用戶的頭像、密碼、個人說明等信息。小號批量刷贊、評論&#xff1a;可以批量用Facebook小號給帖子、主頁等刷贊或評論。直播帖刷人氣/評論/分享&#xff1a;可以直接刷直播帖子的人氣、評論&a…
閱讀更多...
京東內部員工，爆料工資與公積金收入！

京東內部員工，爆料工資與公積金收入！

精彩回顧&#xff1a;進了央企&#xff0c;拿了戶口&#xff0c;卻感覺被困住了。 每個企業都有它的一套規則&#xff0c;哪些人適合加薪&#xff0c;哪些人適合拿獎金&#xff0c;哪些人適合給股票期權等等。但是說實話&#xff0c;很多人都只能拿底薪&#xff0c;這些福利啥的…
閱讀更多...
數據挖掘 K近鄰

數據挖掘 K近鄰

什么時候用K近鄰&#xff1f; 交叉驗證的時候。最常見的交叉驗證方法是K折交叉驗證&#xff0c;其中數據集被均勻分成K個子集&#xff0c;稱為折&#xff0c;然后執行K次訓練和測試&#xff0c;每次選擇不同的折作為測試集&#xff0c;其余的作為訓練集。最后&#xff0c;將K次…
閱讀更多...
JavaScript編程基礎 – 對象

JavaScript編程基礎 – 對象

JavaScript編程基礎 – 對象 JavaScript Programming Essentials – Object 本文簡要介紹JavaScript面向對象編程&#xff0c;如何實現其中的對象以及實例演示&#xff0c;希望對大家學習JavaScript有所幫助。 1. 面向對象編程特點 面向對象編程(Object-Oriented Programmi…
閱讀更多...
淺談JDK動態代理(上)

淺談JDK動態代理(上)

作者簡介&#xff1a;大家好&#xff0c;我是smart哥&#xff0c;前中興通訊、美團架構師&#xff0c;現某互聯網公司CTO 聯系qq&#xff1a;184480602&#xff0c;加我進群&#xff0c;大家一起學習&#xff0c;一起進步&#xff0c;一起對抗互聯網寒冬 到目前為止&#xff0c…
閱讀更多...
Splunk 編寫高效 查詢語句

Splunk 編寫高效 查詢語句

1: 背景： splunk 的查詢語句的是否優化，對是否節省資源有很大的影響。下面說一下大概的方法： There are a set of basic principles that you can follow to optimize your searches. Retrieve only the required data Move as little data as possible Parallelize as mu…
閱讀更多...
力扣OJ題講解——循環隊列

力扣OJ題講解——循環隊列

今天我們一起來做一道關于隊列的OJ題目&#xff0c;這是力扣題目622題&#xff0c;點擊題目鏈接可以直接跳轉&#xff0c;https://leetcode.cn/problems/design-circular-queue/ 首先&#xff0c;我們看到要求&#xff0c;需要我們實現哪些功能&#xff1f; 我們需要設置隊列長…
閱讀更多...
最新文章

Copyright @ 2022~2023