1.map和set底层调用的红黑树的实现
有不清楚的地方，参考AVL树的模拟实现和红黑树的模拟实现
红黑树迭代器的实现
// 红黑树迭代器的类模板
template<class T, class Ref, class Ptr>
struct __RBTreeIterator
{
// 将红黑树节点的类类型定义为Node
typedef RBTreeNode<T> Node;
// 将红黑树迭代器的类类型定义为Self
typedef __RBTreeIterator<T, Ref, Ptr> Self;
// 创建一个红黑树节点的指针
Node* _node;
// 红黑树迭代器的构造函数
__RBTreeIterator(Node* node)
:_node(node)
{}
// 普通迭代器的时候，他是拷贝构造
// const迭代器的时候，他是构造函数，
// 支持用普通迭代器构造const迭代器
__RBTreeIterator(const iterator& s)
:_node(s._node)
{}
// 对红黑树节点的解引用
T& operator*()
{
return _node->_data;
}
// 在外部调用时，编译器会进行这样的处理:
// it->元素 就相当于 it.operator->()->元素
T* operator->()
{
return &_node->_data;
}
// 重载前置++
Self& operator++()
{
// 红黑树遍历的顺序是中序遍历的顺序：左子树 根 右子树
// 假设我们调用s.begin()迭代器，这个迭代器指向这颗红黑树左子树的最小节点
// 接下来，我们要访问这个最小节点的右子树
if (_node->_right)
{
// 如果这个节点的右子树不为空，那么我们就先访问右子树的最小节点，也就是右子树，最左路径的最小节点（根据红黑树访问节点的顺序）
Node* min = _node->_right;
while (min->_left)
{
min = min->_left;
}
// 此时_node为最小节点
_node = min;
}
else
{
// 如果右子树为空，我们需要去找_node节点的祖先节点
// 将cur初始化为_node
Node* cur = _node;
// 父节点就是cur的父节点
Node* parent = cur->_parent;
// parent为空，说明我们已经遍历完了整个红黑树
// 当cur 不等于 parent->_right，说明我们已经找到了我们想要遍历的祖先节点
// 1.最小节点在红黑树的左路节点中，此时可以确定最小节点的右子树为空，
// 2.那么++之后，最小节点的父节点就是迭代器++后指向的节点
while (parent && cur == parent->_right)
{
// 迭代
cur = cur->_parent;
parent = parent->_parent;
}
// 此时parent就是我们要找的祖先节点
_node = parent;
}
// 返回这个迭代器
return *this;
}
// 重载前置--
Self& operator--()
{
// --和++的逻辑是相反的
// ++是按照中序遍历的顺序: 左子树 根 右子树
// --则是将中序遍历的顺序反过来: 右子树 根 左子树
// 假设此时我们迭代器指向的是这颗红黑树的右子树的最右路径的最后一个节点
// 那么接下来我们要访问的就是这个节点的左子树的最大节点
//（所含元素最大的节点，也就是最右路径的最后一个节点）
if (_node->_left)
{
// 当左子树不为空时
// 将最大节点地址初始化为左子树的根节点
Node* max = _node->_left;
// 当max->_right为空时，说明max是最右路径的最后一个节点（也就是key值最大的节点）
while (max->_right)
{
max = max->_right;
}
// _node此时是val值最大的节点
_node = max;
}
else
{
// 当左子树为空时
// 此时，我们需要去找祖先(_node节点的祖先)
Node* cur = _node;
Node* parent = cur->_parent;
// parent为空，说明我们已经遍历完了整颗红黑树
// 当cur 不等于 parent->_left时，说明cur是右路径上的节点，不是parent左子树上面的节点
// 根据遍历的顺序右子树 根 左子树（遍历完右子树的节点后，要遍历根节点，这个根节点就是我们需要找的祖先节点）
while (parent && cur == parent->_left)
{
cur = cur->_parent;
parent = parent->_parent;
}
// 此时parent就是我们需要找的祖先节点
_node = parent;
}
return *this;
}
// 重载不等于
bool operator!=(const Self& s) const
{
// 不相等为真，相等则为假
return _node != s._node;
}
// 重载等于
// 右侧加上const来修饰this，则const迭代器也可以调用这个重载
bool operator==(const Self& s) const
{
return _node == s._node;
}
};
- 前置++
红黑树insert的实现
// 为了支持operator[]的重载，insert的返回值设为pair<iterator, bool>
/*
pair<iterator,bool> insert (const value_type& val)
insert函数的返回值：Return value
The single element versions (1) return a pair, with its member pair::first set to an iterator pointing to either the newly inserted element or to the element with an equivalent key in the map. The pair::second element in the pair is set to true if a new element was inserted or false if an equivalent key already existed.
单元素版本(1)返回一个pair，
其成员pair::first为指向新插入元素或着为指向与key相等的元素的迭代器。
如果插入了新元素，pair中的第二个元素将被设置为true，如果已经存在key则为false。
*/
template<class K, class V>
class map
{
// 仿函数
// 我们通过仿函数MapKeyOfT拿到map的key值
struct MapKeyOfT
{
const K& operator()(const pair<const K, V>& kv)
{
return kv.first;
}
};
}
template<class K>
class set
{
// 仿函数
// 我们通过仿函数SetKeyOfT拿到set的key值
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
}
pair<iterator, bool> Insert(const T& data)
{
// 如果根节点为空，那么新插入的这个节点就是根节点
if (_root == nullptr)
{
// 新创建的节点就是根节点，并且根节点的颜色是黑色
_root = new Node(data);
_root->_col = BLACK;
// 此时，是插入新的节点，因此pair::second为ture
// pair::first为_root节点的迭代器
return make_pair(iterator(_root), true);
}
// 当我们插入新的节点时，
// 1.map->RBTree<K, pair<const K, V>, MapKeyOfT> _t;
// 如果是map，我们通过仿函数MapKeyOfT拿到map的key值
// 2.set->RBTree<K, K, SetKeyOfT> _t;
// 如果是set，我们通过仿函数SetKeyOfT拿到set的key值
// 3.通过比较key的大小，来确定新插入节点的位置
// 4.创建一个仿函数对象，类型为KeyOfT，对象名为kot
KeyOfT kot;
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
// kot(cur->_data)，返回的是map或者set的key值（取决于创建map或者set对象时，传入的仿函数）
if (kot(cur->_data) < kot(data))
{
parent = cur;
cur = cur->_right;
}
else if (kot(cur->_data) > kot(data))
{
parent = cur;
cur = cur->_left;
}
else
{
// 此时，要插入节点的key，与红黑树已有节点cur的key相同，因此返回cur节点的迭代器
// pair::second为false
return make_pair(iterator(cur), false);
}
}
// 构造的新节点
cur = new Node(data);
// 由于最终要返回新插入节点构造的迭代器，因此我们需要提前将cur给到newnode
// 这样，就算后续在调整红黑树时，cur被改变，我们依旧可以通过newnode找到新插入的这个节点
Node* newnode = cur;
cur->_col = RED;
if (kot(parent->_data) < kot(data))
{
parent->_right = cur;
cur->_parent = parent;
}
else
{
parent->_left = cur;
cur->_parent = parent;
}
// 此时，新的节点已经插入到了相对应的位置
// 为了保证插入新节点之后仍旧满足红黑树的性质，
// 我们需要进行相应的变色和旋转
while (parent && parent->_col == RED)
{
Node* grandfater = parent->_parent;
if (parent == grandfater->_left)
{
Node* uncle = grandfater->_right;
// 情况一 uncle存在且为红
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfater->_col = RED;
cur = grandfater;
parent = cur->_parent;
}
else
{
if (cur == parent->_left)
{
// 情况二
RotateR(grandfater);
parent->_col = BLACK;
grandfater->_col = RED;
}
else
{
// 情况三
RotateL(parent);
RotateR(grandfater);
cur->_col = BLACK;
grandfater->_col = RED;
}
break;
}
}
else // (parent == grandfater->_right)
{
Node* uncle = grandfater->_left;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfater->_col = RED;
cur = grandfater;
parent = cur->_parent;
}
else
{
// g
// p
// c
if (cur == parent->_right)
{
RotateL(grandfater);
parent->_col = BLACK;
grandfater->_col = RED;
}
else
{
// g
// p
// c
RotateR(parent);
RotateL(grandfater);
cur->_col = BLACK;
grandfater->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
// 插入节点的迭代器就是iterator(newnode)，插入成功所以pair::second为true
return make_pair(iterator(newnode), true);
}
红黑树完整的模拟实现
// RBTree.h
#pragma once
// 枚举机构
enum Colour
{
RED,
BLACK,
};
// 红黑树节点的类模板
template<class T>
struct RBTreeNode
{
T _data;
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
Colour _col;
RBTreeNode(const T& data)
:_data(data)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _col(RED)
{}
};
// 红黑树迭代器的类模板
template<class T, class Ref, class Ptr>
struct __RBTreeIterator
{
typedef RBTreeNode<T> Node;
typedef __RBTreeIterator<T, Ref, Ptr> Self;
Node* _node;
__RBTreeIterator(Node* node)
:_node(node)
{}
// 普通迭代器的时候，他是拷贝构造
// const迭代器的时候，他是构造，支持用普通迭代器构造const迭代器
// iterator始终是普通迭代器，而Self则会根据实例化生成不同的模板
__RBTreeIterator(const iterator& s)
:_node(s._node)
{}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
Self& operator++()
{
if (_node->_right)
{
Node* min = _node->_right;
while (min->_left)
{
min = min->_left;
}
_node = min;
}
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--()
{
if (_node->_left)
{
Node* max = _node->_left;
while (max->_right)
{
max = max->_right;
}
_node = max;
}
else
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_left)
{
cur = cur->_parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
bool operator!=(const Self& s) const
{
return _node != s._node;
}
bool operator==(const Self& s) const
{
return _node == s._node;
}
};
// 红黑树的类模板实现（传入不同的类型的参数和仿函数，用红黑树的类模板构造map或者set）
// map->RBTree<K, pair<const K, V>, MapKeyOfT> _t;
// set->RBTree<K, K, SetKeyOfT> _t;
template<class K, class T, class KeyOfT>
class RBTree
{
typedef RBTreeNode<T> Node;
public:
// 普通迭代器
typedef __RBTreeIterator<T, T& ,T*> iterator;
// const迭代器
typedef __RBTreeIterator<T, const T&, const T*> const_iterator;
// 普通迭代器
iterator begin()
{
Node* left = _root;
// left不为空，是为了保证left->_left不是野指针
// 当left->_left为空时，说明left是这颗红黑树左子树的最小节点
while (left && left->_left)
{
left = left->_left;
}
// 左路节点的val值最小的节点为起始节点
return iterator(left);
}
iterator end()
{
// end()指向空节点
return iterator(nullptr);
}
// const迭代器
const_iterator begin() const
{
Node* left = _root;
while (left && left->_left)
{
left = left->_left;
}
return const_iterator(left);
}
const_iterator end() const
{
return const_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);
}
KeyOfT kot;
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (kot(cur->_data) < kot(data))
{
parent = cur;
cur = cur->_right;
}
else if (kot(cur->_data) > kot(data))
{
parent = cur;
cur = cur->_left;
}
else
{
// 此时，要插入节点的key，与红黑树已有节点cur的key相同，因此返回cur节点的迭代器
// pair::second为false
return make_pair(iterator(cur), false);
}
}
cur = new Node(data);
// 由于最终要返回新插入节点构造的迭代器，因此我们需要提前将cur给到newnode
// 这样，就算后续在调整红黑树时，cur被改变，我们依旧可以通过newnode找到新插入的这个节点
Node* newnode = cur;
cur->_col = RED;
if (kot(parent->_data) < kot(data))
{
parent->_right = cur;
cur->_parent = parent;
}
else
{
parent->_left = cur;
cur->_parent = parent;
}
// 此时，新的节点已经插入到了相对应的位置
// 为了保证插入新节点之后仍旧满足红黑树的性质，
// 我们需要进行相应的变色和旋转
while (parent && parent->_col == RED)
{
Node* grandfater = parent->_parent;
if (parent == grandfater->_left)
{
Node* uncle = grandfater->_right;
// 情况一 uncle存在且为红
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfater->_col = RED;
cur = grandfater;
parent = cur->_parent;
}
else
{
if (cur == parent->_left)
{
// 情况二
RotateR(grandfater);
parent->_col = BLACK;
grandfater->_col = RED;
}
else
{
// 情况三
RotateL(parent);
RotateR(grandfater);
cur->_col = BLACK;
grandfater->_col = RED;
}
break;
}
}
else // (parent == grandfater->_right)
{
Node* uncle = grandfater->_left;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfater->_col = RED;
cur = grandfater;
parent = cur->_parent;
}
else
{
// g
// p
// c
if (cur == parent->_right)
{
RotateL(grandfater);
parent->_col = BLACK;
grandfater->_col = RED;
}
else
{
// g
// p
// c
RotateR(parent);
RotateL(grandfater);
cur->_col = BLACK;
grandfater->_col = RED;
}
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;
Node* ppNode = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
if (ppNode == nullptr)
{
_root = subR;
_root->_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;
}
Node* ppNode = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
//if (_root == parent)
if (ppNode == nullptr)
{
_root = subL;
_root->_parent = nullptr;
}
else
{
if (ppNode->_left == parent)
{
ppNode->_left = subL;
}
else
{
ppNode->_right = subL;
}
subL->_parent = ppNode;
}
}
// 中序遍历
void Inorder()
{
_Inorder(_root);
}
void _Inorder(Node* root)
{
if (root == nullptr)
return;
_Inorder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
_Inorder(root->_right);
}
bool Check(Node* root, int blackNum, const int ref)
{
if (root == nullptr)
{
//cout << blackNum << endl;
if (blackNum != ref)
{
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, ref)
&& Check(root->_right, blackNum, ref);
}
// 判断是否是红黑树
bool IsBalance()
{
if (_root == nullptr)
{
return true;
}
if (_root->_col != BLACK)
{
return false;
}
int ref = 0;
Node* left = _root;
while (left)
{
if (left->_col == BLACK)
{
++ref;
}
left = left->_left;
}
return Check(_root, 0, ref);
}
private:
Node* _root = nullptr;
};
2.map的实现
#include "RBTree.h"
namespace qwy
{
template<class K, class V>
class map
{
// 仿函数
// 我们通过仿函数MapKeyOfT拿到模板T的key
struct MapKeyOfT
{
const K& operator()(const pair<const K, V>& kv)
{
return kv.first;
}
};
public:
// typename的用法：让编译器明白RBTree<K, K, SetKeyOfT>::iterator是一个类型，而不是静态成员变量，或者静态成员函数
// 此时模板类型RBTree<K, K, SetKeyOfT>::iterator还没有实例化，因此编译器无法确定其到底是模板类型，还是静态成员变量，或者静态成员函数
// 因此，使用typename这个关键词，这样就算没有实例化模板，编译器也知道
// RBTree<K, K, SetKeyOfT>::iterator是一个类型
// 普通迭代器
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
// const迭代器
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
const_iterator begin() const
{
return _t.begin();
}
const_iterator end() const
{
return _t.end();
}
pair<iterator, bool> insert(const pair<const K, V>& kv)
{
return _t.Insert(kv);
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = insert(make_pair(key, V()));
return ret.first->second;
}
private:
// 第一个参数传key，是因为实现find()时，我们需要传key
// iterator find(const key& key)
RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};
void test_map()
{
int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
map<int, int> m;
for (auto e : a)
{
m.insert(make_pair(e, e));
}
map<string, int> countMap;
string arr[] = { "苹果", "西瓜", "香蕉", "草莓", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
for (auto& e : arr)
{
countMap[e]++;
}
for (auto& kv : countMap)
{
cout << kv.first << ":" << kv.second << endl;
}
}
}
3.set的实现
#pragma once
#include "RBTree.h"
namespace qwy
{
template<class K>
class set
{
// 仿函数
// 我们通过仿函数SetKeyOfT拿到模板T的key
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
// typename的用法：让编译器明白RBTree<K, K, SetKeyOfT>::iterator是一个类型，而不是静态成员变量，或者静态成员函数
// 此时模板类型RBTree<K, K, SetKeyOfT>::iterator还没有实例化，因此编译器无法确定其到底是模板类型，还是静态成员变量，或者静态成员函数
// 因此，使用typename这个关键词，这样就算没有实例化模板，编译器也知道
// RBTree<K, K, SetKeyOfT>::iterator是一个类型
// 普通迭代器
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;
// const迭代器
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;
// 为了保证set的模板RBTree<K, K, SetKeyOfT>中的参数K不被修改
// 如迭代器 it
// *it += 10; // 普通迭代器iterator的底层也是const迭代器，因此*it无法被修改
// 因此，我们只提供了一个const的begin, 普通迭代器和const迭代器都可以调用这个接口
iterator begin() const
{
return _t.begin();
}
iterator end() const
{
return _t.end();
}
// pair::first 是一个const迭代器，iterator的底层是const迭代器
pair<iterator, bool> insert(const K& key)
{
// 在set中定义的迭代器iterator和const_iterator的底层都是const迭代器：typename RBTree<K, K, SetKeyOfT>::iterator
// 在红黑树迭代器模板中定义的iterator是普通迭代器：typedef __RBTreeIterator<T, T&, T*> iterator
// insert插入key之后，返回的新节点的迭代器是普通迭代器，因此必须指明iterator是属于红黑树模板中的普通迭代器
pair<typename RBTree<K, K, SetKeyOfT>::iterator, bool> ret = _t.Insert(key);
// 利用我们写的函数__RBTreeIterator(const iterator& s)
// 用普通迭代器ret.first来构造const迭代器iterator
return pair<iterator, bool>(ret.first, ret.second); // 返回了一个匿名对象
}
private:
RBTree<K, K, SetKeyOfT> _t;
};
void test_set()
{
int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
set<int> s;
for (auto e : a)
{
s.insert(e);
}
set<int>::iterator it = s.begin();
while (it != s.end())
{
// *it += 10; // 普通迭代器iterator的底层也是const迭代器，因此*it无法被修改
cout << *it << " ";
++it;
}
cout << endl;
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
}
}
