红黑树的概念回顾
红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red（红色）或Black（黑色）。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。（平衡的概念可参考AVL树，AVL树是一个高度平衡二叉搜索树，其左右子树的高度差不超过1）
见图
?引发的疑问：
如何保证没有一条路径会比其他路径长出俩倍呢？只需满足红黑树的性质便可保证
红黑树的性质
- 每个结点不是红色就是黑色
- 根节点是黑色的
- 如果一个节点是红色的，则它的两个孩子结点是黑色的（即树中没有连续的红节点）
- 对于每个结点，从该结点到其所有后代空结点的简单路径上，均包含相同数目的黑色结点
?特别提醒：
关于空节点有多种处理方式，有的将其称呼为外部节点，有的将其命名为叶子节点
这里还是称其为空节点。
关于路径数量的统计：
?
?NIL表示空节点，从根节点开始到其所有后代空结点一共有12条路径（这里画上空节点只是为了
方便计算路径，没有其它含义）
红黑树的模拟实现
?1、颜色的实现
根据性质1，红黑树中节点要么是黑的要么是红的，因此这里使用枚举来表示颜色
?
根据枚举的性质，BLACK==0，RED==1。
2、定义节点结构
?键值对
键值对的意思是一个K对于一个V，这里用pair<K,V>定义出一个对象_kv，那么如何通过_kv取出K，以及对应的V呢，
?
?pair类模板提供两个成员变量，一个是first,一个是second，可以通过_kv.first
以及_kv.second来使用，其中_kv.first对应K，_kv.second对应V
可以默认给新增节点置黑吗
置红破坏了性质3，即可能会出现相连的红节点
置黑则一定会破坏性质4，即每条路径上的黑节点不一样，因为新增节点所在的路径黑节点多了一个。
通过以上对比发现置红有时候不一定会破坏红黑树的性质，而且只会影响这一条路径上的
而置黑则一定会破坏性质4，在调整红黑树的结构过程中需要从新计算每条路径上的黑节点以保证性质4，可见给新增节点默认置红是比较好的选择。
3、迭代器的定义
template<class K, class V, class Ref, class Ptr>
class IteratorRBTree
{
friend class RBTree<K, V>;
typedef RBTreeNode<K, V> Node;
typedef IteratorRBTree<K, V, Ref, Ptr> Self;
public:
IteratorRBTree(Node* node)
:_node(node)
{}
//迭代器的六大操作*.->,++,--,!=,==
Ref operator*()//Ref表示_kv的引用
{
return _node->_kv;
}
Ptr operator->()//Ptr表示_kv的地址
{
return &_node->_kv;
}
Self& operator++()//前置++(找右边最小的)
{
if (_node->_right != nullptr)
{
Node* cur = _node->_right;
while (cur->_left)
{
cur = cur->_left;
}
_node = cur;
}
else if (_node->_right == nullptr)
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent&&parent->_right == cur)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}
Self operator++(int)//后置++
{
Self tmp(_node);
++*this;
return tmp;
}
//因为将end()记为空指针，因此无法实现自减
bool operator==(const Self<)
{
return _node == lt._node;
}
bool operator!=(const Self<)
{
return !(*this == lt);
}
private:
Node* _node;
};4、红黑树的整体实现
#pragma once
#include <iostream>
#include <string>
#include<utility>
#include<algorithm>
using namespace std;
namespace my_std1
{
enum Color
{
BLACK
, RED
};
template<class K, class V>//使用模板，并且采用键值对的方式
struct RBTreeNode
{
//使用三叉链，方便寻找其双亲以及左右孩子
RBTreeNode*_parent;
RBTreeNode*_left;
RBTreeNode*_right;
Color _col;//定义枚举变量_col，_col用来表示该节点的颜色
pair<K, V> _kv;//C++中用pair类模板管理键值对
//其头文件为<utility>
RBTreeNode(const pair<K, V>&kv)
:_parent(nullptr)//使用初始化列表初始化
, _left(nullptr)
, _right(nullptr)
, _col(RED)//默认将节点颜色给红
, _kv(kv)
{}
};
template<class K, class V>//前置声明
class RBTree;
template<class K, class V, class Ref, class Ptr>
class IteratorRBTree
{
friend class RBTree<K, V>;
typedef RBTreeNode<K, V> Node;
typedef IteratorRBTree<K, V, Ref, Ptr> Self;
public:
IteratorRBTree(Node* node)
:_node(node)
{}
//迭代器的六大操作*.->,++,--,!=,==
Ref operator*()
{
return _node->_kv;
}
Ptr operator->()
{
return &_node->_kv;
}
Self& operator++()//前置++(找右边最小的)
{
if (_node->_right != nullptr)
{
Node* cur = _node->_right;
while (cur->_left)
{
cur = cur->_left;
}
_node = cur;
}
else if (_node->_right == nullptr)
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent&&parent->_right == cur)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}
Self operator++(int)//后置++
{
Self tmp(_node);
++*this;
return tmp;
}
//因为将end()记为空指针，因此无法实现自减
bool operator==(const Self<)
{
return _node == lt._node;
}
bool operator!=(const Self<)
{
return !(*this == lt);
}
private:
Node* _node;
};
template<class K, class V>
class RBTree
{
public:
typedef RBTreeNode<K, V> Node;
typedef IteratorRBTree<K, V, const pair<K, V>&, const pair<K, V>*> Iterator;
pair<Iterator, bool> Insert(const pair<K, V>&kv)
{
//先按照搜索树的规则进行插入
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = BLACK;//根给黑
/*pair<Iterator, bool> tmp;
tmp.first = Iterator(_root);
tmp.second = true;
return tmp;*/
//return make_pair<Iterator(_root), true>;
return pair<Iterator, bool>(Iterator(_root), true);
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (kv.first < cur->_kv.first)
{
parent = cur;
cur = cur->_left;
}
else if (kv.first > cur->_kv.first)
{
parent = cur;
cur = cur->_right;
}
else
{
return make_pair(Iterator(cur), false);
}
}
//找到了要插入的地方
cur = new Node(kv);
cur->_parent = parent;
if (kv.first < parent->_kv.first)
parent->_left = cur;
else if (kv.first > parent->_kv.first)
parent->_right = cur;
//更新颜色
//_root的颜色要保证为黑色
while (parent&&parent->_col == RED)//从上面下来的parent不可能为_root
//但是下面的往上更新可能会更到_root以及_root的parent
{
Node*grandfather = parent->_parent;
if (grandfather->_left == parent)
{
Node*uncle = grandfather->_right;
if (uncle&&uncle->_col == RED)//叔叔存在且为红
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//继续往上更新
cur = grandfather;
parent = grandfather->_parent;
}
else //叔叔不存在或者叔叔存在且为黑
{
if (parent->_right == cur)
{
RotateL(parent);
std::swap(cur, parent);//深拷贝还是浅拷贝？仅仅是交换两个指针
}
RotateR(grandfather);
parent->_col = BLACK;
cur->_col = grandfather->_col = RED;
}
}
else if (grandfather->_right == parent)
{
Node*uncle = grandfather->_left;
if (uncle&&uncle->_col == RED)//叔叔存在且为红
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//继续往上更新
cur = grandfather;
parent = grandfather->_parent;
}
else //叔叔不存在或者叔叔存在且为黑
{
if (parent->_left == cur)
{
RotateR(parent);
std::swap(cur, parent);
}
RotateL(grandfather);
parent->_col = BLACK;
cur->_col = grandfather->_col = RED;
}
}
_root->_col = BLACK;//不可以用parent去判断是否与_root相等
//然后将parent->_col变黑，因为parent可能为空，而此时_root中
//节点颜色为红色(在叔叔存在且为红时向上更新出现的,当插入9时就发生这种情况)
}
return make_pair(Iterator(cur), true);
}
void RotateL(Node* parent)
{
Node*SubR = parent->_right;
Node*SubRL = SubR->_left;
if (_root != parent)
{
Node* GrandFather = parent->_parent;
if (GrandFather->_left == parent)
{
GrandFather->_left = SubR;
}
else if (GrandFather->_right == parent)
{
GrandFather->_right = SubR;
}
SubR->_parent = GrandFather;
}
else
{
_root = SubR;//给新的根
SubR->_parent = nullptr;
}
parent->_right = SubRL;
if (SubRL)//要判空
SubRL->_parent = parent;
SubR->_left = parent;
parent->_parent = SubR;
}
void RotateR(Node* parent)
{
Node* SubL = parent->_left;
Node* SubLR = SubL->_right;
if (_root != parent)
{
Node*GrandFather = parent->_parent;
if (GrandFather->_left == parent)
GrandFather->_left = SubL;
else if (GrandFather->_right == parent)
GrandFather->_right = SubL;
SubL->_parent = GrandFather;
}
else
{
_root = SubL;
SubL->_parent = nullptr;
}
parent->_left = SubLR;
if (SubLR)
{
SubLR->_parent = parent;
}
SubL->_right = parent;
parent->_parent = SubL;
}
Iterator begin()//从最小的元素开始
{
Node* cur = _root;
while (cur->_left)
{
cur = cur->_left;
}
return cur;
}
Iterator end()//将结束状态记为空指针，只有_root的parent为空
{
return Iterator(nullptr);
}
void _InOrde(Node *root)
{
if (root == nullptr)
return;
_InOrde(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
_InOrde(root->_right);
}
void InOrde()
{
_InOrde(_root);
}
Iterator Find(const K&k)
{
Node*cur = _root;
while (cur)
{
if (k > cur->_kv.first)
cur = cur->_right;
else if (k < cur->_kv.first)
cur = cur->_left;
else
return Iterator(cur);
}
return Iterator(nullptr);
}
private:
bool _IsValidRBTree(Node*root, size_t k, const size_t &BlackCout)
{
if (root == nullptr)//判断一条路径上的黑色节点数是否相同
{
if (k != BlackCout)
return false;
else if (k == BlackCout)
return true;
}
if (root->_col == BLACK)//累计黑色节点数
++k;
//判断子类是否与双亲的颜色都为红色
Node*parent = root->_parent;
if (parent&&root->_col == RED && parent->_col == RED)
return false;
return _IsValidRBTree(root->_left, k, BlackCout)&
_IsValidRBTree(root->_right, k, BlackCout);
}
public:
bool IsValidRBTree()
{
//空也是红黑树
if (_root == nullptr)
return true;
//检查根是否为黑色
else if (_root->_col == RED)
return false;
else
{
//检查是否满足红黑树的性质
//先获取任意一条路径黑色节点的个数
size_t BlackCout = 0;//记录该路径上黑色节点的个数
Node* cur = _root;
while (cur)
{
if (cur->_col == BLACK)
BlackCout++;
cur = cur->_left;
}
//开始检查
size_t k = 0;//递归每一层会自己记录其对应K的值
return _IsValidRBTree(_root, k, BlackCout);//会生成k的拷贝
//每一层都有一个地址不一样的k
}
}
private:
Node*_root = nullptr;
};
void test1_rbtree()//测试函数
{
RBTree<string, string>rt;
rt.Insert(make_pair("sort", "排序"));
rt.Insert(make_pair("left", "左边"));
rt.Insert(make_pair("right", "右边"));
rt.InOrde();
cout << endl;
cout << rt.begin()->first << ":" << rt.begin()->second << endl;
}
void test2_rbtree()//测试函数
{
RBTree<int, int>rt;
int arr[] = { 3,5,2,9,7,13,11,19,20,17,1 };
int sz = sizeof(arr) / sizeof(arr[0]);
for (auto e : arr)
{
pair<RBTree<int, int>::Iterator, bool>p = rt.Insert(make_pair(e, e));
cout << p.first->first << ":" << p.first->second << " bool:" << p.second << endl;
}
pair<RBTree<int, int>::Iterator, bool>p = rt.Insert(make_pair(6, 6));
cout << p.first->first << ":" << p.first->second << " bool:" << p.second << endl;
cout << endl;
rt.InOrde();
cout << endl;
auto it = rt.begin();
for (int i = 0; i < sz; i++)
{
//auto lt=++it;
auto lt = it++;
cout << lt->first << ":" << lt->second << endl;
}
cout << endl;
for (auto e : rt)
{
cout << e.first << ":" << e.second << endl;
}
auto lt = rt.Find(6);
if (lt != rt.end())
{
cout << lt->first << ":" << lt->second << endl;
}
cout << rt.IsValidRBTree() << endl;
}
}