目录
本篇是建立在理解红黑树的插入机制上的
AVL树和红黑树的Insert(插入)(实现map.insert)-CSDN博客文章浏览阅读86次。本文介绍了C++中map、set等关联式容器的底层实现。首先探讨了二叉搜索树(BST)的缺陷，指出有序插入会导致性能退化至O(N)。为此，介绍了两种优化方案： AVL树：通过平衡因子控制，保证左右子树高度差不超过1。详细讲解了单旋（左旋、右旋）和双旋（左右、右左）的实现逻辑，以及插入后平衡因子的调整规则。 红黑树：通过颜色标记实现近似平衡，分析其5条核心规则。重点阐述了插入时的3种处理情况，以及对应的旋转和变色策略。 对比测试表明，尽管AVL树理论性能更优，但红黑树实际运行效率与之接近，且旋转次数更少，因此https://blog.csdn.net/suimingtao/article/details/148219103在上面这篇文章中，已经讲完了红黑树的实现(核心部分)，本篇将带大家以红黑树为底层实现map/set（本篇代码改造之前就是参考的上面这篇文章）
本篇只会实现一些重点接口，如迭代器，插入，[]重载等
改造RBTree.h
本次实现map/set是用的STL标准库中的思想，可以说是一种高级复用，一般来说实现map/set可能需要两颗红黑树，分别代表map和set，但这里编者会用一颗红黑树来实现map和set
先来看看STL库中定义的set和map(已经被编者简化过了)
可以看到，他们都用的同一颗二叉树，只不过在set中给红黑树的value依旧是key，而map中给红黑树的value是pair,这才是复用的是最高境界啊(感叹)。
但也因为这种程度的复用，导致红黑树的实现有许多方面都需要改
红黑树节点中存的值就是value(可能是key也可能是pair)
读者可能会发现，rb_tree的模板参数有第三个，除了KV之外，还有个KeyOfValue，这就是由于高级复用导致的问题之一：
对于set而言，value存的是key，在比较大小时可以直接比较，但对于map而言，value存的是pair，pair自带的小/大于重载是“key和value中只要有一个小/大”，即为真，因此这里的解决方案是传一个仿函数给红黑树，set中传的仿函数就是返回key本身，而map中传的仿函数是返回pair中的first值
(由于自定义的map/set可能会和STL中的重复，因此这里建议把自定义的map/set放在自定义的命名空间中)
改造后的RBTree.h
#pragma once
enum Color//红黑树的颜色
{
RED,
BLACK
};
template<class T>
struct RBTreeNode//红黑树的节点
{
//三叉链
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
Color _col;//节点的颜色
T _data;//KV模型或K模型
RBTreeNode(const T& data)//默认构造函数
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_col(RED)
,_data(data)
{}
};
template<class K,class T,class KOfT>
class RBTree//红黑树
{
typedef RBTreeNode<T> Node;
public:
bool Insert(const T& data)//红黑树的插入
{
if (_root == nullptr)//如果当前是空树，就插入到根节点中
{
_root = new Node(data);
}
else
{
Node* cur = _root;
Node* parent = nullptr;
while (cur)//找到要在哪里插入
{
if (koft(data) > koft(cur->_data))//要插入的节点比当前节点大，就去右边
{
parent = cur;
cur = cur->_right;
}
else if (koft(data) < koft(cur->_data))//要插入的节点比当前节点小，就去左边
{
parent = cur;
cur = cur->_left;
}
else//如果相等，插入失败
{
return false;
}
}
cur = new Node(data);//为该kv开辟空间
if (koft(cur->_data) > koft(parent->_data))//在parent的右边
{
parent->_right = cur;
cur->_parent = parent;
}
else//在parent的左边
{
parent->_left = cur;
cur->_parent = parent;
}
//cur->_col = RED;//默认颜色为红色
Node* grandfather = nullptr;
Node* uncle = nullptr;
while (parent && parent->_col == RED)//若父亲也是红色，此时需要调整
{
grandfather = parent->_parent;
if (grandfather->_left == parent)//若父亲在祖父的左边
{
uncle = grandfather->_right;//那叔叔就在祖父的右边
if (uncle && uncle->_col == RED)//如果叔叔为红色，就将parent和uncle置黑，grandfather置红
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//继续向上调整
cur = grandfather;
parent = cur->_parent;
}
else//走到这里说明叔叔为黑色或不存在，就要旋转，要么左右双旋
//要么右单旋，但就算是左右双旋，也是要执行一次左单旋一次右单旋，
// 所以可以先判断是否需要左右双旋，如果需要，就先左单旋一次，
// 这样即使是左右双旋的情况也可以转换成需要右单旋的情况
{
if (parent->_right == cur)//此时就要左右双旋(对于左边来说要左旋)
{
RotateL(parent);//因为双旋的第一次单旋会让cur和parent调换
//位置，所以先让parent和cur再换过来，之后再单旋就不会因为
//之前单旋过一次而出问题了
std::swap(cur, parent);
}
RotateR(grandfather);
grandfather->_col = RED;
parent->_col = BLACK;
break;
}
}
else//若父亲在祖父的右边
{
uncle = grandfather->_left;//那叔叔就在祖父的左边
if (uncle && uncle->_col == RED)//如果叔叔为红色，就将parent和uncle置黑，grandfather置红
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//继续向上调整
cur = grandfather;
parent = cur->_parent;
}
else//走到这里说明叔叔为黑色或不存在，就要旋转，要么右左双旋
//要么左单旋，但就算是右左双旋，也是要执行一次右单旋一次左单旋，
//所以可以先判断是否需要右左双旋，如果需要，就先右单旋一次，
//这样即使是右左双旋也可以转换成需要左单旋的情况
{
if (parent->_left == cur)//此时需要右左双旋(对于右边来说右边高)
{
RotateR(parent);//因为双旋的第一次单旋会让cur和parent调换
//位置，所以先让parent和cur再换过来，之后再单旋就不会因为
//之前单旋过一次而出问题了
std::swap(cur, parent);
}
RotateL(grandfather);
grandfather->_col = RED;
parent->_col = BLACK;
break;
}
}
}
}
_root->_col = BLACK;//确保最后调整完根节点是黑色
return true;
}
void RotateL(Node* parent)//左单旋
{
Node* subR = parent->_right;//右子树
Node* subRL = subR->_left;//右子树的左子树
Node* ppNode = parent->_parent;//当前根节点的父亲
//将当前根节点和左树压到subR的左树，并把原来subR的左树变成当前根节点的右树
subR->_left = parent;
parent->_parent = subR;//维护三叉链关系
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;//维护三叉链关系
//如果当前根节点就是整棵树的根，要把_root也重新指向subR
if (_root == parent)
{
_root = subR;
subR->_parent = nullptr;
}
else//当前根节点也只是个子树，就不需要重新指向_root
{
if (ppNode->_left == parent)//如果本来的根节点在它父亲的左边
ppNode->_left = subR;//就让subR到左边
else//如果本来的根节点在它父亲的右边
ppNode->_right = subR;//就让subR到右边
subR->_parent = ppNode;
}
}
void RotateR(Node* parent)//右单旋
{
Node* subL = parent->_left;//当前根节点的左子树
Node* subLR = subL->_right;//当前根节点的左子树的右子树
Node* ppNode = parent->_parent;//当前根节点的父亲
//将当前根节点和右树压到subL的右子树，并将原来subL的左树变成当前根节点的左树
subL->_right = parent;
parent->_parent = subL;//维护三叉链关系
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;//维护三叉链关系
//如果当前根节点就是整个树的根，就需要把_root重新置成subL
if (_root == parent)
{
_root = subL;
subL->_parent = nullptr;
}
else//如果当前根节点也只是一个子树，就不用改_root
{
if (ppNode->_left == parent)//如果原来的根节点在父亲的左边
ppNode->_left = subL;//就让subL去左边
else//如果原来的根节点在父亲的右边
ppNode->_right = subL;//就让subL去右边
subL->_parent = ppNode;
}
}
Node* Find(const K& key)//查找
{
Node* cur = _root;
while (cur)
{
if (key > koft(cur->_data))
cur = cur->_right;
else if (key < koft(cur->_data))
cur = cur->_left;
else
return cur;
}
return nullptr;
}
private:
Node* _root = nullptr;
KOfT koft;//用于返回K/KV模型中的K
};map.h
#pragma once
#include "RBTree.h"
namespace valkyrie
{
template<class K,class V>
class map
{
struct KeyOfMap//用于返回pair中的first
{
const K& operator()(const pair<K, V>& data)
{
return data.first;
}
};
public:
bool Insert(const pair<K, V>& data)
{
return _r.Insert(data);
}
private:
RBTree<K,pair<K,V>,KeyOfMap> _r;
};
}
set.h
#pragma once
#include "RBTree.h"
namespace valkyrie
{
template<class K>
class set
{
struct KeyOfSet//用于返回key本身(和map的KeyOfMap对应)
{
const K& operator()(const K& data)
{
return data;
}
};
public:
bool Insert(const K& data)
{
return _r.Insert(data);
}
private:
RBTree<K, K, KeyOfSet> _r;
};
}
迭代器实现：
map/set迭代器的本质就是节点指针，关键是让迭代器实现递增递减操作
定义还是在RBTree.h里(为了复用，map/set共用一个迭代器)，迭代器的模板参数即决定它是K模型还是KV模型（Ref和Ptr分别代表T类型的引用和T类型的指针，这是为了方便复用const迭代器，这种方式在list时也用过）
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)
{}
};那要怎么实现set调用解引用返回的是key，map调用解引用返回的是pair呢？
用set的迭代器解引用时候都会用*it，而用map迭代器解引用时都会用it->first，it->second，因此operator*即是set的解引用，operator->()即是map的解引用
Ref operator*()//set的解引用
{
return _node->_data;
}
Ptr operator->()//map的解引用
{
return &_node->_data;//m->first中，其实用了两次->，第一次就是取到了KV模型的地址
}这里要特别注意的是map迭代器在解引用it->first时，实际是it->->first，编译器省略了一个"->"，因此第一次"->"返回的应该是pair类型的地址
等于/不等于重载也很简单
bool operator!=(const Self& it)
{
return _node != it._node;
}
bool operator==(const Self& it)
{
return _node == it._node;
}递增递减的实现
这里才是实现的重难点
递增(operator++)
假设当前迭代器指向中序遍历的第一个节点(即1)，此时++it，如果将1看成子树的根节点，既然都访问到根了，就代表左子树已经访问完了，所以应该去该树的右子树的最左节点
再++it，此时it的右子树为空，那就需要向上走，重点在于走到哪里停住呢？
此时的parent就是迭代器递增之后的结果
由此可总结出
- 若当前节点右子树不为空，那下一个节点就是右子树的最左节点
- 若当前节点右子树为空，那下一个节点就是“祖先中第一个孩子在父亲左树” 中的父亲节点
operator++代码示例
Self& operator++()//迭代器前置++
{
if (_node->_right)//如果它的右树有节点，那下一个节点就是右树的最左节点
{
Node* subR = _node->_right;
while (subR->_left)
subR = subR->_left;
_node = subR;
}
else//如果右树没节点，那下一个节点就是“祖先中第一个孩子在父亲左树”中的父亲节点
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && parent->_right == cur)//如果此时孩子还是在父亲的右边，就继续向上
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}递减(operator--)
递减和递增逻辑相反
若再递减
由此可总结出
- 若当前节点左子树不为空，那上一个节点就是左子树的最右节点
- 若当前节点左子树为空，那上一个节点就是“祖先中第一个孩子是父亲的右树” 中的父亲节点
operator--代码示例
Self& operator--()
{
if (_node->_left)//如果左子树有节点，它的上一个就是左子树的最右节点
{
Node* subL = _node->_left;
while (subL->_right)
{
subL = subL->_right;
}
_node = subL;
}
else//如果左子树没有节点，它的上一个就是“祖先中第一个孩子在父亲右树”中的父亲节点
{
Node* parent = _node->_parent;
Node* cur = _node;
while (parent && parent->_left == cur)//如果此时孩子还是在父亲的左边，就继续向上
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}此时map/set已经支持迭代器了。那么Find函数的返回值就可以换成迭代器了
iterator Find(const K& key)//查找
{
Node* cur = _root;
while (cur)
{
if (key > koft(cur->_data))
cur = cur->_right;
else if (key < koft(cur->_data))
cur = cur->_left;
else
return iterator(cur);
}
return iterator(nullptr);
}map中[]重载实现
对map有着基本了解的读者都知道，map的[]重载是通过复用insert出来的
为了让手搓的map也支持[]重载，需要先改装一下现在的insert，使它的返回值为pair<iterator,bool>
pair<iterator,bool> Insert(const T& data)//红黑树的插入
{
Node* newnode;//最后返回该值
if (_root == nullptr)//如果当前是空树，就插入到根节点中
{
_root = new Node(data);
newnode = _root;
}
else
{
Node* cur = _root;
Node* parent = nullptr;
while (cur)//找到要在哪里插入
{
if (koft(data) > koft(cur->_data))//要插入的节点比当前节点大，就去右边
{
parent = cur;
cur = cur->_right;
}
else if (koft(data) < koft(cur->_data))//要插入的节点比当前节点小，就去左边
{
parent = cur;
cur = cur->_left;
}
else//如果相等，插入失败
{
return make_pair(cur,false);
}
}
cur = new Node(data);//为该kv开辟空间
newnode = cur;
if (koft(cur->_data) > koft(parent->_data))//在parent的右边
{
parent->_right = cur;
cur->_parent = parent;
}
else//在parent的左边
{
parent->_left = cur;
cur->_parent = parent;
}
//cur->_col = RED;//默认颜色为红色
Node* grandfather = nullptr;
Node* uncle = nullptr;
while (parent && parent->_col == RED)//若父亲也是红色，此时需要调整
{
grandfather = parent->_parent;
if (grandfather->_left == parent)//若父亲在祖父的左边
{
uncle = grandfather->_right;//那叔叔就在祖父的右边
if (uncle && uncle->_col == RED)//如果叔叔为红色，就将parent和uncle置黑，grandfather置红
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//继续向上调整
cur = grandfather;
parent = cur->_parent;
}
else//走到这里说明叔叔为黑色或不存在，就要旋转，要么左右双旋
//要么右单旋，但就算是左右双旋，也是要执行一次左单旋一次右单旋，
// 所以可以先判断是否需要左右双旋，如果需要，就先左单旋一次，
// 这样即使是左右双旋的情况也可以转换成需要右单旋的情况
{
if (parent->_right == cur)//此时就要左右双旋(对于左边来说要左旋)
{
RotateL(parent);//因为双旋的第一次单旋会让cur和parent调换
//位置，所以先让parent和cur再换过来，之后再单旋就不会因为
//之前单旋过一次而出问题了
std::swap(cur, parent);
}
RotateR(grandfather);
grandfather->_col = RED;
parent->_col = BLACK;
break;
}
}
else//若父亲在祖父的右边
{
uncle = grandfather->_left;//那叔叔就在祖父的左边
if (uncle && uncle->_col == RED)//如果叔叔为红色，就将parent和uncle置黑，grandfather置红
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//继续向上调整
cur = grandfather;
parent = cur->_parent;
}
else//走到这里说明叔叔为黑色或不存在，就要旋转，要么右左双旋
//要么左单旋，但就算是右左双旋，也是要执行一次右单旋一次左单旋，
//所以可以先判断是否需要右左双旋，如果需要，就先右单旋一次，
//这样即使是右左双旋也可以转换成需要左单旋的情况
{
if (parent->_left == cur)//此时需要右左双旋(对于右边来说右边高)
{
RotateR(parent);//因为双旋的第一次单旋会让cur和parent调换
//位置，所以先让parent和cur再换过来，之后再单旋就不会因为
//之前单旋过一次而出问题了
std::swap(cur, parent);
}
RotateL(grandfather);
grandfather->_col = RED;
parent->_col = BLACK;
break;
}
}
}
}
_root->_col = BLACK;//确保最后调整完根节点是黑色
return make_pair(newnode,true);
}因此map，set中的Insert返回值也需要改
pair<iterator,bool> Insert(const pair<K, V>& data)
{
return _r.Insert(data);
}pair<iterator,bool> Insert(const K& data)
{
return _r.Insert(data);
}当执行m["目标值"]++时， insert无论插入失败还是成功，都会返回key为目标值的迭代器，如果插入成功，此时的value为0，++后就会变成1；如果插入失败，此时的value也会被++
V& operator[](const K& key)
{
//不管插入成功还是失败，pr.first都为key值的迭代器，此时只要返回该迭代器的value就可以
pair<iterator, bool> pr = Insert(make_pair(key,V()));
return pr.first->second;
}