红黑树的概念:
红黑树,是一种二叉搜索树,但是**在每个节点上增加一个存储位表示节点的颜色,可以是red或者black。**通过对任何一条从根到叶子的路径上各个节点着色方式的限制,红黑树确保没有一条路径会比其他路径长出两倍,因而是接近平衡的。
红黑树的性质
- 每个节点不是红色就是黑色
- 根节点是黑色
- 如果一个节点是红色,则它的两个孩子节点是黑色(没有连续的两个红色节点)
- 对于每个节点,从该节点到其所有后代叶节点的简单路径上,均包含相同数目的黑色节点个数
- 每个叶子节点都是黑色
为什么满足上面的性质,红黑树就能保证,最长路径中的节点个数不会超过最短路径上节点数的两倍?
原因:因为红黑树是用颜色来保持平衡的,而且红色节点不能连续,并且从根节点到任意一个叶子节点其路径上的黑色节点个数都相等。
红黑树节点的定义
//红黑树结点的定义
template<class K, class V>
struct RBTreeNode
{
//三叉链
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
//存储的键值对
pair<K, V> _kv;
//结点的颜色
int _col; //红/黑
//构造函数
RBTreeNode(const pair<K, V>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _col(RED)
{
}
};
红黑树的插入
按照二叉搜索树规则对新节点进行插入
//插入函数
pair<Node*, bool> Insert(const pair<K, V>& kv)
{
if (_root == nullptr) //若红黑树为空树,则插入结点直接作为根结点
{
_root = new Node(kv);
_root->_col = BLACK; //根结点必须是黑色
return make_pair(_root, true); //插入成功
}
//1、按二叉搜索树的插入方法,找到待插入位置
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (kv.first < cur->_kv.first) //待插入结点的key值小于当前结点的key值
{
//往该结点的左子树走
parent = cur;
cur = cur->_left;
}
else