紅黑樹(shù)的迭代器

//紅黑樹(shù)的迭代器 template<class T> struct RBTreeIterator {typedef RBTreeNode<T>Node;typedef RBTreeIterator<T> Self; public:RBTreeIterator(Node* pNode = nullptr):_pNode(pNode){}//具有指針操作T& operator*(){return _pNode->_data;//找值}T* operator->(){return &(operator*());}//可以移動(dòng)Self& operator++(){Increament();return *this;}Self operator++(int){Self temp(*this);Increament(); //往后走一步return temp;}Self& operator--(){DeIncreament();return *this;}Self operator--(int){Self temp(*this);DeIncreament();return temp;}bool operator==(const Self& s)const{return _pNode == s._pNode;}bool operator!=(const Self& s)const{return _pNode != s._pNode;} private:void Increament(){if (_pNode->_pRight) //右子樹(shù)存在{_pNode = _pNode->_pRight;while (_pNode->_pLeft)_pNode = _pNode->_pLeft;}else{//比_pNode大的元素可能在它的雙親中Node* pParent = _pNode->_pParent;while (_pNode == pParent->_pRight){_pNode = pParent;pParent = _pNode->_pParent;}//根結(jié)點(diǎn)沒(méi)有右子樹(shù)&&迭代器在根結(jié)點(diǎn)的位置if (_pNode->_pRight!=pParent)_pNode = pParent; //把pNode放到雙親的位置}}void DeIncreament(){if (_pNode->_pParent->_pParent == _pNode&& RED == _pNode->_color){_pNode = _pNode->_pRight;}else if (_pNode->_pLeft){//如果左子樹(shù)存在，應(yīng)該在左子樹(shù)中找最大的結(jié)點(diǎn)_pNode = _pNode->_pLeft;while (_pNode->_pRight)_pNode = _pNode->_pRight;}else{//向上找Node* pParent = _pNode->_pParent;while (_pNode == pParent->_pLeft){_pNode = pParent;pParent = _pNode->_pParent;}//begin不可能再減_pNode = pParent;}} private:Node* _pNode; };

紅黑樹(shù)的改造

template<class T,class KOFV> class RBTree {typedef RBTreeNode<T> Node; public:typedef RBTreeIterator<T> iterator;public:RBTree():_size(0){_pHead = new Node;_pHead->_pLeft = _pHead;_pHead->_pRight = _pHead;//構(gòu)造里已經(jīng)將雙親給成空}iterator begin(){return iterator(_pHead->_pLeft);}iterator end(){return iterator(_pHead);}pair<iterator,bool> Insert(const T&data){Node*& pRoot = GetRoot(); //必須以引用的方式進(jìn)行接受Node* pNewNode = nullptr;if (nullptr == pRoot) //樹(shù)為空,創(chuàng)建根結(jié)點(diǎn){pNewNode = pRoot = new Node(data, BLACK);pRoot->_pParent = _pHead;//只有一個(gè)結(jié)點(diǎn)，head就是根節(jié)點(diǎn)的雙親}else{//說(shuō)明樹(shù)已經(jīng)不為空了//1.按照二叉搜索樹(shù)的性質(zhì)找到帶插入結(jié)點(diǎn)在紅黑樹(shù)的位置Node* pCur = pRoot;Node* pParent = nullptr;while (pCur){pParent = pCur;//標(biāo)記雙親位置if (KOFV()(data) < KOFV()(pCur->_data))pCur = pCur->_pLeft;else if (KOFV()(data) > KOFV()(pCur->_data))pCur = pCur->_pRight;else//相同不插入return make_pair(iterator(pCur),false);}//2. 插入新結(jié)點(diǎn)pNewNode = pCur = new Node(data);if (KOFV()(data) < KOFV()(pParent->_data))pParent->_pLeft = pCur;elsepParent->_pRight = pCur;//3. 更新雙親位置pCur->_pParent = pParent;//以上沒(méi)錯(cuò)//4.檢測(cè):是否新結(jié)點(diǎn)插入后連在一起的紅色結(jié)點(diǎn)while (pParent != _pHead && RED == pParent->_color){Node* granderFather = pParent->_pParent;if (pParent == granderFather->_pLeft){//叔叔結(jié)點(diǎn)在右側(cè)Node* uncle = granderFather->_pRight;//情況一:叔叔結(jié)點(diǎn)存在，且為紅if (uncle && RED == uncle->_color){pParent->_color = BLACK;uncle->_color = BLACK;granderFather->_color = RED;pCur = granderFather;pParent = pCur->_pParent;}//以上沒(méi)問(wèn)題else{//情況三if (pCur == pParent->_pRight) //情況三{//轉(zhuǎn)變成情況二RotateLeft(pParent);swap(pParent, pCur);}//情況二pParent->_color = BLACK;granderFather->_color = RED;RotateRight(granderFather);}//以上沒(méi)問(wèn)題}else{//叔叔結(jié)點(diǎn)在左側(cè)Node* uncle = granderFather->_pLeft;//情況一的反情況if (uncle && uncle->_color == RED){pParent->_color = BLACK;uncle->_color = BLACK;granderFather->_color = RED;pCur = granderFather;pParent = pCur->_pParent;}//以上沒(méi)問(wèn)題else{//情況三的反情況if (pCur == pParent->_pLeft) /**/{//情況三的反情況變成情況二的反情況RotateRight(pParent);swap(pParent, pCur);}//情況二反情況處理pParent->_color = BLACK;granderFather->_color = RED;RotateLeft(granderFather);}//以上沒(méi)問(wèn)題}}}//5.調(diào)整頭結(jié)點(diǎn)的左右指針域//保證根節(jié)點(diǎn)是黑色++_size;pRoot->_color = BLACK;_pHead->_pLeft = LeftMost();_pHead->_pRight = RightMost();return make_pair(iterator(pNewNode), true);}iterator Find(const T& data)const{Node* pCur = _pHead->_pParent;while (pCur){if (KOFV()(data) == KOFV()(pCur->_data))return iterator(pCur);else if (KOFV()(data) < KOFV()(pCur->_data))pCur = pCur->_pLeft;elsepCur = pCur->_pRight;}return end();}void InOrder(){_InOrder(GetRoot());}//檢測(cè)紅黑樹(shù)bool IsValidRBTree(){Node* pRoot = GetRoot();if (nullptr == pRoot)return true;if (pRoot->_color != BLACK){cout << "違反性質(zhì)2：根結(jié)點(diǎn)顏色必須為黑色" << endl;return false;}//獲取一條路徑中結(jié)點(diǎn)的個(gè)數(shù)size_t blackCount = 0; //基準(zhǔn)值Node* pCur = pRoot;while (pCur){if (pCur->_color == BLACK)blackCount++;pCur = pCur->_pLeft;}size_t pathBlack = 0; //每條路徑中的黑色結(jié)點(diǎn)個(gè)數(shù)return _IsValidRBTree(pRoot, blackCount, pathBlack);}bool Empty()const{return nullptr = _pHead->_pParent;}size_t Size()const{return _size;} protected:bool _IsValidRBTree(Node* pRoot, size_t blackCount, size_t pathBlack){if (nullptr == pRoot)return true;if (pRoot->_color == BLACK)pathBlack++;//檢測(cè)性質(zhì)3Node* pParent = pRoot->_pParent;if (pParent != _pHead && pParent->_color == RED&&pRoot->_color == RED){cout << "違反性質(zhì)3:不能有連在一起的紅色結(jié)點(diǎn)" << endl;return false;}if (nullptr == pRoot->_pLeft&&nullptr == pRoot->_pRight){//一條路徑到葉子if (blackCount != pathBlack){cout << "違反了性質(zhì)4：每條路徑中黑色結(jié)點(diǎn)個(gè)數(shù)必須相同" << endl;return false;}}return _IsValidRBTree(pRoot->_pLeft, blackCount, pathBlack) &&_IsValidRBTree(pRoot->_pRight, blackCount, pathBlack);}Node* LeftMost(){//得到根節(jié)點(diǎn)Node* pRoot = GetRoot();if (nullptr == pRoot)return _pHead;Node* pCur = pRoot;//找到最左側(cè)結(jié)點(diǎn)while (pCur->_pLeft)pCur = pCur->_pLeft;return pCur;}Node* RightMost(){//得到根節(jié)點(diǎn)Node* pRoot = GetRoot();if (nullptr == pRoot)return _pHead;Node* pCur = pRoot;//找到最右側(cè)結(jié)點(diǎn)while (pCur->_pRight)pCur = pCur->_pRight;return pCur;}void RotateLeft(Node* pParent){Node* pSubR = pParent->_pRight;Node* pSubRL = pSubR->_pLeft;pParent->_pRight = pSubRL;if (pSubRL)pSubRL->_pParent = pParent;pSubR->_pLeft = pParent;Node* pPParent = pParent->_pParent;pParent->_pParent = pSubR;pSubR->_pParent = pPParent;if (pPParent == _pHead)GetRoot() = pSubR;else{if (pPParent->_pLeft == pParent)pPParent->_pLeft = pSubR;elsepPParent->_pRight = pSubR;}}void RotateRight(Node* pParent){Node* pSubL = pParent->_pLeft;Node* pSubLR = pSubL->_pRight;pParent->_pLeft = pSubLR;if (pSubLR)pSubLR->_pParent = pParent;pSubL->_pRight = pParent;Node* pPParent = pParent->_pParent;pParent->_pParent = pSubL;pSubL->_pParent = pPParent;//pParent是根結(jié)點(diǎn)if (pPParent == _pHead)GetRoot() = pSubL;else{//非根結(jié)點(diǎn)if (pPParent->_pLeft == pParent)pPParent->_pLeft = pSubL;elsepPParent->_pRight = pSubL;}}Node*& GetRoot() //head是new出來(lái)的，head存在parent一定存在，按引用方式返回沒(méi)有問(wèn)題{//得到根節(jié)點(diǎn)，也就是頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)return _pHead->_pParent;}void _InOrder(Node* pRoot){if (pRoot){_InOrder(pRoot->_pLeft);cout << pRoot->_data << " ";_InOrder(pRoot->_pRight);}} private:Node* _pHead;size_t _size; //記錄紅黑樹(shù)中有效結(jié)點(diǎn)的個(gè)數(shù) }; struct KeyValue {int operator()(int data){return data;} };

模擬實(shí)現(xiàn)map和set

map<key,value>----比較方式:鍵值對(duì)中的key
set:key ----比較方式:直接用其元素比較

map模擬實(shí)現(xiàn)

#pragma once #include"RBTree.h"namespace bite {//只需要封裝一個(gè)紅黑樹(shù)template<class K, class V>class map{typedef pair<K, V> ValueType;struct KeyOfValue{const K& operator()(const ValueType & data){return data.first;}};public://編譯器有可能將iterator當(dāng)成靜態(tài)成員變量來(lái)處理typename typedef RBTree<ValueType, KeyOfValue>::iterator iterator;//明確的告訴編譯器iterator 時(shí)紅黑樹(shù)中的一種類(lèi)型public:map():_t(){}iterator begin(){return _t.begin();}iterator end(){return _t.end();}pair<iterator, bool> insert(const ValueType&data){return _t.Insert(data);}size_t size()const{return _t.Size();}bool Empty()const{return _t.Empty();}iterator find(const K& key){return _t.Find(make_pair(key,V()));}V& operator[](const K& key){return (*(_t.Insert(ValueType(key, V()))).first).second;}private:RBTree<ValueType,KeyOfValue> _t;}; }#include<string> #include<iostream> using namespace std; void TestMap() {bite::map<std::string, std::string>m;m.insert(pair<std::string,std::string>("2222","11111"));m.insert(make_pair("1111","1111"));m["0000"] = "0000";cout << m.size() << endl;for (auto e : m)cout << e.first << " " << e.second << endl;cout << endl; }

set模擬實(shí)現(xiàn)

namespace bite {//只需要封裝一個(gè)紅黑樹(shù)template<class K>class set{typedef K ValueType;struct KeyOfValue{const K& operator()(const ValueType & data){return data;}};public://編譯器有可能將iterator當(dāng)成靜態(tài)成員變量來(lái)處理typename typedef RBTree<ValueType, KeyOfValue>::iterator iterator;//明確的告訴編譯器iterator 時(shí)紅黑樹(shù)中的一種類(lèi)型public:set():_t(){}iterator begin(){return _t.begin();}iterator end(){return _t.end();}pair<iterator, bool> insert(const ValueType&data){return _t.Insert(data);}size_t size()const{return _t.Size();}bool Empty()const{return _t.Empty();}iterator find(const K& key){return _t.Find(key);}private:RBTree<ValueType, KeyOfValue> _t;}; } #include<string> #include<iostream> using namespace std; void TestSet() {bite::set<std::string>m;m.insert("2222");m.insert("11111");m.insert("11111");cout << m.size() << endl;for (auto e : m)cout << e << endl;cout << endl; }

總結(jié)

以上是生活随笔為你收集整理的模拟实现STL中map和set容器的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。