一。红黑树的改造
map 和 set 底层都是通过红黑树实现的，但是 set 中存放的是 key，map 中为 key,value。我们不会去写两棵红黑树来实现它们，因为代码会重复，需要对红黑树内部进行改造。
template<class K,class T,class KOfT>
为了可以同时处理 set 和 map，传一个 T 过去，是 set 的时候为 key，map 为 pair<K,V>。
对于 set 和 map 他们的排序，set 可以直接通过 key 来排序，而 map 的排序规则与 set 不同，先比较 key，如果相同比较 value，所以传一个 KOfT。
struct SetKeyOfT { const K& operator()(const K& k) { return k; } };
struct MapKeyOfT { const K& operator()(const pair<K, V>& kv) { return kv.first; } };
通过 KOfT 来分别处理 set 和 map 的排序。
红黑树的迭代器
iterator begin() { Node* cur = _root; while (cur && cur->_left) { cur = cur->_left; } return iterator(cur); }
iterator end() { return iterator(nullptr); }
operator++ 与 operator--
Self& operator++() {
// 如果右不为空，中序的下一个就是右子树的最左节点
// 如果右为空，表示_node 所在子树访问完，下一个节点在他的祖先中找
if (_node->_right) {
Node* subLeft = _node->_right;
while (subLeft->_left) { subLeft = subLeft->_left; }
_node = subLeft;
} else {
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_right) {
cur = cur->_parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
Self& operator--() {
// 与++基本相反
return *this;
}
set 和 map 的实现都是对红黑树的复用，所以理解红黑树是关键。
二。模拟实现 set
set 的实现通过对红黑树的复用即可完成。
template<class K>
class set {
struct SetKeyOfT {
const K& operator()(const K& k) { return k; }
};
public:
typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;
iterator begin() { return _t.begin(); }
iterator end() { return _t.end(); }
pair<iterator, bool> Insert(const K& k) { return _t.Insert(k); }
private:
RBTree<K, K, SetKeyOfT> _t;
};
三。模拟实现 map
template<class K,class V>
class map {
struct MapKeyOfT {
const K& operator()(const pair<K, V>& kv) { return kv.first; }
};
public:
typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator;
iterator begin() { return _t.begin(); }
iterator end() { return _t.end(); }
pair<iterator, bool> Insert(const pair<K, V>& kv) { return _t.Insert(kv); }
V& operator[](const K& key) {
pair<iterator, bool> ret = _t.Insert(make_pair(key, V()));
return ret.first->second;
}
private:
RBTree<K, pair<K, V>, MapKeyOfT> _t;
};
四。整体代码
1.RBTree.h
#pragma once
enum Colour { BLACK, RED, };
template<class T>
struct RBTreeNode {
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
T _data;
Colour _col;
RBTreeNode(const T& data) :_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED) { };
};
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; }
Self& operator++() {
if (_node->_right) {
Node* subLeft = _node->_right;
while (subLeft->_left) { subLeft = subLeft->_left; }
_node = subLeft;
} else {
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_right) {
cur = cur->_parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
Self& operator--() {
return *this;
}
bool operator !=(const Self& s) { return _node != s._node; }
bool operator ==(const Self& s) { return _node == s._node; }
};
template<class K,class T,class KOfT>
class RBTree {
typedef RBTreeNode<T> Node;
public:
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); }
pair<iterator, bool> Insert(const T& data) {
if (_root == nullptr) {
_root = new Node(data);
_root->_col = BLACK;
return make_pair(iterator(_root), true);
}
KOfT koft;
Node* parent = nullptr;
Node* cur = _root;
while (cur) {
if (koft(cur->_data) < koft(data)) {
parent = cur;
cur = cur->_right;
} else if (koft(cur->_data) > koft(data)) {
parent = cur;
cur = cur->_left;
} else {
return make_pair(iterator(cur), false);
}
}
cur = new Node(data);
Node* newnode = cur;
if (koft(parent->_data) < koft(cur->_data)) {
parent->_right = cur;
cur->_parent = parent;
} else {
parent->_left = cur;
cur->_parent = parent;
}
cur->_col = RED;
while (parent && parent->_col == RED) {
Node* grandfather = parent->_parent;
if (grandfather->_left == parent) {
Node* 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->_right) {
RotateL(parent);
swap(parent, cur);
}
RotateR(grandfather);
grandfather->_col = RED;
parent->_col = BLACK;
break;
}
} else {
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->_left) {
RotateR(parent);
swap(parent, cur);
}
RotateL(grandfather);
grandfather->_col = RED;
parent->_col = BLACK;
break;
}
}
}
_root->_col = BLACK;
return make_pair(iterator(newnode), true);
}
void RotateL(Node* parent) {
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL) subRL->_parent = parent;
subR->_left = parent;
Node* ppNode = parent->_parent;
parent->_parent = subR;
if (_root == parent) {
_root = subR;
subR->_parent = nullptr;
} else {
if (ppNode->_left == parent) ppNode->_left = subR;
else ppNode->_right = subR;
subR->_parent = ppNode;
}
}
void RotateR(Node* parent) {
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR) subLR->_parent = parent;
subL->_right = parent;
Node* ppNode = parent->_parent;
parent->_parent = subL;
if (_root == parent) {
_root = subL;
subL->_parent = nullptr;
} else {
if (ppNode->_left == parent) ppNode->_left = subL;
else ppNode->_right = subL;
subL->_parent = ppNode;
}
}
void _InOrder(Node* root) {
if (root == nullptr) return;
_InOrder(root->_left);
cout << root->_data << endl;
_InOrder(root->_right);
}
void InOrder() { _InOrder(_root); }
bool IsValidRBTree() {
Node* pRoot = _root;
if (nullptr == pRoot) return true;
if (BLACK != pRoot->_col) {
cout << "违反红黑树性质：根节点必须为黑色" << endl;
return false;
}
size_t blackCount = 0;
Node* pCur = pRoot;
while (pCur) {
if (BLACK == pCur->_col) blackCount++;
pCur = pCur->_left;
}
size_t k = 0;
return _IsValidRBTree(pRoot, k, blackCount);
}
bool _IsValidRBTree(Node* pRoot, size_t k, const size_t blackCount) {
if (nullptr == pRoot) {
if (k != blackCount) {
cout << "违反性质：每条路径中黑色节点的个数必须相同" << endl;
return false;
}
return true;
}
if (BLACK == pRoot->_col) k++;
Node* pParent = pRoot->_parent;
if (pParent && RED == pParent->_col && RED == pRoot->_col) {
cout << "违反性质：没有连在一起的红色节点" << endl;
return false;
}
return _IsValidRBTree(pRoot->_left, k, blackCount) && _IsValidRBTree(pRoot->_right, k, blackCount);
}
iterator Find(const K& data) {
KOfT koft;
Node* cur = _root;
while (cur) {
if (koft(cur->_data) < koft(data)) {
cur = cur->_right;
} else if (koft(cur->_data) > koft(data)) {
cur = cur->_left;
} else {
return iterator(cur);
}
}
return iterator(nullptr);
}
private:
Node* _root = nullptr;
};
2.MySet.h
#pragma once
#include"RBTree.h"
template<class K>
class set {
struct SetKeyOfT {
const K& operator()(const K& k) { return k; }
};
public:
typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;
iterator begin() { return _t.begin(); }
iterator end() { return _t.end(); }
pair<iterator, bool> Insert(const K& k) { return _t.Insert(k); }
private:
RBTree<K, K, SetKeyOfT> _t;
};
void test_set() {
set<int> s;
s.Insert(1);
s.Insert(3);
s.Insert(2);
s.Insert(4);
s.Insert(5);
set<int>::iterator it = s.begin();
while (it != s.end()) {
cout << *it << " ";
++it;
}
cout << endl;
for (auto e : s) {
cout << e << " ";
}
cout << endl;
}
3.MyMap.h
#pragma once
#include"RBTree.h"
template<class K,class V>
class map {
struct MapKeyOfT {
const K& operator()(const pair<K, V>& kv) { return kv.first; }
};
public:
typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator;
iterator begin() { return _t.begin(); }
iterator end() { return _t.end(); }
pair<iterator, bool> Insert(const pair<K, V>& kv) { return _t.Insert(kv); }
V& operator[](const K& key) {
pair<iterator, bool> ret = _t.Insert(make_pair(key, V()));
return ret.first->second;
}
private:
RBTree<K, pair<K, V>, MapKeyOfT> _t;
};
void test_map() {
map<int, int> m;
m.Insert(make_pair(1, 1));
m.Insert(make_pair(2, 2));
m.Insert(make_pair(4, 4));
m.Insert(make_pair(3, 3));
m.Insert(make_pair(5, 5));
map<int, int>::iterator it = m.begin();
while (it != m.end()) {
cout << it->first << ":" << it->second << endl;
++it;
}
cout << endl;
for (auto e : m) {
cout << e.first << ":" << e.second << endl;
}
cout << endl;
string strs[] = { "西瓜","苹果","西瓜", "葡萄", "西瓜", "橘子", "西瓜", "苹果", "西瓜", "橘子" };
map<string, int> countmap;
for (auto& str : strs) {
countmap[str]++;
}
for (auto kv : countmap) {
cout << kv.first << ":" << kv.second << endl;
}
cout << endl;
}
4.Test.cpp
#include<iostream>
using namespace std;
#include"MyMap.h"
#include"MySet.h"
int main() {
test_map();
test_set();
return 0;
}
