紅黑樹的學習

紅黑樹的概念

紅黑樹，是一種二叉搜索樹，但在每個結點上增加一個存儲位表示結點的顏色，可以是Red或
Black。 通過對任何一條從根到葉子的路徑上各個結點著色方式的限制，紅黑樹確保沒有一條路徑會比其他路徑長出倆倍，因而是接近平衡的。

image.png

對比一下：
AVLTree ，是嚴格平衡，左右的高度差 不超過 1
紅黑樹，是近似平衡，最長路徑不會超過最短路徑的 2倍

紅黑樹的性質

  1. 每個結點不是紅色就是黑色
  2. 根節點是黑色的
  3. 如果一個節點是紅色的，則它的兩個孩子結點是黑色的

就是說，如果父節點是紅色的，他的兩個孩子也必須是紅色的，不能出現連續的紅色節點，即：父子節點的顏色只有這幾種可能：父（黑) + 子（黑），父（黑）+ 子（紅）,父（紅）+ 子（黑），

  1. 對于每個結點，從該結點到其所有后代葉子結點的簡單路徑上，均包含相同數目的黑色結點

意思就是每條路徑上都有相同數量的黑色節點

  1. 每個葉子結點都是黑色的(此處的葉子結點指的是空結點)

這里的葉子節點不是指的傳統意義上的葉子節點，而是指的空結點,也稱NIL結點，這個NIL 節點的作用是方便我們數路勁，就是數這棵樹有幾條路徑，比如下面的例子：
image.png

思考：為什么滿足上
我們來分析一下，什k面的性質，紅黑樹就能保證：其最長路徑中節點個數不會超過最短路徑節點個數的兩倍？ 🔎

我們來分析一下，什么情況下，路徑是最短的？

根據性質4每條路徑上都包含相同數目的黑色節點 , 那就說明如果一條路徑上只有黑色節點，沒有紅色節點的話，更其他那些有紅色節點的路勁相比，它就是最短的。
所以：

路勁最短 ： 只有黑色節點的情況

我們再來分析一下，什么情況下，路徑是最長的呢？

在相同黑色節點的條件下，紅色節點的個數越多，路勁就越長，根據性質3，要盡可能的增加紅色節點的個數的的話，它們之間的搭配條件要盡可能滿足：父（黑）+ 子（紅）+ 孫子（黑）+ 重孫子（紅），這樣的紅黑紅黑的交替的情況，所以最長的路徑就是最短路徑的2倍

路徑最長 ： 在黑色節點數目一定的情況下，紅色節點的數目最多

綜上所述，假設有N個黑色的節點，每條路徑的的節點的個數的范圍是[N,2N]

📌紅黑樹節點的定義

的定義：

enum Color{RED,BLACK};
// ekkkkk
kkkkk：
```c+num 是一個枚舉類型，第一個RED是第一kkkkkk'k'k'k+
enum Color{RED,BLACKk'k'k'k;
// enum 是一個枚舉類型，第一個RED是第一個枚舉值，默認是 0、
// 第二個BLACK 是第二個枚舉值，kkkkk
k'k'k'k
紅黑樹節點的定義：
```c++
template <class K, class V>
struct RBTreeNode
{RBTreeNode<K, V> *_left;RBTreeNode<K, V> *_right;RBTreeNode<K, V> *_parent;pair<K, V> _kv;Colour _col;RBTreeNode(const pair<K, V> &kv): _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}
};

🍉 上面的構造函數中，為什么默認節點的顏色要給成 紅色呢？

  1. 保持樹的黑色高度不變。
    因為紅黑數的性質4: 對于每個結點，從該結點到其所有后代葉子結點的簡單路徑上，均包含相同數目的黑色結點
  2. 減少插入時的調整操作：
    如果插入的是黑色節點，需要進行更多的調整操作來恢復紅黑樹的性質

📌紅黑樹的插入操作


template <class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;public:bool Inster(const pair<K, V> &kv){if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK; // 如果是空的，那我們要插入一個節點，這個節點的顏色是黑色，因為性質2，跟節點的顏色是黑色的。return true;}Node *parent = nullptr;Node *cur = _root;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);cur->_col = RED;if (parent->_kv.first < kv.first){parent->_kv.first < kv.first;cur->_parent = parent;}else if{parent->_left = cur;cur->parent = parent;}return true;}private:Node *_root = nullptr;
};

我們插入節點的的時候，如果插入的是一個紅色的節點，但是這個新增節點的父親是黑色的，那么插入結束，我們可以不做任何處理。

image.png
但是，如果我們插入一個紅色的節點，但是他的父親也是紅色的，這個時候該怎么處理呢？

image.png
以上的這種情況是違反規則 3 的，所以，我們必然要做的一步就是：把新增節點的父親變成黑色 節點，然后，我們在根據規則對其他節點顏色的顏色進行相應的調整以維護紅樹黑樹的性質

image.png

這么看來紅黑樹的插入操作挺麻煩的呀，那為之奈何呀？
其實也有一定的規律在里面，下面我們細細的分析

首先，我們新增一個節點，我們選擇的是新增紅色的節點，這樣對整個樹的影響會小一些

如果新增節點的父親是黑色的，那我們不需要處理。
如果新增節點的父親是紅色的，那我們需要處理，處理的方式可能是：1. 旋轉 2. 變色
有可能只變色就可以了，也有可能既要旋轉又要變色。

第一種情況：

新增節點是紅色的，新增節點的父親也是紅色的，祖父是黑色節點。并且叔叔存在而且叔叔也是紅色的；

image.png

我們的解決辦法是，
將父親節點和叔叔節點變成紅色，
祖父節點：

  1. 如果祖父節點是這棵樹的根節點，那就必須是黑色，所以保持顏色不變。
  2. 如果祖父節點也只是這棵樹的一個局部，那我們要把祖父節點變成紅色的，這樣才能保持這條路徑中黑色節點的個數不變。

image.png
但是，這樣我們忽略了一個問題：如果祖父節點的父親（曾祖父）是紅色的咋辦？如下圖：

image.png

遇到這種情況，首先，如果曾祖父是紅色的，說明曾祖父不是根節點，因為根節點一定是黑色的，所以我們要往上走，把曾祖父當成當前節點，然后繼續的看曾祖父的父節點和祖父節點，這樣循環的往上處理。

第二種情況：

當前的節點是紅色，父親節點是紅色，祖父節點是黑色，叔叔節點要么不存在，要么存在是黑色

cur : 表示當前節點
p : parent 表示父親節點
g : grandpa 表示祖父節點
u : uncle 表示叔叔節點

  1. 當前節點是紅色，父親節點是紅色，祖父節點是黑色，叔叔節點不存在：

image.png

image.png

解決方案：
parent 是 grandpa 的左孩子，cur 是parent 的左孩子，進行右單旋轉
parent 是 grandpa 的右孩子，cur 是 parent的右邊孩子，進行左單旋轉
parent 和 grandpa 變色

  1. 如果叔叔存在且為黑色：

image.png

這種情況，不止需要變色，還需要旋轉

假設每條路徑黑色節點的數量h 個，
h <= 紅黑樹中任意一條路徑長度 <= 2h
最短路徑：h
最長的路徑：2h
最長路徑和最短路徑是不一定存在的，紅黑樹是一種近似平衡

完整代碼：

RBTree.h

#pragma once
#pragma onceenum Colour
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;pair<K, V> _kv;Colour _col;RBTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}
};template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}Node* parent = nullptr;Node* cur = _root;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);cur->_col = RED;if (parent->_kv.first < kv.first){parent->_right = cur;cur->_parent = parent;}else{parent->_left = cur;cur->_parent = parent;}while (parent && parent->_col == RED){Node* grandfather = parent->_parent;if (parent == grandfather->_left){//     g//   p   u// cNode* uncle = grandfather->_right;if (uncle && uncle->_col == RED){// 變色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 繼續往上更新處理cur = grandfather;parent = cur->_parent;}else{if (cur == parent->_left){// 單旋//     g//   p// cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{// 雙旋//     g//   p//     cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else  // parent == grandfather->_right{//     g//   u   p //          c//Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){// 變色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 繼續往上處理cur = grandfather;parent = cur->_parent;}else{if (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//     g//   u   p //     c//RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;subR->_left = parent;Node* parentParent = parent->_parent;parent->_parent = subR;if (subRL)subRL->_parent = parent;if (_root == parent){_root = subR;subR->_parent = nullptr;}else{if (parentParent->_left == parent){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* parentParent = parent->_parent;subL->_right = parent;parent->_parent = subL;if (_root == parent){_root = subL;subL->_parent = nullptr;}else{if (parentParent->_left == parent){parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent;}}void InOrder(){_InOrder(_root);cout << endl;}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << " ";_InOrder(root->_right);}// 根節點->當前節點這條路徑的黑色節點的數量bool Check(Node* root, int blacknum, const int refVal){if (root == nullptr){//cout << balcknum << endl;if (blacknum != refVal){cout << "存在黑色節點數量不相等的路徑" << endl;return false;}return true;}if (root->_col == RED && root->_parent->_col == RED){cout << "有連續的紅色節點" << endl;return false;}if (root->_col == BLACK){++blacknum;}return Check(root->_left, blacknum, refVal)&& Check(root->_right, blacknum, refVal);}bool IsBalance(){if (_root == nullptr)return true;if (_root->_col == RED)return false;//參考值int refVal = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){++refVal;}cur = cur->_left;}int blacknum = 0;return Check(_root, blacknum, refVal);}private:Node* _root = nullptr;
};

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

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

相關文章

2025年01月31日Github流行趨勢

2025年01月31日Github流行趨勢

項目名稱&#xff1a;Qwen2.5項目地址url&#xff1a;https://github.com/QwenLM/Qwen2.5項目語言&#xff1a;Shell歷史star數&#xff1a;13199今日star數&#xff1a;459項目維護者&#xff1a;jklj077, JustinLin610, bug-orz, huybery, JianxinMa項目簡介&#xff1a;Qwen…
閱讀更多...
Java基礎面試題總結（題目來源JavaGuide）

Java基礎面試題總結（題目來源JavaGuide）

問題1&#xff1a;Java 中有哪 8 種基本數據類型&#xff1f;它們的默認值和占用的空間大小知道不&#xff1f; 說說這 8 種基本數據類型對 應的包裝類型。 在 Java 中&#xff0c;有 8 種基本數據類型&#xff08;Primitive Types&#xff09;&#xff1a; 基本數據類型關鍵…
閱讀更多...
人工智能|基本概念|人工智能相關重要概念---AI定義以及模型相關知識

人工智能|基本概念|人工智能相關重要概念---AI定義以及模型相關知識

一、 前言&#xff1a; 最近deepseek&#xff08;深度求索&#xff09;公司的開源自然語言處理模型非常火爆。 本人很早就對人工智能比較感興趣&#xff0c;但由于種種原因沒有過多的深入此領域&#xff0c;僅僅是做了一點初步的了解&#xff0c;借著這個deepseek&#xff0…
閱讀更多...
Python GIL（全局解釋器鎖）機制對多線程性能影響的深度分析

Python GIL（全局解釋器鎖）機制對多線程性能影響的深度分析

在Python開發領域&#xff0c;GIL&#xff08;Global Interpreter Lock&#xff09;一直是一個廣受關注的技術話題。在3.13已經默認將GIL去除&#xff0c;在詳細介紹3.13的更親前&#xff0c;我們先要留了解GIL的技術本質、其對Python程序性能的影響。本文將主要基于CPython&am…
閱讀更多...
從0開始使用面對對象C語言搭建一個基于OLED的圖形顯示框架（繪圖設備封裝）

從0開始使用面對對象C語言搭建一個基于OLED的圖形顯示框架（繪圖設備封裝）

目錄 圖像層的底層抽象——繪圖設備抽象 如何抽象一個繪圖設備&#xff1f; 橋接繪圖設備&#xff0c;特化為OLED設備 題外話&#xff1a;設備的屬性&#xff0c;與設計一個相似函數化簡的通用辦法 使用函數指針來操作設備 總結一下 圖像層的底層抽象——繪圖設備抽象 在…
閱讀更多...
Git 版本控制：基礎介紹與常用操作

Git 版本控制：基礎介紹與常用操作

目錄 Git 的基本概念 Git 安裝與配置 Git 常用命令與操作 1. 初始化本地倉庫 2. 版本控制工作流程 3. 分支管理 4. 解決沖突 5. 回退和撤銷 6. 查看提交日志 前言 在軟件開發過程中&#xff0c;開發者常常需要在現有程序的基礎上進行修改和擴展。但如果不加以管理&am…
閱讀更多...
（筆記+作業）書生大模型實戰營春節卷王班---L0G2000 Python 基礎知識

（筆記+作業）書生大模型實戰營春節卷王班---L0G2000 Python 基礎知識

學員闖關手冊&#xff1a;https://aicarrier.feishu.cn/wiki/QtJnweAW1iFl8LkoMKGcsUS9nld 課程視頻&#xff1a;https://www.bilibili.com/video/BV13U1VYmEUr/ 課程文檔&#xff1a;https://github.com/InternLM/Tutorial/tree/camp4/docs/L0/Python 關卡作業&#xff1a;htt…
閱讀更多...
仿真設計|基于51單片機的高速路口貨車稱重系統仿真

仿真設計|基于51單片機的高速路口貨車稱重系統仿真

目錄 具體實現功能 設計介紹 51單片機簡介 資料內容 仿真實現&#xff08;protues8.7&#xff09; 程序&#xff08;Keil5&#xff09; 全部內容 資料獲取 具體實現功能 &#xff08;1&#xff09;LCD1602液晶第一行顯示當前的車輛重量&#xff0c;第二行顯示車輛重量…
閱讀更多...
Ubuntu Server 安裝 XFCE4桌面

Ubuntu Server 安裝 XFCE4桌面

Ubuntu Server沒有桌面環境&#xff0c;一些軟件有桌面環境使用起來才更加方便&#xff0c;所以我嘗試安裝桌面環境。常用的桌面環境有&#xff1a;GNOME、KDE Plasma、XFCE4等。這里我選擇安裝XFCE4桌面環境&#xff0c;主要因為它是一個極輕量級的桌面環境&#xff0c;適合內…
閱讀更多...
2025：影刀RPA使用新實踐--CSDN博客下載

2025：影刀RPA使用新實踐--CSDN博客下載

文章目錄 一鍵CSDN博客下載器程序說明指導說明使用步驟 獲取方法 一鍵CSDN博客下載器 程序說明 配置信息&#xff1a;CSDN賬號&#xff08;手機號/郵箱/用戶名&#xff09;、密碼、博客文件類型支持markdown格式、html格式&#xff08;默認值markdown格式&#xff09;、博客保…
閱讀更多...
深度學習的應用

深度學習的應用

目錄 一、機器視覺 1.1 應用場景 1.2 常見的計算機視覺任務 1.2.1 圖像分類 1.2.2 目標檢測 1.2.3 圖像分割 二、自然語言處理 三、推薦系統 3.1 常用的推薦系統算法實現方案 四、圖像分類實驗補充 4.1 CIFAR-100 數據集實驗 實驗代碼 4.2 CIFAR-10 實驗代碼 深…
閱讀更多...
前端js高級25.1.30

前端js高級25.1.30

原型&#xff1a;函數的組成結構 通過這個圖我們需要知道。 假設我們創建了一個Foo函數。 規則&#xff1a;Function.protoType是函數顯示原型。__proto__是隱式對象。 Function、Object、Foo函數的__proto__指向了Function.protoType說明。這三個都依托function函數來創建。…
閱讀更多...
android 音視頻系列引導

android 音視頻系列引導

音視頻這塊的知識點自己工作中有用到&#xff0c;一直沒有好好做一個總結&#xff0c;原因有客觀和主觀的。 客觀是工作太忙&#xff0c;沒有成段時間做總結。 主觀自己懶。 趁著這次主動離職拿了n1的錢&#xff0c;休息一下&#xff0c;對自己的人生做一下總結&#xff0c;…
閱讀更多...
為AI聊天工具添加一個知識系統 之80 詳細設計之21 符號邏輯 之1

為AI聊天工具添加一個知識系統 之80 詳細設計之21 符號邏輯 之1

本文要點 要點 前面我們討論了本項目中的正則表達式。現在我們將前面討論的正則表達式視為狹義的符號文本及其符號規則rule&#xff08;認識的原則--認識上認識對象的約束&#xff09;&#xff0c;進而在更廣泛的視角下將其視為符號邏輯及其符號原則principle&#xff08;知識…
閱讀更多...
.NET Core緩存

.NET Core緩存

目錄 緩存的概念 客戶端響應緩存 cache-control 服務器端響應緩存 內存緩存&#xff08;In-memory cache&#xff09; 用法 GetOrCreateAsync 緩存過期時間策略 緩存的過期時間 解決方法&#xff1a; 兩種過期時間策略&#xff1a; 絕對過期時間 滑動過期時間 兩…
閱讀更多...
自動駕駛---蘇箐對智駕產品的思考

自動駕駛---蘇箐對智駕產品的思考

1 前言 對于更高級別的自動駕駛&#xff0c;很多人都有不同的思考&#xff0c;方案也好&#xff0c;產品也罷。最近在圈內一位知名的自動駕駛專家蘇箐發表了他自己對于自動駕駛未來的思考。 蘇箐是地平線的副總裁兼首席架構師&#xff0c;同時也是高階智能駕駛解決方案SuperDri…
閱讀更多...
Sklearn 中的邏輯回歸

Sklearn 中的邏輯回歸

邏輯回歸的數學模型 基本模型 邏輯回歸主要用于處理二分類問題。二分類問題對于模型的輸出包含 0 和 1&#xff0c;是一個不連續的值。分類問題的結果一般不能由線性函數求出。這里就需要一個特別的函數來求解&#xff0c;這里引入一個新的函數 Sigmoid 函數&#xff0c;也成…
閱讀更多...
FPGA|使用quartus II通過AS下載POF固件

FPGA|使用quartus II通過AS下載POF固件

1、將開發板設置到AS下載擋位&#xff0c;或者把下載線插入到AS端口 2、打開quartus II&#xff0c;選擇Tools→Programmer→ Mode選擇Active Serial Programming 3、點擊左側Add file…&#xff0c;選擇 .pof 文件 →start 4、勾選program和verify&#xff08;可選&#xff0…
閱讀更多...
.Net / C# 分析文件編碼 并將 各種編碼格式 轉為 另一個編碼格式 ( 比如: GB2312→UTF-8, UTF-8→GB2312)

.Net / C# 分析文件編碼 并將 各種編碼格式 轉為 另一個編碼格式 ( 比如: GB2312→UTF-8, UTF-8→GB2312)

相關庫 .Net 8 編碼識別: github.com/CharsetDetector/UTF-unknown <PackageReference Include"UTF.Unknown" Version"2.5.1" />代碼 using UtfUnknown;var dir_path "D:\\Desktop\\新建文件夾2\\新建文件夾"; var dir_new_path &quo…
閱讀更多...
32. C 語言 安全函數( _s 尾綴)

32. C 語言 安全函數( _s 尾綴)

本章目錄 前言什么是安全函數&#xff1f;安全函數的特點主要的安全函數1. 字符串操作安全函數2. 格式化輸出安全函數3. 內存操作安全函數4. 其他常用安全函數 安全函數實例示例 1&#xff1a;strcpy_s 和 strcat_s示例 2&#xff1a;memcpy_s示例 3&#xff1a;strtok_s 總結 …
閱讀更多...
最新文章

Copyright @ 2022~2023