📝個人主頁🌹：Eternity._
?收錄專欄?：C++ “ 登神長階 ”
🤡往期回顧🤡：了解 紅黑樹
🌹🌹期待您的關注 🌹🌹

---

前言： 在編程的浩瀚宇宙中，數據結構作為構建程序的基石，扮演著至關重要的角色。它們不僅定義了數據的存儲方式，還極大地影響著程序的性能與效率。在眾多經典數據結構中，Map（映射）和Set（集合）以其獨特的性質和廣泛的應用場景，成為了程序員們手中不可或缺的工具。Map允許我們根據鍵（Key）快速檢索值（Value），而Set則提供了一種不包含重復元素的數據集合

深入理解并熟練掌握這些高級數據結構，并非一蹴而就。為了更加深刻地認識Map與Set的工作原理，以及它們背后隱藏的算法智慧，一個行之有效的方法便是親手模擬實現它們。這一過程，不僅能夠幫助我們加深對數據結構的理解，還能在實踐中鍛煉編程能力和問題解決能力

本文旨在為讀者提供一個全面而深入的視角，通過逐步解析紅黑樹的基本原理、詳細闡述模擬實現的過程，并輔以豐富的代碼示例，幫助讀者掌握紅黑樹Map與Set的構建與使用。我們將從最基本的二叉搜索樹出發，逐步引入紅黑樹的特性和規則

讓我們一起踏上學習的旅程，探索它帶來的無盡可能！

---

📒1. 改造紅黑樹

改造紅黑樹以適配map和set容器，主要涉及到如何根據這兩種容器的特性來設計和實現紅黑樹節點的存儲以及相應的操作。map和set的主要區別在于它們存儲的元素類型：map存儲鍵值對（key-value pairs），而set僅存儲唯一的鍵值（通常是鍵本身作為值）。盡管如此，它們在底層數據結構（如紅黑樹）的實現上有很多相似之處

改造內容：

• K：key的類型
• T：如果是map，則為pair<K, V>; 如果是set，則為K
• KeyOfT：通過T來獲取key的一個仿函數類

// Map 與 Set
// set -> RBTree<K, K, SetKeyOfT> _t;
// map -> RBTree<K, pair<const K, V, MapKeyOfT>> _t;

---

紅黑樹的節點設計：

enum Color
{RED,BLACK
};template<class T>
struct RBTreeNode
{RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;// pair<K, V> _kv; // 上節內容使用的這種方式T _data;Color _col;RBTreeNode(const T& data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED){}
};

---

紅黑樹類的實現參考上一篇文章：紅黑樹類的實現
與紅黑樹類的不同的是Insert(插入)的類型是pair<iterator, bool>或者pair<Node*, bool>，然后還要修改內部的return返回的對象

以pair<Node*, bool>為例
代碼示例：

pair<Node*, bool> Insert(const T& data){if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return make_pair(_root, true);}Node* parent = nullptr;Node* cur = _root;// 通過仿函數KeyOfT來比較數據的大小KeyOfT kot;while (cur){parent = cur;if (kot(cur->_data) < kot(data)){cur = cur->_right;}else if (kot(cur->_data) > kot(data)){cur = cur->_left;}else{return make_pair(cur, false);}}// 新增節點給紅色cur = new Node(data);// 注意，這里需要保存一個新增節點，以便用來返回Node* newnode = cur;cur->_col = RED;// 旋轉變色return make_pair(newnode, true);;}

對于set，你可以簡單地使用RBTree<K, K, SetKeyOfT>；而對于map，則使用RBTree<K, pair<const K, V>, MapKeyOfT>

---

📜2. 紅黑樹的迭代器

🌞迭代器基本設計

// 通過模板來達到const的迭代器的復用
template<class T, class Ref, class Ptr>
struct __TreeIterator
{typedef RBTreeNode<T> Node;typedef __TreeIterator<T, Ref, Ptr> Self;Node* _node;// 構造函數__TreeIterator(Node* node):_node(node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &(_node->_data);}bool operator!=(const Self& s){return _node != s._node;}
};

---

🌙begin()與end()

STL明確規定，begin()與end()代表的是一段前閉后開的區間，而對紅黑樹進行中序遍歷后，
可以得到一個有序的序列，因此：begin()可以放在紅黑樹中最小節點(即最左側節點)的位
置，end()放在最大節點(最右側節點)的下一個位置，關鍵是最大節點的下一個位置在哪塊？
能否給成nullptr呢？答案是行不通的，因為對end()位置的迭代器進行–操作，必須要能找最
后一個元素，此處就不行，因此最好的方式是將end()放在頭結點的位置

代碼示例(C++)：
(注意：此步需要在RBTree類的內部實現)，以便map,set的使用

typedef __TreeIterator<T, T&, T*> iterator;
typedef __TreeIterator<T, const T&, const T*> const_iterator;iterator begin()
{Node* cur = _root;while (cur && cur->_left){cur = cur->_left;}return iterator(cur);
}iterator end()
{return iterator(nullptr);
}const_iterator begin() const
{Node* cur = _root;while (cur && cur->_left){cur = cur->_left;}return const_iterator(cur);
}const_iterator end() const
{return const_iterator(nullptr);
}

---

?operator++()與operator–()

operator++()

• 右不為空，右子樹的最左節點
• 右為空，沿著到根的路徑找孩子是父親左的那個祖先

operator–()

• 左不為空，左子樹的最右節點
• 左為空，沿著到根的路徑找孩子是父親右的那個祖先

注意：++和–正好是完全相反的

---

代碼示例(C++)：

Self& operator++()
{if (_node->_right){Node* cur = _node->_right;while (cur->_left){cur = cur->_left;}_node = cur;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = cur->_parent;}_node = parent;}return *this;
}Self& operator--()
{if (_node->_left){Node* cur = _node->_left;while (cur->_right){cur = cur->_right;}_node = cur;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent&& cur == parent->_left){cur = parent;parent = cur->_parent;}_node = parent;}return *this;
}

---

📚3. Set的模擬實現

🧩Set的基本設計

template<class K>
class set
{
public:// SetKeyOfT：通過T來獲取key的一個仿函數類struct SetKeyOfT{const K& operator()(const K& key){return key;}};// typename告訴編譯器這是類型，// 因為set不能夠進行修改，所以我們用const迭代器來初始化普通迭代器，來達到不能修改的目的typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;iterator begin() const{return _t.begin();}iterator end() const{return _t.end();}// 復用RBTree中的插入pair<iterator, bool> insert(const K& key){return _t.Insert(key);}private:RBTree<K, K, SetKeyOfT> _t;
};

---

📝4. Map的模擬實現

🧩Map的基本設計

template<class K, class V>
class map
{
public:// MapKeyOfT：通過pair來獲取kv.first的一個仿函數類struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};// map是一個key不能修改，value能夠修改的結構typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator const_iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}// 重載map中的operatorp[]// operatorp[] 當原數據中沒有時，插入并初始化，有則修改secondV& operator[](const K& key){// 沒有是插入，有則是查找pair<iterator, bool> ret = insert(make_pair(key, V()));return ret.first->second;}// 復用RBTree中的插入pair<iterator, bool> insert(const pair<K, V>& kv){return _t.Insert(kv);}private:RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};

---

📖5. 總結

隨著我們對紅黑樹Map與Set的深入探索與模擬實現，這場高效數據存儲的旅程也即將畫上圓滿的句號。回望這段旅程，我們從紅黑樹的基本概念出發，逐步揭示了其保持平衡、實現高效操作的秘密，并通過親手編寫代碼，將理論轉化為了實踐

同時，我們也要意識到，數據結構的選擇并非一成不變。在實際應用中，我們需要根據具體需求、數據規模、性能要求等因素綜合考慮，選擇最合適的數據結構來解決問題。只有這樣，我們才能真正做到高效、穩定地處理數據。

然而，學習之路永無止境。紅黑樹只是眾多高效數據結構中的一種，它們各自有著獨特的優勢和適用場景。在未來的學習與實踐中，我們還需要繼續探索其他數據結構，如AVL樹、B樹、B+樹等，以拓寬我們的視野，提升我們的技能

希望各位在未來的學習與工作中，保持對知識的渴望與追求，勇于挑戰自我，不斷探索未知領域。相信在不久的將來，你們定能在數據處理的廣闊舞臺上大放異彩！

希望本文能夠為你提供有益的參考和啟示，讓我們一起在編程的道路上不斷前行！
謝謝大家支持本篇到這里就結束了，祝大家天天開心！