深入理解 C++ 紅黑樹：從理論到實踐

引言

在計算機科學領域，數據結構是構建高效算法的基石。而在眾多的數據結構中，平衡二叉搜索樹因其優秀的查找、插入和刪除性能而備受關注。紅黑樹（Red-Black Tree）作為一種自平衡的二叉搜索樹，更是在 C++ 標準庫（如 STL 中的 map 和 set）中得到了廣泛應用。本文將深入探討紅黑樹的原理、實現及應用，幫助讀者全面掌握這一重要的數據結構。

紅黑樹的基本概念

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

紅黑樹必須滿足以下五個性質：

  1. 每個節點要么是紅色，要么是黑色。
  2. 根節點是黑色。
  3. 每個葉子節點（NIL 節點，空節點）是黑色的。
  4. 如果一個節點是紅色的，則它的兩個子節點都是黑色的。
  5. 對每個節點，從該節點到其所有后代葉節點的簡單路徑上，均包含相同數目的黑色節點。

這些性質的約束使得紅黑樹的高度始終保持在 O (log n)，從而保證了基本操作的高效性。

紅黑樹的操作

紅黑樹的基本操作包括插入、刪除和查找。由于紅黑樹是二叉搜索樹的一種，其查找操作與普通二叉搜索樹相同，但插入和刪除操作后需要通過旋轉和變色來維持紅黑樹的性質。

插入操作

插入操作首先按照二叉搜索樹的方式插入新節點，并將其著色為紅色。然后通過一系列的旋轉和顏色調整來修復紅黑樹的性質。插入操作的時間復雜度為 O (log n)。

插入修復主要分為三種情況：

  1. 情況 1：插入節點的父節點是紅色，且叔叔節點（父節點的兄弟節點）也是紅色。此時將父節點和叔叔節點變為黑色，祖父節點變為紅色，然后繼續處理祖父節點。
  2. 情況 2：插入節點的父節點是紅色，叔叔節點是黑色，且插入節點是父節點的右孩子。此時進行左旋操作，將問題轉化為情況 3。
  3. 情況 3：插入節點的父節點是紅色，叔叔節點是黑色，且插入節點是父節點的左孩子。此時將父節點變為黑色，祖父節點變為紅色，然后進行右旋操作。
刪除操作

刪除操作同樣首先按照二叉搜索樹的方式刪除節點，然后通過旋轉和變色來修復紅黑樹的性質。刪除操作的時間復雜度也為 O (log n)。

刪除修復比插入修復更為復雜，主要分為四種情況，需要考慮兄弟節點的顏色以及兄弟節點子節點的顏色。

紅黑樹的 C++ 實現

下面是紅黑樹的 C++ 實現代碼，包括節點結構、插入、刪除、查找等基本操作：

#include "red_black_tree.hpp"
#include <iostream>
#include <cassert>int main() {RedBlackTree<int> tree;// 測試插入操作tree.insert(10);tree.insert(20);tree.insert(5);tree.insert(15);tree.insert(30);std::cout << "Inorder traversal after insertion: ";tree.inorder(); // 應輸出 5 10 15 20 30// 測試查找操作assert(tree.contains(15) == true);assert(tree.contains(25) == false);std::cout << "Contains test passed." << std::endl;// 測試刪除操作tree.remove(20);std::cout << "Inorder traversal after deleting 20: ";tree.inorder(); // 應輸出 5 10 15 30assert(tree.contains(20) == false);// 測試大小assert(tree.size() == 4);std::cout << "Size after deletion: " << tree.size() << std::endl;// 測試空樹RedBlackTree<int> emptyTree;assert(emptyTree.empty() == true);std::cout << "Empty tree test passed." << std::endl;std::cout << "All tests passed!" << std::endl;return 0;
}    
#ifndef RED_BLACK_TREE_HPP
#define RED_BLACK_TREE_HPP#include <iostream>
#include <memory>
#include <functional>
#include <cassert>template<typename T, typename Compare = std::less<T>>
class RedBlackTree {
private:enum class Color { RED, BLACK };struct Node {T data;Color color;std::unique_ptr<Node> left;std::unique_ptr<Node> right;Node* parent;Node(const T& value, Color nodeColor = Color::RED): data(value), color(nodeColor), left(nullptr), right(nullptr), parent(nullptr) {}};std::unique_ptr<Node> root;Compare compare;size_t treeSize;// 左旋操作void leftRotate(Node* x) {Node* y = x->right.get();x->right = std::move(y->left);if (y->left) {y->left->parent = x;}y->parent = x->parent;if (!x->parent) {root = std::unique_ptr<Node>(y);} else if (x == x->parent->left.get()) {x->parent->left = std::unique_ptr<Node>(y);} else {x->parent->right = std::unique_ptr<Node>(y);}y->left = std::move(x->right);x->parent = y;}// 右旋操作void rightRotate(Node* y) {Node* x = y->left.get();y->left = std::move(x->right);if (x->right) {x->right->parent = y;}x->parent = y->parent;if (!y->parent) {root = std::unique_ptr<Node>(x);} else if (y == y->parent->right.get()) {y->parent->right = std::unique_ptr<Node>(x);} else {y->parent->left = std::unique_ptr<Node>(x);}x->right = std::move(y->left);y->parent = x;}// 插入修復void insertFixup(Node* z) {while (z->parent && z->parent->color == Color::RED) {if (z->parent == z->parent->parent->left.get()) {Node* y = z->parent->parent->right.get();if (y && y->color == Color::RED) {z->parent->color = Color::BLACK;y->color = Color::BLACK;z->parent->parent->color = Color::RED;z = z->parent->parent;} else {if (z == z->parent->right.get()) {z = z->parent;leftRotate(z);}z->parent->color = Color::BLACK;z->parent->parent->color = Color::RED;rightRotate(z->parent->parent);}} else {Node* y = z->parent->parent->left.get();if (y && y->color == Color::RED) {z->parent->color = Color::BLACK;y->color = Color::BLACK;z->parent->parent->color = Color::RED;z = z->parent->parent;} else {if (z == z->parent->left.get()) {z = z->parent;rightRotate(z);}z->parent->color = Color::BLACK;z->parent->parent->color = Color::RED;leftRotate(z->parent->parent);}}}root->color = Color::BLACK;}// 查找最小節點Node* minimum(Node* node) const {while (node->left) {node = node->left.get();}return node;}// 查找最大節點Node* maximum(Node* node) const {while (node->right) {node = node->right.get();}return node;}// 查找后繼節點Node* successor(Node* node) const {if (node->right) {return minimum(node->right.get());}Node* y = node->parent;while (y && node == y->right.get()) {node = y;y = y->parent;}return y;}// 查找前驅節點Node* predecessor(Node* node) const {if (node->left) {return maximum(node->left.get());}Node* y = node->parent;while (y && node == y->left.get()) {node = y;y = y->parent;}return y;}// 刪除修復void deleteFixup(Node* x, Node* parent) {while (x != root.get() && (x == nullptr || x->color == Color::BLACK)) {if (x == parent->left.get()) {Node* w = parent->right.get();if (w->color == Color::RED) {w->color = Color::BLACK;parent->color = Color::RED;leftRotate(parent);w = parent->right.get();}if ((w->left == nullptr || w->left->color == Color::BLACK) &&(w->right == nullptr || w->right->color == Color::BLACK)) {w->color = Color::RED;x = parent;parent = x->parent;} else {if (w->right == nullptr || w->right->color == Color::BLACK) {if (w->left) w->left->color = Color::BLACK;w->color = Color::RED;rightRotate(w);w = parent->right.get();}w->color = parent->color;parent->color = Color::BLACK;if (w->right) w->right->color = Color::BLACK;leftRotate(parent);x = root.get();parent = nullptr;}} else {Node* w = parent->left.get();if (w->color == Color::RED) {w->color = Color::BLACK;parent->color = Color::RED;rightRotate(parent);w = parent->left.get();}if ((w->right == nullptr || w->right->color == Color::BLACK) &&(w->left == nullptr || w->left->color == Color::BLACK)) {w->color = Color::RED;x = parent;parent = x->parent;} else {if (w->left == nullptr || w->left->color == Color::BLACK) {if (w->right) w->right->color = Color::BLACK;w->color = Color::RED;leftRotate(w);w = parent->left.get();}w->color = parent->color;parent->color = Color::BLACK;if (w->left) w->left->color = Color::BLACK;rightRotate(parent);x = root.get();parent = nullptr;}}}if (x) x->color = Color::BLACK;}// 中序遍歷輔助函數void inorderTraversal(Node* node) const {if (node) {inorderTraversal(node->left.get());std::cout << node->data << " ";inorderTraversal(node->right.get());}}// 查找節點輔助函數Node* findNode(const T& value) const {Node* current = root.get();while (current) {if (compare(value, current->data)) {current = current->left.get();} else if (compare(current->data, value)) {current = current->right.get();} else {return current;}}return nullptr;}public:RedBlackTree() : root(nullptr), compare(), treeSize(0) {}// 插入操作void insert(const T& value) {Node* z = new Node(value);Node* y = nullptr;Node* x = root.get();while (x) {y = x;if (compare(z->data, x->data)) {x = x->left.get();} else {x = x->right.get();}}z->parent = y;if (!y) {root = std::unique_ptr<Node>(z);} else if (compare(z->data, y->data)) {y->left = std::unique_ptr<Node>(z);} else {y->right = std::unique_ptr<Node>(z);}z->color = Color::RED;insertFixup(z);treeSize++;}// 刪除操作bool remove(const T& value) {Node* z = findNode(value);if (!z) return false;Node* y = z;Node* x;Color yOriginalColor = y->color;if (!z->left) {x = z->right.get();transplant(z, std::move(z->right));} else if (!z->right) {x = z->left.get();transplant(z, std::move(z->left));} else {y = minimum(z->right.get());yOriginalColor = y->color;x = y->right.get();if (y->parent == z) {if (x) x->parent = y;} else {transplant(y, std::move(y->right));y->right = std::move(z->right);y->right->parent = y;}transplant(z, std::move(std::unique_ptr<Node>(y)));y->left = std::move(z->left);y->left->parent = y;y->color = z->color;}if (yOriginalColor == Color::BLACK) {deleteFixup(x, y->parent);}treeSize--;return true;}// 查找操作bool contains(const T& value) const {return findNode(value) != nullptr;}// 獲取元素數量size_t size() const {return treeSize;}// 判斷是否為空bool empty() const {return treeSize == 0;}// 中序遍歷void inorder() const {inorderTraversal(root.get());std::cout << std::endl;}// 移植輔助函數void transplant(Node* u, std::unique_ptr<Node> v) {Node* uParent = u->parent;if (!uParent) {root = std::move(v);} else if (u == uParent->left.get()) {uParent->left = std::move(v);} else {uParent->right = std::move(v);}if (v) {v->parent = uParent;}}
};#endif // RED_BLACK_TREE_HPP

這段代碼實現了一個模板類 RedBlackTree，包含了紅黑樹的基本操作。代碼中使用了智能指針管理內存，確保內存安全。同時，通過插入修復和刪除修復函數來維護紅黑樹的性質。

紅黑樹的應用

紅黑樹在計算機科學中有廣泛的應用，主要包括：

  1. C++ 標準庫：STL 中的 map 和 set 就是基于紅黑樹實現的，保證了元素的有序性和高效的插入、刪除、查找操作。
  2. 操作系統：Linux 內核中的完全公平調度器（CFS）使用紅黑樹來管理進程調度。
  3. 數據庫系統：許多數據庫系統使用紅黑樹來索引數據，提高查詢效率。
  4. 其他應用：如 Java 的 TreeMap 和 TreeSet、Python 的 SortedContainers 等。
紅黑樹與其他數據結構的比較

紅黑樹與其他平衡二叉搜索樹（如 AVL 樹、B 樹等）相比，具有以下特點：

  1. 與 AVL 樹相比：紅黑樹的平衡性要求不如 AVL 樹嚴格，因此插入和刪除操作的旋轉次數更少，但查找操作的效率略低。
  2. 與 B 樹相比：紅黑樹是二叉樹，而 B 樹是多叉樹，更適合存儲在磁盤等外部存儲設備上。
  3. 與哈希表相比：紅黑樹可以保證元素的有序性，而哈希表不能，但哈希表的平均查找時間復雜度為 O (1)，比紅黑樹更快。
總結

紅黑樹作為一種重要的數據結構，憑借其良好的平衡性和高效的操作性能，在計算機科學領域得到了廣泛應用。通過本文的介紹，讀者應該對紅黑樹的原理、實現和應用有了全面的了解。掌握紅黑樹不僅有助于理解各種高級算法和數據結構，也能在實際編程中發揮重要作用。

希望本文對您理解 C++ 紅黑樹有所幫助！
?

附：恩師博客hnjzsyjyj-CSDN博客

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

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

相關文章

外星人筆記本裝win11哪個版本好_外星人筆記本裝win11專業版教程

外星人筆記本裝win11哪個版本好_外星人筆記本裝win11專業版教程

外星人筆記本安裝win11哪個版本好&#xff1f;答&#xff1a;外星人筆記本還是建議安裝win11專業版。Win分為多個版本&#xff0c;其中家庭版&#xff08;Home&#xff09;和專業版&#xff08;Pro&#xff09;是用戶選擇最多的兩個版本。win11專業版在功能以及安全性方面有著明…
閱讀更多...
自學嵌入式 day37 HTML

自學嵌入式 day37 HTML

HTML:超文本標記語言HyperText Markup Language一種用于創建網頁的標準標記語言HTML 運行在瀏覽器上&#xff0c;由瀏覽器來解析。https://www.runoob.com/html/html-tutorial.html1.格式 <!DOCTYPE html> <html><head><meta charset"utf-8"&g…
閱讀更多...
【車聯網kafka】Kafka核心架構與實戰經驗（第一篇）

【車聯網kafka】Kafka核心架構與實戰經驗（第一篇）

目錄 一、我與kafka的緣分-初識Kafka 二、Kafka深入探討-了解kafka ?編輯2.1 kafka 生產者框架 2.1.1 生產者在生活中的實例 2.1.2 kafka生產者流程及框架 1. 主線程處理階段 2. Sender線程處理階段 設計優勢總結 2.2 kafka 生產者框架中的一些關鍵參數 2.3 kafka 生…
閱讀更多...
Go 語言變量作用域

Go 語言變量作用域

Go 語言變量作用域 引言 在編程語言中&#xff0c;變量作用域是定義變量可以使用和不可使用的區域。在Go語言中&#xff0c;理解變量的作用域對于編寫高效且易于維護的代碼至關重要。本文將詳細介紹Go語言中的變量作用域&#xff0c;包括其規則、類型以及實際應用。 一、變量作…
閱讀更多...
單卡10分鐘部署MiniCPM4-0.5B：輕量級大模型本地運行指南

單卡10分鐘部署MiniCPM4-0.5B：輕量級大模型本地運行指南

一、介紹 MiniCPM 4 是一個極其高效的邊緣側大型模型&#xff0c;經過了模型架構、學習算法、訓練數據和推理系統四個維度的高效優化&#xff0c;實現了極致的效率提升。 &#x1f3d7;? 高效的模型架構&#xff1a; InfLLM v2 – 可訓練的稀疏注意力機制&#xff1a;采用可…
閱讀更多...
CSS變量與Houdini自定義屬性：解鎖樣式編程新維度

CSS變量與Houdini自定義屬性：解鎖樣式編程新維度

在前端開發中&#xff0c;CSS變量和Houdini自定義屬性正在徹底改變我們編寫和管理樣式的方式。這些技術不僅提高了樣式代碼的可維護性&#xff0c;更為CSS帶來了編程語言的強大能力。一、CSS變量&#xff1a;原生樣式的革命 CSS變量&#xff08;CSS Custom Properties&#xff…
閱讀更多...
Android中PID與UID的區別和聯系(2)

Android中PID與UID的區別和聯系(2)

一、核心概念對比特性PID (Process ID)UID (User ID)本質進程唯一標識符應用身份標識符分配時機進程啟動時動態分配應用安裝時靜態分配生命周期進程結束時回收應用卸載時才回收變化性每次啟動都可能不同長期保持不變作用范圍單進程內唯一全設備范圍唯一核心作用系統資源管理&am…
閱讀更多...
TCPDump實戰手冊：協議/端口/IP過濾與組合分析指南

TCPDump實戰手冊：協議/端口/IP過濾與組合分析指南

目錄 一、基礎過濾速查表 1. 協議過濾&#xff08;單協議&#xff09; 2. 端口過濾 3. IP地址過濾 二、組合過濾實戰示例 1. 協議端口組合 2. IP端口組合 3. 復雜邏輯組合 三、高級協議分析示例 1. HTTP請求分析 2. DNS問題排查 3. TCP連接問題分析 四、組合過濾場…
閱讀更多...
【智能協同云圖庫】智能協同云圖庫第八彈：基于阿里云百煉大模型—實現 AI 擴圖功能

【智能協同云圖庫】智能協同云圖庫第八彈：基于阿里云百煉大模型—實現 AI 擴圖功能

AI 擴圖功能 需求分析 隨著 AI 的高速發展&#xff0c;AI 幾乎可以應用到任何傳統業務中&#xff0c;增強應用的功能&#xff0c;帶給用戶更好的體驗。 對于圖庫網站來說&#xff0c;AI 也有非常多的應用空間&#xff0c;比如可以利用 AI 繪圖大模型來編輯圖片&#xff0c;實現…
閱讀更多...
2025年Solar應急響應公益月賽-7月筆記ing

2025年Solar應急響應公益月賽-7月筆記ing

應急響應身為顏狗的我是真心覺得lovelymem的ui寫得~~~~【任務1】應急大師題目描述&#xff1a;請提交隱藏用戶的名稱&#xff1f;print打印注冊表&#xff0c;或者開啟環境是就有【任務4】應急大師題目描述&#xff1a;請提交黑客創建隱藏用戶的TargetSid&#xff08;目標賬戶安…
閱讀更多...
C++/CLI vs 標準 C++ vs C# 語法對照手冊

C++/CLI vs 標準 C++ vs C# 語法對照手冊

&#x1f680; C/CLI vs 標準 C vs C# 語法對照手冊&#x1f9e9; 核心類型系統對比 // 類型聲明語法對比 標準 C C/CLI C# ─────────────────────────────────────────────────…
閱讀更多...
倉庫管理系統-2-后端之基于繼承基類的方式實現增刪改查

倉庫管理系統-2-后端之基于繼承基類的方式實現增刪改查

文章目錄 1 數據庫表user 2 后端通用框架 2.1 User.java(實體類) 2.2 使用封裝的方法(繼承基類) 2.2.1 UserMapper.java(mapper接口) 2.2.2 UserService.java(service接口) 2.2.3 UserServiceImpl.java(service實現類) 2.2.4 UserController.java(控制器) 3 增刪改查(封裝的方法…
閱讀更多...
【el-table滾動事件】el-table表格滾動時，獲取可視窗口內的行數據

【el-table滾動事件】el-table表格滾動時，獲取可視窗口內的行數據

一個簡單的獲取內容的辦法 表格部分&#xff0c;主要是ref寫一下<el-table :data"tableData" ref"tableRef"> </el-table>進入頁面的時候綁定監聽 mounted(){ // 綁定滾動事件this.$nextTick(() > {const table this.$refs.tableRef;const…
閱讀更多...
OCR 賦能自動閱卷：讓評分更高效精準

OCR 賦能自動閱卷：讓評分更高效精準

考試閱卷中&#xff0c;OCR 技術正成為高效助手&#xff0c;尤其在客觀題和標準化答題場景中表現亮眼。將考生答題卡掃描后&#xff0c;OCR 能快速識別填涂的選項、手寫數字或特定符號&#xff0c;與標準答案比對后自動判分。相比人工閱卷&#xff0c;它能在短時間內完成成百上…
閱讀更多...
在docker中安裝frp實現內網穿透

在docker中安裝frp實現內網穿透

服務端frps 1.首先在服務器端安裝frps docker pull snowdreamtech/frps2.本地創建frps的配置文件frps.ini [common] bind_port 7000 # frp 服務端控制端口 token xxxxx # 客戶端認證密鑰3.啟動frps docker run -d --name frps \ --network host \ --restartalwa…
閱讀更多...
電腦開機后網絡連接慢？

電腦開機后網絡連接慢？

在數字化日益普及的今天&#xff0c;電腦已成為我們工作和生活中不可或缺的工具。但是&#xff0c;可能很多用戶都遇到過電腦開機后網絡連接慢的情況&#xff0c;這不僅影響了我們的工作效率&#xff0c;還極大降低了上網體驗。怎么解決該問題呢&#xff1f;本文分享的這5個方法…
閱讀更多...
一分鐘部署一個導航網站

一分鐘部署一個導航網站

先看效果1.部署教程 mkdir -p /home/ascendking/mysite cd /home/ascendking/mysite# 安裝 WebStack-Hugo 主題git clone https://gitee.com/WangZhe168_admin/WebStack-Hugo.git themes/WebStack-Hugo# 將 exampleSite 目錄下的文件復制到 hugo 站點根目錄 cd /home/ascendki…
閱讀更多...
Rust實現微積分與高等數學公式

Rust實現微積分與高等數學公式

基于Rust實現高等數學中微積分 以下是基于Rust實現高等數學中微積分相關公式的示例整理，涵蓋微分、積分、級數等常見計算場景。內容分為基礎公式和進階應用兩類，提供可直接運行的Rust代碼片段（需依賴num或nalgebra等庫）。 微分運算 導數的數值近似（前向差分） 適用于函…
閱讀更多...
Android 鍵盤

Android 鍵盤

基礎知識1. 物理鍵盤&#xff08;Physical Keyboard&#xff09;定義物理鍵盤指的是設備上真實存在的、可以按壓的鍵盤。例如&#xff1a;早期的 Android 手機&#xff08;如黑莓、摩托羅拉 Milestone&#xff09;自帶的 QWERTY 鍵盤外接的藍牙/USB 鍵盤平板或 Chromebook 上的…
閱讀更多...
SuperClaude Framework 使用指南

SuperClaude Framework 使用指南

SuperClaude Framework 使用指南SuperClaude Framework 是一個開源配置框架&#xff0c;將 Claude Code 從通用 AI 助手轉變為專業的上下文感知開發伙伴。該框架通過模板驅動架構應用軟件工程原理&#xff0c;為專業軟件開發工作流程提供了強大的增強功能。目前該項目處于 v3.0…
閱讀更多...
最新文章

Copyright @ 2022~2023