用一棵红黑树同时封装出map和set
目录
红黑树源代码
下面我们将对一棵KV模型的红黑树进行封装，同时模拟实现出C++STL库当中的map和set，所用到的红黑树源代码如下：
#pragma once
#include<iostream>
#include<vector>
#include<string>
using namespace std;
enum Colour
{
RED,
BLACK,
};
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->_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 = parent->_parent;
}
_node = parent;
}
return *this;
}
Self& operator++()
{
//走的是中序 左 根 右
if (_node->_right)
{
//右子树不为空，下一个就是右子树的最左结点
Node* cur = _node->_right;
while (cur->_left)
{
cur = cur->_left;
}
_node = cur;
}
else
{
//右子树为空，it所在全已访问完，下一个就是往上找左（孩子是父亲左的那个祖先）
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_right)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
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 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);
}
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);
}
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;
while (cur)
{
if (cur->_data < data)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_data > data)
{
parent = cur;
cur = cur->_left;
}
else
{
return make_pair(cur, false);;
}
}
cur = new Node(data);
Node* newnode = cur;
//默认结点颜色为红色
if (parent->_data < data)
{
parent->_right = cur;
cur->_parent = parent;
}
else
{
parent->_left = cur;
cur->_parent = parent;
}
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
//大前提
//parent在左
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
//Node* uncle = parent->_right;//错误二
if (uncle && uncle->_col == RED)
{
//情景一：cur->红，parent->红，grandfather->黑，uncle存在且为红
// g
// p u
// c
//
//解决：p，u改为黑，g改为红，最后g为红所以，要继续向上调整
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_left)
{
//情景二：cur->红，parent->红，grandfather->黑，uncle不存在/为黑
// g
// p u
// c
//
// 解决：对g右单旋，p改为黑，g改为红，最后g为黑所以，直接break
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
//情景三：cur->红，parent->红，grandfather->黑，uncle不存在/为黑
// g
// p u
// c
// 解决：对p左单旋，后变为情景二。
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else//情景大概反着来
{
//1 uncle
Node* uncle = grandfather->_left;//错误一
//Node* uncle = parent->_right;//错误一
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_right)//2
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else//3
{
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
//最后
_root->_col = BLACK;
return make_pair(newnode, true);;
}
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
subR->_left = parent;
Node* parentParent = parent->_parent;
parent->_parent = subR;
if (subRL)
subRL->_parent = parent;
if (_root == parent)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subR;
}
else
{
parentParent->_right = subR;
}
subR->_parent = parentParent;
}
}
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
Node* parentParent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (_root == parent)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subL;
}
else
{
parentParent->_right = subL;
}
subL->_parent = parentParent;
}
}
iterator Find(const K& key)
{
Node* cur = _root;
KeyOfT kot;
while (cur)
{
if (cur->_data < key)
{
cur = cur->_right;
}
else if (cur->_data > key)
{
cur = cur->_left;
}
else
{
return iterator(cur);
}
}
return end();
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << kof(root->_data) << " ";
_InOrder(root->_right);
}
bool Check(Node* root, int blacknum, const int refVal)
{
if (root == nullptr)
{
if (refVal != blacknum)
{
cout << "存在黑色节点数量不相等的路径" << endl;
return false;
}
return true;
}
if (root->_col == RED)
{
if (root->_parent->_col == RED)
{
cout << "有连续的红色节点" << endl;
return false;
}
}
if (root->_col == BLACK)
{
++blacknum;
}
return Check(root->_left, blacknum, refVal)
&& Check(root->_right, blacknum, refVal);
}
bool IsBalance()
{
//1:是否存在 红-红
//每条路径黑色结点是否相同个数
//最长的不超过最短的二倍
//根，叶子为黑
if (_root == nullptr)
return true;
if (_root->_col == RED)
return false;
int refVal = 0;
Node* cur = _root;
while (cur)
{
if (cur->_col == BLACK)
{
++refVal;
}
cur = cur->_left;
}
int blacknum = 0;
return Check(_root, blacknum, refVal);
}
private:
Node* _root = nullptr;
};对于封装，要想看明白这篇文章还是需要把我写的上一篇文章看明白的，上一章的知识就是铺垫知识，是必要的。
模板参数中仿函数的增加
再完成上面的代码后，我们的底层代码已经完成了，这时候已经是一个底层STL的红黑树了，已经已符合库里面的要求了，这时候我们是需要给他穿上对应的“衣服”，比如穿上set的“衣服”，那么这个穿上set的“衣服”，那么他就符合库里面set的要求了，同样map一样，这时候我们就需要实现set与map了。
那么第一个问题就是：
现在由于结点当中存储的是T，这个T可能是Key，也可能是<Key, Value>键值对。那么当我们需要进行结点的键值比较时，应该如何获取结点的键值呢？
当上层容器是set的时候T就是键值Key，直接用T进行比较即可，但当上层容器是map的时候就不行了，此时我们需要从<Key, Value>键值对当中取出键值Key后，再用Key值进行比较。
因此，上层容器map需要向底层红黑树提供一个仿函数，用于获取T当中的键值Key，这样一来，当底层红黑树当中需要比较两个结点的键值时，就可以通过这个仿函数来获取T当中的键值了。
仿函数，就是使一个类的使用看上去像一个函数。其实现就是类中实现一个
operator()，这个类就有了类似函数的行为，就是一个仿函数类了。
template<class K, class V>
class map
{
public:
//仿函数
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
//...
private:
RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};但是对于底层红黑树来说，它并不知道上层容器是map还是set，因此当需要进行两个结点键值的比较时，底层红黑树都会通过传入的仿函数来获取键值Key，进而进行两个结点键值的比较。
因此，set容器也需要向底层红黑树传入一个仿函数，虽然这个仿函数单独看起来没什么用，但却是必不可少的。
template<class K>
class set
{
public:
//仿函数
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
private:
RBTree<K, K, SetKeyOfT> _t;
};此时，set容器传入底层红黑树的就是set的仿函数，map容器传入底层红黑树的就是map的仿函数。
这样一来，当底层红黑树需要进行两个结点之间键值的比较时，都会通过传入的仿函数来获取相应结点的键值，然后再进行比较，下面以红黑树的查找函数为例：
我们就可以使用仿函数了。
iterator Find(const K& key)
{
Node* cur = _root;
KeyOfT kot;
while (cur)
{
if (kot(cur->_data) < key)
{
cur = cur->_right;
}
else if (kot(cur->_data) > key)
{
cur = cur->_left;
}
else
{
return iterator(cur);
}
}
return end();
}注意： 所有进行结点键值比较的地方，均需要通过仿函数获取对应结点的键值后再进行键值的比较。
同样我们还需要用同样的方法对insert进行修改，
修改后的代码：
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 kot;
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
{
return make_pair(cur, false);;
}
}
cur = new Node(data);
Node* newnode = cur;
//默认结点颜色为红色
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* grandfather = parent->_parent;
//大前提
//parent在左
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
//Node* uncle = parent->_right;//错误二
if (uncle && uncle->_col == RED)
{
//情景一：cur->红，parent->红，grandfather->黑，uncle存在且为红
// g
// p u
// c
//
//解决：p，u改为黑，g改为红，最后g为红所以，要继续向上调整
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_left)
{
//情景二：cur->红，parent->红，grandfather->黑，uncle不存在/为黑
// g
// p u
// c
//
// 解决：对g右单旋，p改为黑，g改为红，最后g为黑所以，直接break
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
//情景三：cur->红，parent->红，grandfather->黑，uncle不存在/为黑
// g
// p u
// c
// 解决：对p左单旋，后变为情景二。
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else//情景大概反着来
{
//1 uncle
Node* uncle = grandfather->_left;//错误一
//Node* uncle = parent->_right;//错误一
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_right)//2
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else//3
{
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
//最后
_root->_col = BLACK;
return make_pair(newnode, true);;
}
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
subR->_left = parent;
Node* parentParent = parent->_parent;
parent->_parent = subR;
if (subRL)
subRL->_parent = parent;
if (_root == parent)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subR;
}
else
{
parentParent->_right = subR;
}
subR->_parent = parentParent;
}
}
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
Node* parentParent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (_root == parent)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subL;
}
else
{
parentParent->_right = subL;
}
subL->_parent = parentParent;
}
}修改后的红黑树代码：
#pragma once
#include<iostream>
#include<vector>
#include<string>
using namespace std;
enum Colour
{
RED,
BLACK,
};
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->_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 = parent->_parent;
}
_node = parent;
}
return *this;
}
Self& operator++()
{
//走的是中序 左 根 右
if (_node->_right)
{
//右子树不为空，下一个就是右子树的最左结点
Node* cur = _node->_right;
while (cur->_left)
{
cur = cur->_left;
}
_node = cur;
}
else
{
//右子树为空，it所在全已访问完，下一个就是往上找左（孩子是父亲左的那个祖先）
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_right)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
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 KeyOfT>
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);
}
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);
}
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 kot;
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
{
return make_pair(cur, false);;
}
}
cur = new Node(data);
Node* newnode = cur;
//默认结点颜色为红色
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* grandfather = parent->_parent;
//大前提
//parent在左
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
//Node* uncle = parent->_right;//错误二
if (uncle && uncle->_col == RED)
{
//情景一：cur->红，parent->红，grandfather->黑，uncle存在且为红
// g
// p u
// c
//
//解决：p，u改为黑，g改为红，最后g为红所以，要继续向上调整
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_left)
{
//情景二：cur->红，parent->红，grandfather->黑，uncle不存在/为黑
// g
// p u
// c
//
// 解决：对g右单旋，p改为黑，g改为红，最后g为黑所以，直接break
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
//情景三：cur->红，parent->红，grandfather->黑，uncle不存在/为黑
// g
// p u
// c
// 解决：对p左单旋，后变为情景二。
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else//情景大概反着来
{
//1 uncle
Node* uncle = grandfather->_left;//错误一
//Node* uncle = parent->_right;//错误一
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_right)//2
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else//3
{
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
//最后
_root->_col = BLACK;
return make_pair(newnode, true);;
}
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
subR->_left = parent;
Node* parentParent = parent->_parent;
parent->_parent = subR;
if (subRL)
subRL->_parent = parent;
if (_root == parent)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subR;
}
else
{
parentParent->_right = subR;
}
subR->_parent = parentParent;
}
}
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
Node* parentParent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (_root == parent)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subL;
}
else
{
parentParent->_right = subL;
}
subL->_parent = parentParent;
}
}
iterator Find(const K& key)
{
Node* cur = _root;
KeyOfT kot;
while (cur)
{
if (kot(cur->_data) < key)
{
cur = cur->_right;
}
else if (kot(cur->_data) > key)
{
cur = cur->_left;
}
else
{
return iterator(cur);
}
}
return end();
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << kof(root->_data) << " ";
_InOrder(root->_right);
}
bool Check(Node* root, int blacknum, const int refVal)
{
if (root == nullptr)
{
if (refVal != blacknum)
{
cout << "存在黑色节点数量不相等的路径" << endl;
return false;
}
return true;
}
if (root->_col == RED)
{
if (root->_parent->_col == RED)
{
cout << "有连续的红色节点" << endl;
return false;
}
}
if (root->_col == BLACK)
{
++blacknum;
}
return Check(root->_left, blacknum, refVal)
&& Check(root->_right, blacknum, refVal);
}
bool IsBalance()
{
//1:是否存在 红-红
//每条路径黑色结点是否相同个数
//最长的不超过最短的二倍
//根，叶子为黑
if (_root == nullptr)
return true;
if (_root->_col == RED)
return false;
int refVal = 0;
Node* cur = _root;
while (cur)
{
if (cur->_col == BLACK)
{
++refVal;
}
cur = cur->_left;
}
int blacknum = 0;
return Check(_root, blacknum, refVal);
}
private:
Node* _root = nullptr;
};set的模拟实现
同样对于set的代码还需要添加上各个底层实现的功能，比如insert，find，迭代器begin与end......
其模拟实现也就很简单了，其中的成员函数都是调用底层红黑树的对应接口就行了，只不过需要注意将插入函数和查找函数返回值当中的结点指针改为迭代器即可。
template<class K>
class set
{
public:
//仿函数
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
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();
}
pair<iterator, bool> insert(const K& key)
{
return _t.Insert(key);
}
bool IsBalance()
{
return _t.IsBalance();
}
private:
RBTree<K, K, SetKeyOfT> _t;
};map的模拟实现
map的模拟实现也是相同的道理，其成员函数也是调用底层红黑树的对应接口，但对于map来说，除了将插入函数和查找函数返回值当中的结点指针改为迭代器之外，还需要实现[]运算符的重载函数。
template<class K, class V>
class map
{
public:
//仿函数
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
// 对类模板取内嵌类型，加typename告诉编译器这里是类型
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;
iterator begin() const
{
return _t.begin();
}
iterator end() const
{
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 = insert(make_pair(key, V()));//默认构造为0
//V()：在这里，V() 是一个临时创建的 V 类型的对象。
// 它使用 V 类型的默认构造函数创建一个默认的值对象。
// 这样做的目的是为了确保即使映射中没有该键，
// 也能够返回一个默认构造的值的引用，以便在插入新键值对时，
// 通过返回引用，可以直接为新键关联一个默认构造的值。
return ret.first->second;
}
bool IsBalance()
{
return _t.IsBalance();
}
private:
RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};封装完成后的代码
虽然封装过程已经阐述完毕了，但在代码更改过程中还是有许多细节的，下面给出完整封装后的代码。
红黑树的代码
#pragma once
#include<iostream>
#include<vector>
#include<string>
using namespace std;
enum Colour
{
RED,
BLACK,
};
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->_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 = parent->_parent;
}
_node = parent;
}
return *this;
}
Self& operator++()
{
//走的是中序 左 根 右
if (_node->_right)
{
//右子树不为空，下一个就是右子树的最左结点
Node* cur = _node->_right;
while (cur->_left)
{
cur = cur->_left;
}
_node = cur;
}
else
{
//右子树为空，it所在全已访问完，下一个就是往上找左（孩子是父亲左的那个祖先）
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_right)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
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 KeyOfT>
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);
}
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);
}
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 kot;
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
{
return make_pair(cur, false);;
}
}
cur = new Node(data);
Node* newnode = cur;
//默认结点颜色为红色
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* grandfather = parent->_parent;
//大前提
//parent在左
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
//Node* uncle = parent->_right;//错误二
if (uncle && uncle->_col == RED)
{
//情景一：cur->红，parent->红，grandfather->黑，uncle存在且为红
// g
// p u
// c
//
//解决：p，u改为黑，g改为红，最后g为红所以，要继续向上调整
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_left)
{
//情景二：cur->红，parent->红，grandfather->黑，uncle不存在/为黑
// g
// p u
// c
//
// 解决：对g右单旋，p改为黑，g改为红，最后g为黑所以，直接break
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
//情景三：cur->红，parent->红，grandfather->黑，uncle不存在/为黑
// g
// p u
// c
// 解决：对p左单旋，后变为情景二。
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else//情景大概反着来
{
//1 uncle
Node* uncle = grandfather->_left;//错误一
//Node* uncle = parent->_right;//错误一
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_right)//2
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else//3
{
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
//最后
_root->_col = BLACK;
return make_pair(newnode, true);;
}
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
subR->_left = parent;
Node* parentParent = parent->_parent;
parent->_parent = subR;
if (subRL)
subRL->_parent = parent;
if (_root == parent)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subR;
}
else
{
parentParent->_right = subR;
}
subR->_parent = parentParent;
}
}
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
Node* parentParent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (_root == parent)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subL;
}
else
{
parentParent->_right = subL;
}
subL->_parent = parentParent;
}
}
iterator Find(const K& key)
{
Node* cur = _root;
KeyOfT kot;
while (cur)
{
if (kot(cur->_data) < key)
{
cur = cur->_right;
}
else if (kot(cur->_data) > key)
{
cur = cur->_left;
}
else
{
return iterator(cur);
}
}
return end();
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << kof(root->_data) << " ";
_InOrder(root->_right);
}
bool Check(Node* root, int blacknum, const int refVal)
{
if (root == nullptr)
{
if (refVal != blacknum)
{
cout << "存在黑色节点数量不相等的路径" << endl;
return false;
}
return true;
}
if (root->_col == RED)
{
if (root->_parent->_col == RED)
{
cout << "有连续的红色节点" << endl;
return false;
}
}
if (root->_col == BLACK)
{
++blacknum;
}
return Check(root->_left, blacknum, refVal)
&& Check(root->_right, blacknum, refVal);
}
bool IsBalance()
{
//1:是否存在 红-红
//每条路径黑色结点是否相同个数
//最长的不超过最短的二倍
//根，叶子为黑
if (_root == nullptr)
return true;
if (_root->_col == RED)
return false;
int refVal = 0;
Node* cur = _root;
while (cur)
{
if (cur->_col == BLACK)
{
++refVal;
}
cur = cur->_left;
}
int blacknum = 0;
return Check(_root, blacknum, refVal);
}
private:
Node* _root = nullptr;
};set的代码
#pragma once
#include"RBTree.h"
namespace myset
{
template<class K>
class set
{
public:
//仿函数
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
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();
}
pair<iterator, bool> insert(const K& key)
{
return _t.Insert(key);
}
bool IsBalance()
{
return _t.IsBalance();
}
private:
RBTree<K, K, SetKeyOfT> _t;
};
}map的代码
#pragma once
#include"RBTree.h"
namespace mymap
{
template<class K, class V>
class map
{
public:
//仿函数
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
// 对类模板取内嵌类型，加typename告诉编译器这里是类型
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;
iterator begin() const
{
return _t.begin();
}
iterator end() const
{
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 = insert(make_pair(key, V()));//默认构造为0
//V()：在这里，V() 是一个临时创建的 V 类型的对象。
// 它使用 V 类型的默认构造函数创建一个默认的值对象。
// 这样做的目的是为了确保即使映射中没有该键，
// 也能够返回一个默认构造的值的引用，以便在插入新键值对时，
// 通过返回引用，可以直接为新键关联一个默认构造的值。
return ret.first->second;
}
bool IsBalance()
{
return _t.IsBalance();
}
private:
RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};
}
原文地址：https://blog.csdn.net/2301_81265915/article/details/142860566
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！