Stl中map、set 容器（数据结构：AVL树、红黑树）--C++
目录
前言
set
set的模板参数
set的功能概览
set的insert函数
set测试
map
map的模板参数
map的功能概览
map的insert函数
map的 [ ] 重载
map测试
AVL树
AVL树性质
AVL树的节点结构
AVL树的 insert 操作
四种插入情况
1.插入节点在较高的左子树的左侧--右单旋
2.插入节点在较高的右子树的右侧--左单旋
3.插入节点在较高的左子树的右侧--左右旋
4.插入节点在较高的右子树的左侧
insert函数代码
AVL树规则检测
AVL树测试
高度检测
中序检测
红黑树
红黑树性质
红黑树节点
红黑树框架
红黑树insert实现
insert框架
插入位置的查找
插入之后的调整
红黑树迭代器实现
框架
*
->
前置++
后置++
前置--
后置--
重载 != 与 ==
红黑树的其他函数部分模拟
红黑树模拟实现map
代码
测试
红黑树模拟实现set
代码
测试
总结
前言
Stl的容器中，map和set都是用的树状数据结构----二叉树！但实际上用的并不是普普通通的树状结构，而是一种设计好的，规律性极强的树状数据结构：红黑树（二叉树的一种，细节下面讲）对于map和set来讲，中序遍历依旧是有序的，而这和之前讲的二叉搜索树有点相似。
在之前的一篇博客里我对二叉搜索树（又叫二叉排序树）的结构和功能进行了一番解析，但是在最后性能那里谈到了一点：二叉搜索树的性能不够稳定，容易出现有序数据插入造树形成单支二叉树的情况，从而使二叉树的数据结构的优势没法发挥出来，这让实际应用变得不是那么靠谱。基于上述情况，AVL树和红黑树就诞生了，他们是在继承二叉搜索树的优点的基础上，进一步解决了树不平衡的问题，使树尽量保持接近完全二叉树，使性能变得更加稳定，因此map和set的实现就选用了红黑树作为底层实现的数据结构。（其实AVL树也能实现map和set，Stl为什么不选用后面会讲到。）
接下来我们会以map和set的插入操作为切入点逐步讲解。并会对AVL树和红黑树的插入操作进行模拟。
set
容器的一种，底层以红黑树数据结构实现。节点只存一个值key，且节点值不重复。
set的模板参数
T：既是key值的类型 ，又是value值类型。
value值就是与key值对应的另一个数据，相当于每个节点存了两个数据，但只有key值用来判断节点的插入与否和插入位置，且value值可改而key值不能改。实际上set只有key值，所以value值的数据类型看成是key的数据类型也行，不影响树的生成。这样做实际上是与map的节点值类型保持一致，一个节点都有两个数据。个人认为是底层用红黑树实现的影响，无伤大雅。
补充：
key又叫键值
value又叫实值
Compare：树的中序遍历的排序方式，默认是升序排列。
Alloc：内存分配器，默认调用库里提供的内存池。
set的功能概览
set的insert函数
可以看出有三种插入方式：
1.参数：单个数据val。返回值：pair<iterator,bool>类型的数据。插入成功返回插入节点的迭代器和ture，重复插入返回已有val值的节点的迭代器和false。
pair是把两个数据揉成一个数据的操作，两个数据形成一个键值对，实际上给人的感觉就像是一个类，需要那个数据就取哪个数据。（通过调用公有成员first和second来实现）
2.参数：插入节点的迭代器position，插入数据val。返回值：插入成功返回插入新节点的迭代器，重复插入返回已有val值的节点的迭代器。
3.参数：插入数据的迭代器区间。返回值：无返回值。
set测试
// set::insert (C++98)
#include <iostream>
#include <set>
int main ()
{
std::set<int> myset;
std::set<int>::iterator it;
std::pair<std::set<int>::iterator,bool> ret;
// 单个数据插入
for (int i=1; i<=5; ++i) myset.insert(i*10); // set: 10 20 30 40 50
ret = myset.insert(20); // 重复插入20
if (ret.second==false) it=ret.first; // "it" now points to element 20
//通过迭代器插入
myset.insert (it,25);
myset.insert (it,24);
myset.insert (it,26);
//区间插入
int myints[]= {5,10,15};
myset.insert (myints,myints+3);
std::cout << "myset contains:";
for (it=myset.begin(); it!=myset.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
return 0;
}
map
map的模板参数
Key:键值
T：实值
Compare：树的中序遍历的排序方式，默认是升序排列。
Alloc：内存分配器，默认调用库里提供的内存池。
map的功能概览
map的insert函数
有三种插入方式：
1.参数：val（pair类型）。返回值：pair<iterator,bool>类型的数据。插入成功返回插入节点的迭代器和ture，重复插入返回已有val.first值（key值）的节点的迭代器和false。
2.参数：插入节点的迭代器position，插入数据val。返回值：插入成功返回插入新节点的迭代器，重复插入返回已有val值的节点的迭代器。
3.参数：插入数据的迭代器区间。返回值：无返回值。
map的 [ ] 重载
这个 [ ] 就相当于执行了插入操作，并返回了插入函数所返回的迭代器的实值引用。可以看出这种操作相当于插入和改变实值同时进行了。
map测试
#include <iostream>
#include <map>
int main()
{
std::map<char, int> mymap;
// first insert function version (single parameter):
mymap.insert(std::pair<char, int>('a', 100));
mymap.insert(std::pair<char, int>('z', 200));
std::pair<std::map<char, int>::iterator, bool> ret;
ret = mymap.insert(std::pair<char, int>('z', 500));
if (ret.second == false) {
std::cout << "element 'z' already existed";
std::cout << " with a value of " << ret.first->second << '\n';
}
// second insert function version (with hint position):
std::map<char, int>::iterator it = mymap.begin();
mymap.insert(it, std::pair<char, int>('b', 300));
mymap.insert(it, std::pair<char, int>('c', 400));
// third insert function version (range insertion):
std::map<char, int> anothermap;
anothermap.insert(mymap.begin(), mymap.find('c'));
// showing contents:
std::cout << "mymap contains:\n";
for (it = mymap.begin(); it != mymap.end(); ++it)
std::cout << it->first << " => " << it->second << '\n';
std::cout << "anothermap contains:\n";
for (it = anothermap.begin(); it != anothermap.end(); ++it)
std::cout << it->first << " => " << it->second << '\n';
return 0;
}
AVL树
定义：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
AVL树性质
1.左右子树都是AVL树
2.左右子树的高度差（平衡因子）的绝对值不超过1.
3.树的高度：logN（N为节点数）
由上面的性质2可知，AVL树的形状非常接近完全二叉树了。
AVL树的节点结构
//三叉链
template<class K, class V>
struct AVLTreeNode
{
pair<K, V> _kv;
AVLTreeNode<K, V>* _parent;
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
int _bf;（平衡因子）左树插入--，右树插入++
AVLTreeNode()
:_kv(K(),V())
, _parent(nullptr)
, _left(nullptr)
, _right(nullptr)
, _bf(0)//构造的节点左右子树为空，因此平衡因子为零
{}
AVLTreeNode(const pair<K,V>& kv)
:_kv(kv)
, _parent(nullptr)
,_left(nullptr)
,_right(nullptr)
,_bf(0)
{}
};AVL树的 insert 操作
首先，在满足左大右小的排序排列规则时，同时还要满足平衡因子绝对值不超过1。这就给插入操作带来了很大的不便：总会有不满足条件的时候，这时的插入操作还要进行吗？
事实上，最开始我们只管插入，插入之后发现平衡因子不符合规则了，我们就对树进行调整。具体怎么调整得看树的具体结构。
四种插入情况
1.插入节点在较高的左子树的左侧
2.插入节点在较高的右子树的右侧
3.插入节点在较高的左子树的右侧
4.插入节点在较高的右子树的左侧
1.插入节点在较高的左子树的左侧--右单旋
上面的相当于把右树往下调整了，使得树的高度变得一致。这个步骤我们给他起名叫右旋。而4和5节点的平衡因子都要变为0。
代码：
void RotateR(Node* parent)//parent节点相当于5节点
{
Node* subL = parent->_left;//相当于4节点
Node* subLR = subL->_right;//相当于b子树的根节点
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
Node* pp = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (parent == _root)//考虑到parent为根节点，要直接更新根节点。
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (pp->_left == parent)
{
pp->_left = subL;
}
else
{
pp->_right = subL;
}
subL->_parent = pp;
}
subL->_bf = 0;
parent->_bf = 0;
}2.插入节点在较高的右子树的右侧--左单旋
右边的树高就把左边的树往下旋转，以此达到平衡的目的。
代码：
void RotateL(Node* parent)//相当于5节点
{
Node* subR = parent->_right;//相当于6节点
Node* subRL = subR->_left;//相当于b子树的根节点
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
Node* pp = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
if (parent == _root)//考虑到parent为根节点，要直接更新根节点。
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (pp->_left == parent)
{
pp->_left = subR;
}
else
{
pp->_right = subR;
}
subR->_parent = pp;
}
subR->_bf = 0;
parent->_bf = 0;
}🔺左单旋和右单旋的作用：
左单旋使左树的高度增加，右单旋使右子树的高度增加。
3.插入节点在较高的左子树的右侧--左右旋
因为左子树的右侧高了，因此可以通过左旋把左子树的左侧高度调高。调整完之后发现整个树左树太高了，因此通过右旋使整个树的右树高度变高。最终实现高度的调节。最后将对应的平衡因子更改就行了。
可以看出，无论是在b树中插入，还是在c树中插入，都不会影响最后的结果，但是会影响平衡因子的改变，所以要判断一下。
代码：
void RotateLR(Node* parent)//相当于8节点
{
Node* subL = parent->_left;//相当于4节点
Node* subLR = subL->_right;//相当于6节点
int bf = subLR->_bf;//提前存下插入子树父节点的平衡因子，用来判断插入的位置是左还是右。
RotateL(subL);
RotateR(parent);
//针对不同的情况对平衡因子进行更改。
if (bf == 0)
{
subL->_bf = 0;
subLR->_bf = 0;
parent->_bf = 0;
}
else if (bf == -1)
{
subL->_bf = 0;
subLR->_bf = 0;
parent->_bf = 1;
}
else if(bf == 1)
{
subL->_bf = -1;
subLR->_bf = 0;
parent->_bf = 0;
}
else
{
assert(false);
}
}4.插入节点在较高的右子树的左侧
思想与情况三一致。
代码：
void RotateRL(Node* parent)//相当于4节点
{
Node* subR = parent->_right;//相当于8节点
Node* subRL = subR->_left;//相当于6节点
int bf = subRL->_bf;//提前存下插入子树父节点的平衡因子，用来判断插入的位置是左还是右。
RotateR(subR);
RotateL(parent);
//针对不同的情况对平衡因子进行更改。
if (bf == 0)
{
subR->_bf = 0;
subRL->_bf = 0;
parent->_bf = 0;
}
else if (bf == -1)
{
subR->_bf = 1;
subRL->_bf = 0;
parent->_bf = 0;
}
else if(bf == 1)
{
subR->_bf = 0;
subRL->_bf = 0;
parent->_bf = -1;
}
else
{
assert(false);
}
}insert函数代码
因为是模拟，并且也不是库中map和set的底层，我们先不实现AVL树的迭代器了（下面的红黑树我们再实现），因此insert的返回值这里我们先只返回bool值。
bool Insert(const pair<K, V>& kv)
{
//根节点为空，直接更改根节点
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
//寻找插入位置
while (cur)
{
if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else
{
return false;//重复插入，失败。
}
}
cur = new Node(kv);
if (parent->_kv.first > kv.first)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = parent;
//插入之后会使对应路径上的平衡因子都发生改变，因此要从当前节点的父节点一一往上排查。
while (parent)
{
if (cur == parent->_left)
{
parent->_bf--;//左减
}
else
{
parent->_bf++;//右加
}
if (parent->_bf == 0)
{
break;
//此时的子树平衡了，说明插入使得树刚好平衡，就对上面的树没影响了，因此直接跳出循环。
}
else if (parent->_bf == 1 || parent->_bf == -1)
{
//插入后使得原本为0的平衡因子变了，因此造成了上面树的高度的变化，要继续排查。
cur = parent;
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2)
{
//平衡因子明显不符合标准了，因此要分析是哪种情况，并进行旋转操作。
if (parent->_bf == 2 && cur->_bf == 1)
{
RotateL(parent);
}
else if (parent->_bf == -2 && cur->_bf == -1)
{
RotateR(parent);
}
else if (parent->_bf == -2 && cur->_bf == 1)
{
RotateLR(parent);
}
else if (parent->_bf == 2 && cur->_bf == -1)
{
RotateRL(parent);
}
else
{
assert(false);
}
break;
}
//出现了理论上不可能出现的结果，报错。
else
{
assert(false);
}
}
return true;
}AVL树规则检测
AVL树的检测简单来讲就是检测中序遍历是否得到有序数列且每个节点两侧子树的高度差。根据AVL树的机制，高度差不得超过1。因此需要一个计算树的高度的函数，并进行递归操作，检测每一个子树的两侧高度差。
void _InOrder(const Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
_InOrder(root->_right);
}
int _Height(Node* root)
{
if (root == nullptr)
return 0;
int lh = _Height(root->_left);
int rh = _Height(root->_right);
return lh > rh ? lh + 1 : rh + 1;//返回左右子树较高的高度作为当前节点的高度
}
bool _IsBalanceTree(Node* root)
{
if (nullptr == root)
return true;
int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
int diff = rightHeight - leftHeight;//左右子树的高度差
if (abs(diff) >= 2)
{
return false;
}
if (diff != root->_bf)
{
return false;
}
return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);//递归检测左右子树
}
//嵌套一下是避免使用的时候在类外传参！！！
void InOrder()
{
_InOrder(_root);
}
bool IsBalanceTree()
{
return _IsBalanceTree(_root);
}
int Height()
{
return _Height(_root);
}AVL树测试
高度检测
void test_AVLTree()
{
const size_t n = 1000000;
srand(time(0));//随机生成一百万个随机数
AVLTree<int, int> at;
vector<int> v;
v.reserve(n);
for (size_t i = 0; i < n; ++i)
{
v.push_back(rand());
//v.push_back(i);
}
for (const auto& e : v)//树的插入操作
{
at.Insert(make_pair(e, e));
}
if (at.IsBalanceTree())//判断是不是AVL树
{
cout << "Is BalanceTree!" << endl;
}
cout << at.Height() << endl;//树的高度
}
int main()
{
test_AVLTree();
return 0;
}
树的高度是18，而2^18为262144，并不是一百万。原因在于随机数的个数有限，会重复插入。
接下来我们再试试有序数据的插入！
void test_AVLTree()
{
const size_t n = 1000000;
AVLTree<int, int> at;
for (size_t i = 0; i < n; ++i)
{
at.Insert(make_pair(i, i));//有序插入
}
if (at.IsBalanceTree())
{
cout << "Is BalanceTree!" << endl;
}
cout << at.Height() << endl;
}
int main()
{
test_AVLTree();
return 0;
}
观察到树的高度变为20了，而2^20=1,048,576，大概就是一百万的。反向也能推出这是一个AVL树。
中序检测
void test_AVLTree()
{
const size_t n = 10;
srand(time(0));
AVLTree<int, int> at;
vector<int> v;
v.reserve(n);
for (size_t i = 0; i < n; ++i)
{
v.push_back(rand());
}
for (const auto& e : v)
{
at.Insert(make_pair(e, e));
}
if (at.IsBalanceTree())
{
cout << "Is BalanceTree!" << endl;
}
cout << at.Height() << endl;
at.InOrder();
}
int main()
{
test_AVLTree();
return 0;
}
升序排列，正确！
红黑树
红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或
Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路
径会比其他路径长出俩倍，因而是接近平衡的。
与AVL树相比，红黑树的规则更加的宽松。长度只要不超过2倍就行。因此进行的调整次数就会减少一部分，效率就相对高一点。因此用红黑树作为map和set的底层结构。
红黑树性质
1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色的，则它的两个孩子结点是黑色的
4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。最极端的情况就是一条路全是黑色节点（最短路径），一条路是严格的红黑相交（最长路径），因此最长的路径顶多是最短路径的2倍。
5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
红黑树节点
我们之后的红黑树代码实现都是以作为map和set的底层来写的，因此节点存储的数据类型统一使用Data泛型，之后在实现map和set的时候再具体操作，这个我们在这提一嘴，下面会具体讲。
enum Color
{
Red,
Black
};
template<class T>
struct RedBlackTreeNode
{
RedBlackTreeNode<T>* _left;
RedBlackTreeNode<T>* _right;
RedBlackTreeNode<T>* _parent; //三叉链
T _data; //节点数据
Color _col; //节点颜色
RedBlackTreeNode(const T& data)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_data(data)
,_col(Red) //默认颜色为红色
{}
};红黑树框架
template<class K, class T, class KeyOfT> //KeyOfT是一个仿函数的模板，作用是取泛型Data中的Key值。
class RedBlackTree
{
typedef RedBlackTreeNode<T> Node;//节点名称简化
public:
typedef __RedBlackTreeIterator<T, T&, T*> iterator;//迭代器实现在后面，先用着
typedef __RedBlackTreeIterator<T, const T&, const T*> const_iterator;
RedBlackTree()
:_root(nullptr)
{}
/.../ //具体功能
private:
Node* _root;//最初只有根节点
}
红黑树insert实现
相似于AVL树，红黑树的插入也是在找到插入节点的位置后，要判断插入之后整个树的结构是否需要进行调整。且根据不同的情况，要进行不同的调整。
接下来我们就情况来分析插入的操作。
insert框架
pair<iterator, bool> Insert(const T& data)
{
/.../
}返回值类型是pair，包含插入位置的迭代器，以及是否成功插入的布尔值。
插入位置的查找
if (_root == nullptr)//空树改变根节点
{
_root = new Node(data);
_root->_col = Black;
return make_pair(iterator(_root), true);
}
KeyOfT kot;//实例化取key值的仿函数
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (kot(cur->_data) > kot(data))//通过key值在树里查找位置
{
parent = cur;
cur = cur->_left;
}
else if (kot(cur->_data) < kot(data))
{
parent = cur;
cur = cur->_right;
}
else
{
return make_pair(iterator(cur), false); //此时代表重复插入
}
}
cur = new Node(data);//此时表示插入成功，再次判断到底是上一个节点的左节点还是右节点，并进行链接。
Node* newnode = cur;
cur->_col = Red;
if (kot(parent->_data) > kot(data))
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = parent;插入之后的调整
情况1：当前节点以及其父节点和叔叔节点都存在且都为红。
做法：将parent和uncle节点的颜色改为黑色，grandfather节点的颜色改为红色。然后继续向上检查，防止因为grandfather节点的颜色变红造成和grandfather的父节点的颜色冲突 。
cur = grandfather; parent = cur->_parent;
这样一直向上检查到cur为黑色节点就停止。
更改颜色的原因：既满足没有相邻红色节点的要求，又没有改变从grandfather开始算起的每条路径上的黑色节点的数量。（总体上看确实是多了一个黑色节点）
更改过程：
情况2：cur为红，parent为红，grandfather为黑，uncle为黑或uncle不存在。parent为左孩子，uncle为右孩子。
首先我们得清楚一点：当uncle不存在时，cur一定是新插入的节点，原因在于如果不是新插入的节点，则在新的节点插入之前，cur和parent作为原来就存在的节点，必须有一个是黑色的（现在都是红色是因为经过调整了）。而这样就会导致grandfather左右树的黑色节点的数量不相等，与性质四相违背。
因此，当uncle存在且为黑时，cur之所以为红就是经过调整从黑色变成红色的。为什么会这样调整呢？原因可以理解为在进行情况2的调整前，进行了情况一的调整，使得cur由黑变红。而情况一的调整机制是不改变每条路径上的黑色节点数量，因此这时我们就不能仅仅改变parent为黑色，这会导致grandfather节点的左子树的黑色节点数量比右子树多一。
而uncle不存在时，也不能直接改变parent或cur的颜色变为黑色，那样做同样会导致grandfather节点的左子树的黑色节点数量比右子树多一。
综上！我们此时只能借助旋转的思想来调整红黑树此时的尴尬情况。
就以cur为parent的右孩子为例讲解，也就是上图的第二种。
操作：
先以parent为旋转点进行左旋，把树的结构变为上图的第一种。
接着以grandfather为旋转点进行右旋。
流程图：
最后改变节点的颜色时，要注意一些细节：进行旋转操作之前，abc子树的父节点都是红色，de子树的父节点时黑色，最后旋转完之后，为了保持和原来的关系一致，grandfather节点的颜色要变红，cur的颜色变为黑色。此时的树就刚刚好满足红黑树的要求了。
情况3：cur为红，parent为红，grandfather为黑，uncle为黑或uncle不存在。parent为右孩子，uncle为左孩子。
这个情况和前面的情况2类似，只不过是旋转的方向发生了变化。具体的流程图我就不再赘述了。
代码：
//左旋
void RotateL(Node * parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
Node* pp = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
if (parent == _root)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (pp->_left == parent)
{
pp->_left = subR;
}
else
{
pp->_right = subR;
}
subR->_parent = pp;
}
}
//右旋
void RotateR(Node * parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
Node* pp = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (parent == _root)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (pp->_left == parent)
{
pp->_left = subL;
}
else
{
pp->_right = subL;
}
subL->_parent = pp;
}
}
while (parent && parent->_col == Red)//循环向上检查
{
Node* grandfather = parent->_parent;
if (parent == grandfather->_left)//parent为左孩子
{
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == Red)//情况1
{
parent->_col = Black;
uncle->_col = Black;
grandfather->_col = Red;
cur = grandfather;
parent = cur->_parent;
}
else //情况2
{
if (cur == parent->_left)
{
RotateR(grandfather);
grandfather->_col = Red;
parent->_col = Black;
}
else
{
RotateL(parent);
RotateR(grandfather);
cur->_col = Black;
grandfather->_col = Red;
}
break;
}
}
else//parent为右孩子
{
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == Red) //情况1
{
parent->_col = Black;
uncle->_col = Black;
grandfather->_col = Red;
cur = grandfather;
parent = cur->_parent;
}
else //情况3
{
if (cur == parent->_right)
{
RotateL(grandfather);
grandfather->_col = Red;
parent->_col = Black;
}
else
{
RotateR(parent);
RotateL(grandfather);
cur->_col = Black;
grandfather->_col = Red;
}
break;
}
}
}
_root->_col = Black;
return make_pair(iterator(newnode), true);
将插入位置代码与插入调整代码结合起来，就是整个插入操作的代码。其中左旋和右旋函数可以作为私有函数保护起来。
红黑树迭代器实现
迭代器的实现就是对节点的各种操作：解引用，->，++，--等。
框架
template<class T,class Ref,class Ptr> //T:数据类型 Ref：T& Ptr：T*
struct __RedBlackTreeIterator
{
typedef __RedBlackTreeIterator<T, Ref, Ptr> self;
typedef RedBlackTreeNode<T> Node;
Node* _node;
__RedBlackTreeIterator(Node* node)
:_node(node)
{}
/.../ //具体功能
}
*
返回节点数据的引用
Ref operator* ()
{
return _node->_data;
}->
返回节点数据的地址
Ptr operator->()
{
return &_node->_data;
}前置++
寻找当前节点的下一个节点（中序遍历）
有两种情况：
1.当前节点的右子树不为空，下一个节点就是当前节点的右子树的最左节点。
2.当前节点的右子树为空，说明当前节点已经是某棵子树的最右节点了，也就代表着这棵子树被访问完了，要找的节点其实是这棵子树根节点的父节点。
特点就是从当前节点一直往上查找，当节点是其父节点的左孩子时，就找到了要找的节点。这也是巧用了中序遍历的特点来进行查找。
self& operator++()
{
if (_node->_right == nullptr)//找别访问完子树的父节点
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && parent->_right == cur)
{
cur = cur->_parent;
parent = parent->_parent;
}
_node = parent;
}
else //找当前节点右子树的最左节点
{
Node* subLeft = _node->_right;
while (subLeft->_left)
{
subLeft = subLeft->_left;
}
_node = subLeft;
}
return *this;
}后置++
可以复用前置++。
self operator++(int)
{
self tmp(*this);
++(*this);
return tmp;
}前置--
和前置++的思路类似，依旧利用中序遍历的思路来分析。
有两种情况：
1.当前节点的左子树不为空，下一个节点就是当前节点的左子树的最右节点。
2.当前节点的左子树为空，说明当前节点已经是某棵子树的最左节点了，也就代表着这棵子树刚刚被访问，要找的节点其实是这棵子树根节点的父节点。
self& operator--()
{
if (_node->_left == nullptr)//情况2
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && parent->_left == cur)
{
cur = cur->_parent;
parent = parent->_parent;
}
_node = parent;
}
else //情况1
{
Node* subRight = _node->_left;
while (subRight->_right)
{
subRight = subRight->_right;
}
_node = subRight;
}
return *this;
}后置--
复用前置--
self operator--(int)
{
self tmp(*this);
--(*this);
return tmp;
}重载 != 与 ==
bool operator!=(const self& s)
{
return _node != s._node;
}
bool operator==(const self& s)
{
return _node == s._node;
}红黑树的其他函数部分模拟
iterator Begin()
{
Node* subLeft = _root;
while (subLeft->_left)
{
subLeft = subLeft->_left;
}
return iterator(subLeft);
}
iterator End()
{
return iterator(nullptr);
}
const_iterator Begin() const
{
Node* subLeft = _root;
while (subLeft->_left)
{
subLeft = subLeft->_left;
}
return const_iterator(subLeft);
}
const_iterator End() const
{
return const_iterator(nullptr);
}
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->_right;
}
else
{
return iterator(cur);
}
}
return End();
}红黑树模拟实现map
底层就是用红黑树的功能来实现
代码
template<class K, class V>
class map
{
struct MapKeyOfT //仿函数，用来取Key值
{
const K& operator()(const pair<K ,V>& kv)
{
return kv.first;
}
};
public:
typedef typename RedBlackTree<K, pair<K,V>, MapKeyOfT>::iterator iterator;
typedef typename RedBlackTree<K, pair<K, V>, MapKeyOfT>::const_iterator const_iterator;
iterator begin()
{
return _t.Begin();
}
iterator end()
{
return _t.End();
}
pair<iterator, bool> insert(const pair<K, V>& kv)
{
return _t.Insert(kv);
}
iterator find(const K& key)
{
return _t.Find(key);
}
V& operator[](const K& key) //与库中的[]功能保持一致
{
pair<iterator, bool> ret = insert(make_pair(key, V()));
return ret.first->second;
}
private:
RedBlackTree<K, pair<K, V>, MapKeyOfT> _t;
};测试
void test_map()
{
string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
"苹果", "香蕉", "苹果", "香蕉" };
map<string, int> countMap;
for (auto& str : arr)
{
countMap[str]++;
}
for (const auto& kv : countMap)
{
cout << kv.first << ":" << kv.second << endl;
}
cout << endl;
}
int main()
{
test_map();
return ;
}
红黑树模拟实现set
代码
template<class K>
class set
{
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename RedBlackTree<K, K, SetKeyOfT>::iterator iterator;
typedef typename RedBlackTree<K, K, SetKeyOfT>::const_iterator const_iterator;
iterator begin()
{
return _t.Begin();
}
iterator end()
{
return _t.End();
}
pair<iterator, bool> insert(const K& key)
{
return _t.Insert(key);
}
iterator find(const K& key)
{
return _t.Find(key);
}
private:
RedBlackTree<K, K, SetKeyOfT> _t;
};测试
void test_set()
{
set<int> s;
int a[] = { 5,7,6,3,1,4,8,9,2 };
for (auto& e : a)
{
s.insert(e);
}
for (auto& e : s)
{
cout << e << " ";
}
cout << endl;
}
int main()
{
mine::test_set();
return 0;
}
总结
讲了这么多，事实上依旧是在讲排序和搜索，红黑树的结构在这两方面都表现的不错，通过学习他们的底层实现，能够帮助我们更好的理解结构的重要性。今天的讲解就到这，我们下篇博客见😋