STL之红黑树的模拟实现
红黑树的概念
红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或 Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，==红黑树确保没有一条路径会比其他路径长出俩倍==，因而是==接近平衡==的。
==意思就是最长路径不超过最短路径的二倍！==
相比AVL树，红黑树只是接近平衡！AVL树已经是二叉搜索树能解决的最严格的平衡！
红黑树的性质
- 每个结点不是红色就是黑色
- 根节点是黑色的
- 如果一个节点是红色的，则它的两个孩子结点是黑色的
- 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点*
- 每个叶子结点都是黑色的(此处的叶子结点指的是空结点
第一点和第二点就是简单规则
==第三点要注意！如果反过来说，如果一个结点是黑的，那么它的两个子结点一定是红的！这是错的！==
这也是一个红黑树！是完全符合上面的定义的！
第三点保证的是没有连续的红色节点！
第四点保证的是每条路径上包含相同数量的黑色节点！
==前四点保证了最长路径一定不会超过最短路径的两倍！==——这个是保证不超过两倍！
==第五点——将叶子节点（空节点）都定义为黑色节点！就保证了即使是最长路径也不会比最短路径长两倍！==——这个是保证达不到两倍
==这样子黑色节点永远比黑色节点多出一个！==
==关于近似平衡==
最优情况:全黑或 每条路径都是一黑一红相间的路径就是都是 ==满二叉树！(此时左右最平衡)==
最差情况:每一颗子树都满足==左子树全黑，右子树一黑一红！==（此时左右嘴不平衡！）
==例如这个红黑树！==
全黑的路径长度是 h ($log_2(N)$)——2^h^ - 1 = N(全结点数)
最长的路径 2*h （$log_2(N)$）
==红黑树的效率严格来说是没有AVL树好的！==
但是其实也影响不大！
==例如10亿个数据！放在AVL树上就是30次！而放在红黑树上 可能最坏的情况要搜索60次！——但是这个影响很大吗？对于CPU来说无论是30和60其实都是一个数量级！影响很小！==
那么红黑树究竟比AVL优秀在哪里呢？搜索的时候，插入的时候其实效率并不比AVL高上多少！——因为红黑树是近似平衡！而AVL树是严格平衡！
AVL树的严格平衡是==通过频繁的旋转==来达到的！——旋转也是要付出性能代价的！
而红黑树的相比AVL树有着==更少的旋转！==——而性能就是从这一部分的旋转节约下来的！
红黑树的模拟实现
红黑数的节点
namespace MySTL { enum Color { RED, BLACK }; template<class K,class V> struct RBTreeNOde { typedef RBTreeNOde<K,V> Node; RBTreeNOde(const std::pair<K,V>& kv) :_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_color(RED) ,_kv(kv) {} Node* _left; Node* _right; Node* _parent; std::pair<K,V> _kv; Color _color; }; }
红黑树的成员变量
namespace MySTL { template<class K,class V> class RBTree { typedef RBTreeNOde<K,V> Node; RBTree() :_root(nullptr) {} private: Node* _root; }; }
insert
节点插入操作
namespace MySTL { template<class K,class V> class RBTree { typedef RBTreeNOde<K,V> Node; public: bool insert(const std::pair<K,V>& kv) { if(nullptr) { _root = new Node(kv); _root->_color = BLACK;//根节点必须是黑色 return true; } Node* cur = _root; Node* parent = nullptr; 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); cur->_color = RED;//新插入的节点必须是红色 //为什么新插入的节点必须是红色？ //因为如果新插入的节点是黑色，那么就是冒着违法所有路径上黑节点个数相同这个规则的风险 //如果插入的节点是红色，就可能是冒着违法红节点不能相邻这个规则的风险的风险 //相比黑色，红色的风险更小 //因为我们在任意一个位置插入黑色我们一定违背了每个路径黑色节点个数要相同的规则——一定会有一个路径黑色节点个数比其他路径多1 //而我们还很难处理这个问题 //但是如果我们插入红色，我们只有在插入的位置的父节点是红色的时候才会违背红节点不能相邻的规则——如果父亲是黑的！那么就是直接结束了 //如果插入是红色我们可以通过旋转来解决这个问题 if(parent->_kv.first > kv.first) { parent->_left = cur; } else { parent->_right = cur; } } //插入成功！ private: Node* _root; }; }
插入后检查红黑数性质是否遭到破坏！
因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何 性质，则不需要调整.
但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连 在一起的红色节点，此时需要对红黑树分情况来讨论：
情况一——不进行旋转！只变色！
==cur为红色，p为红色，g为黑色，u为红色==——==关键点其实是u节点！==
==情况一向上调整后也可能重新变成情况一==
==处理方式也是同样的==
==a\b\c\d\e是一个抽象图代表了无数多种情况！下面给有几个例子帮助来理解什么是抽象图==
==如果有两个节点及其以上那么就会更加的复杂——光是一个黑色节点的在不插入的时候就有4 * 4 *4 = 64种情况！所以这就是为什么我们需要抽象图来进行表示==
如果算插入后的情况那会更加的复杂！
情况一——代码实现
while (parent && parent->_color == RED)//父节点颜色是红色的那么就要进行处理！
{
//parent不可能是根！因为根节点是黑色的
//所以不用担心grandfather为空的情况
Node *grandfather = parent->_parent;//祖父节点
Node *uncle = nullptr;//叔叔节点
if (grandfather->_left == parent)//左右情况分别处理,叔叔节点为右子树
{
uncle = grandfather->_right;
//情况1，叔叔节点是红色
if (uncle && uncle->_color == RED)//存在且是红色
{
//此时我们只需要将父节点和叔叔节点变成黑色，祖父节点变成红色
uncle->_color = BLACK;
parent->_color = BLACK;
grandfather->_color = RED;
//此时我们需要将cur指向grandfather，然后继续向上判断
cur = grandfather;
parent = cur->_parent;
//为什么要怎么写可以看上面的情况一变成情况一的流程图
}
else
{
//....
}
}
else//叔叔节点左子树
{
uncle = grandfather->_left;
//情况1，叔叔节点是红色
if (uncle && uncle->_color == RED)
{
uncle->_color = BLACK;
parent->_color = BLACK;
grandfather->_color = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{
//.....
}
}
}
情况二——只进行单旋
==cur为红色，p为红色，g为黑色，u不存在或者存在但是为黑色==——==同样关键点是u节点！==
我们可以看看下面的具体情况
==处理办法==
当出现连续的红结点，而且叔叔节点又不存在或者是黑色！——==重点就是将父节点变黑==
==重点就是旋转（以g为轴心）+变色！==
旋转是用来压低树的高度的！
**==无论是情况1还是情况2我们都是对p，g，u这三个节点进行操作！== **
情况二——代码实现
while(parent && parent->_color == RED)//父节点颜色是红色的那么就要进行处理！
{
//parent不可能是根！因为根节点是黑色的
//所以不用担心grandfather为空的情况
Node *grandfather = parent->_parent;//祖父节点
Node *uncle = nullptr;//叔叔节点
if (grandfather->_left == parent)//左右情况分别处理,叔叔节点为右子树
{
uncle = grandfather->_right;
if (uncle && uncle->_color == RED)//存在且是红色
{
//情况1，叔叔节点是红色
}
else
{
//情况2，叔叔节点是黑色或者不存在,cur是parent的左子树
if (cur == parent->_left)
{
//此时我们只需要将parent变成黑色，grandfather变成红色
//然后对grandfather进行右旋
RotateR(grandfather);
parent->_color = BLACK;
grandfather->_color = RED;
//旋转完毕之后就结束了！
//因为我们已经将grandfather变成了红色，而grandfather的父节点（也就是parent）是黑色的，
//不会对上面的节点造成影响所以可以直接退出！
break;
}
else
{
}
}
}
else//叔叔节点左子树
{
uncle = grandfather->_left;
//情况1，叔叔节点是红色
if (uncle && uncle->_color == RED)
{
//......
}
else
{
// g
// p
// u
//情况2，叔叔节点是黑色或者不存在,cur是parent的右子树
if (cur == parent->_right)
{
//此时我们只需要将parent变成黑色，grandfather变成红色
//然后对grandfather进行左旋
RotateL(grandfather);
parent->_color = BLACK;
grandfather->_color = RED;
break;
}
else
{
}
}
}
}
#pragma once #include <iostream> namespace MySTL { template<class K,class V> class RBTree { typedef RBTreeNode<K,V> Node; private://左单旋 void RotateL(Node* parent) { Node* subR = parent->_right;//父节点的右子节点 Node* subRL = subR->_left;//右子节点的左子节点 //让右孩子的左节点成为parent的右节点！ parent->_right = subRL; //有3个节点_parent需要进行更新！ //以及一个节点的子节点需要进行更新！ if (subRL) subRL->_parent = parent;//如果右子节点的左子节点不是一个空节点！那么它的parent也要更新！ Node* ppNode = parent->_parent; if (ppNode) //如果这个颗树是一个子树！那么要跟更新parent的父节点的子节点！ { if (ppNode->_left == parent) ppNode->_left = subR; else ppNode->_right = subR; } else { _root = subR;//如果不是一个子树，那么subR此时就是根！ } //更新subR的父节点！ subR->_parent = ppNode; //让parent 成为右子节点的左节点 subR->_left = parent; //此时parent是subR的左节点！ parent->_parent = subR; } void RotateR(Node* parent)//右单旋 { Node* subL = parent->_left;//父节点的左子节点 Node* subLR = subL->_right;//父节点的左子节点的右子节点 //将父节点的左子节点的右子节点变成父节点的新左子节点！ parent->_left = subLR; //将父节点的原左子节点的右子节点的父节点进行更新为parent if (subLR) subLR->_parent = parent; //更新parent的父节点该指向的新节点！ Node* ppNode = parent->_parent; if (ppNode) { //改树是一个子树 //将ppNode指向新的子树根节点！ if (ppNode->_left == parent) ppNode->_left = subL; else ppNode->_right = subL; } else { //如果不是子树，直接更新，新的根节点 _root = subL; } //更新原父节点的左子节点的父节点 subL->_parent = ppNode; //将父节点变成原父节点的左子节点的右节点！ subL->_right = parent; //将父节点的父节点进行更新 parent->_parent = subL; } private: Node* _root; }; }
情况三——要进行双旋
==cur为红色，p为红色，g为黑色，u不存在或者存在但是为黑色==——和情况2相比！情况3的cur与p和g是一个折线，而情况2是一个直线！
==如果cur是在右子树！u在左子树！我们要先右单旋！再左单旋==
情况三——代码实现
while (parent && parent->_color == RED)//父节点颜色是红色的那么就要进行处理！
{
//parent不可能是根！因为根节点是黑色的
//所以不用担心grandfather为空的情况
Node *grandfather = parent->_parent;//祖父节点
Node *uncle = nullptr;//叔叔节点
if (grandfather->_left == parent)//左右情况分别处理,cur是parent的右子树
{
uncle = grandfather->_right;
if (uncle && uncle->_color == RED)//存在且是红色
{
//情况1，叔叔节点是红色
//....
}
else
{
//情况2，叔叔节点是黑色或者不存在,cur是parent的左子树
if (cur == parent->_left)
{
//情况2
//....
}
else
{
//情况3，cur是parent的右子树
//此时我们需要对parent进行左旋，然后再对grandfather进行右旋
RotateL(parent);
RotateR(grandfather);
grandfather->_color = RED;
cur->_color = BLACK;
//与情况2的理由是一样的！因为第一次左旋之后就变成了清空2！
break;
}
}
}
else//叔叔节点左子树
{
uncle = grandfather->_left;
//情况1，叔叔节点是红色
if (uncle && uncle->_color == RED)
{
//....
}
else
{
//情况2，叔叔节点是黑色或者不存在,cur是parent的右子树
if (cur == parent->_right)
{
//...
}
else//情况3
{
// g
// p
// u
//此时我们需要对parent进行右旋，然后再对grandfather进行左旋
RotateR(parent);
RotateL(grandfather);
grandfather->_color = RED;
cur->_color = BLACK;
break;
}
}
}
}
总结
无论是情况1,2,3其实重点就是看叔叔节点！——先看叔叔节点的颜色！颜色为红就是情况1
颜色为黑或者不存在就是情况2或者3！，其次看叔叔节点的位置！
==而且情况1,2的时候父亲都要变黑！情况3是cur要变黑！==
==我们可以发现无论是情况1，2，3，都可以从情况1变化过来的！==
insert代码总体实现
#pragma once
#include <iostream>
namespace MySTL
{
enum Color
{
RED,
BLACK
};
template<class K,class V>
struct RBTreeNode
{
typedef RBTreeNode<K,V> Node;
RBTreeNode(const std::pair<K,V>& kv)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_color(RED)
,_kv(kv)
{}
Node* _left;
Node* _right;
Node* _parent;
std::pair<K,V> _kv;
Color _color;
};
template<class K,class V>
class RBTree
{
typedef RBTreeNode<K,V> Node;
public:
bool insert(const std::pair<K,V>& kv)
{
if(_root == nullptr)
{
_root = new Node(kv);
_root->_color = BLACK;//根节点必须是黑色
return true;
}
Node* cur = _root;
Node* parent = nullptr;
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);
cur->_color = RED;//新插入的节点必须是红色
//为什么新插入的节点必须是红色？
//因为如果新插入的节点是黑色，那么就是冒着违法所有路径上黑节点个数相同这个规则的风险
//如果插入的节点是红色，就可能是冒着违法红节点不能相邻这个规则的风险的风险
//相比黑色，红色的风险更小
//因为我们在任意一个位置插入黑色我们一定违背了每个路径黑色节点个数要相同的规则——一定会有一个路径黑色节点个数比其他路径多1
//而我们还很难处理这个问题
//但是如果我们插入红色，我们只有在插入的位置的父节点是红色的时候才会违背红节点不能相邻的规则——如果父亲是黑的！那么就是直接结束了
//如果插入是红色我们可以通过旋转来解决这个问题
if(parent->_kv.first > kv.first)
{
parent->_left = cur;
cur->_parent = parent;
}
else
{
parent->_right = cur;
cur->_parent = parent;
}
//插入完成之后，我们需要调整树的结构
while(parent && parent->_color == RED)//父节点颜色是红色的那么就要进行处理！如果是根节点就退出！
{
//parent不可能是根！因为根节点是黑色的
//所以不用担心grandfather为空的情况
Node* grandfather = parent->_parent;//祖父节点
Node* uncle = nullptr;//叔叔节点
if(grandfather->_left == parent)//左右情况分别处理,叔叔节点为右子树
{
uncle = grandfather->_right;
if(uncle && uncle->_color ==RED)//存在且是红色
{
//情况1，叔叔节点是红色
//此时我们只需要将父节点和叔叔节点变成黑色，祖父节点变成红色
uncle->_color = BLACK;
parent->_color = BLACK;
grandfather->_color = RED;
//此时我们需要将cur指向grandfather，然后继续向上判断
cur = grandfather;
parent = cur->_parent;
//为什么要怎么写可以看上面的情况一变成情况一的流程图
}
else
{
//情况2，叔叔节点是黑色或者不存在,cur是parent的左子树
if(cur == parent->_left)
{
//此时我们只需要将parent变成黑色，grandfather变成红色
//然后对grandfather进行右旋
RotateR(grandfather);
parent->_color = BLACK;
grandfather->_color = RED;
//旋转完毕之后就结束了！
//因为我们已经将grandfather变成了红色，而grandfather的父节点是黑色的
//不会对上面的节点造成影响
break;
}
else
{
//情况3，cur是parent的右子树
//此时我们需要对parent进行左旋，然后再对grandfather进行右旋
RotateL(parent);
RotateR(grandfather);
grandfather->_color = RED;
cur->_color = BLACK;
break;
}
}
}
else//叔叔节点左子树
{
uncle = grandfather->_left;
//情况1，叔叔节点是红色
if(uncle && uncle->_color == RED)
{
uncle->_color = BLACK;
parent->_color = BLACK;
grandfather->_color = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{
//情况2，叔叔节点是黑色或者不存在,cur是parent的右子树
if(cur == parent->_right)
{
//此时我们只需要将parent变成黑色，grandfather变成红色
//然后对grandfather进行左旋
RotateL(grandfather);
parent->_color = BLACK;
grandfather->_color = RED;
break;
}
else//情况3，cur是parent的左子树
{
//此时我们需要对parent进行右旋，然后再对grandfather进行左旋
RotateR(parent);
RotateL(grandfather);
grandfather->_color = RED;
cur->_color = BLACK;
break;
}
}
}
}
_root->_color = BLACK;//根节点必须是黑色
return true;
}
private:
void RotateL(Node* parent)
{
Node* subR = parent->_right;//父节点的右子节点
Node* subRL = subR->_left;//右子节点的左子节点
//让右孩子的左节点成为parent的右节点！
parent->_right = subRL;
//有3个节点_parent需要进行更新！
//以及一个节点的子节点需要进行更新！
if (subRL)
subRL->_parent = parent;//如果右子节点的左子节点不是一个空节点！那么它的parent也要更新！
Node* ppNode = parent->_parent;
if (ppNode) //如果这个颗树是一个子树！那么要跟更新parent的父节点的子节点！
{
if (ppNode->_left == parent)
ppNode->_left = subR;
else
ppNode->_right = subR;
}
else
{
_root = subR;//如果不是一个子树，那么subR此时就是根！
}
//更新subR的父节点！
subR->_parent = ppNode;
//让parent 成为右子节点的左节点
subR->_left = parent;
//此时parent是subR的左节点！
parent->_parent = subR;
}
void RotateR(Node* parent)
{
Node* subL = parent->_left;//父节点的左子节点
Node* subLR = subL->_right;//父节点的左子节点的右子节点
//将父节点的左子节点的右子节点变成父节点的新左子节点！
parent->_left = subLR;
//将父节点的原左子节点的右子节点的父节点进行更新为parent
if (subLR)
subLR->_parent = parent;
//更新parent的父节点该指向的新节点！
Node* ppNode = parent->_parent;
if (ppNode)
{
//改树是一个子树
//将ppNode指向新的子树根节点！
if (ppNode->_left == parent)
ppNode->_left = subL;
else
ppNode->_right = subL;
}
else
{
//如果不是子树，直接更新，新的根节点
_root = subL;
}
//更新原父节点的左子节点的父节点
subL->_parent = ppNode;
//将父节点变成原父节点的左子节点的右节点！
subL->_right = parent;
//将父节点的父节点进行更新
parent->_parent = subL;
}
private:
Node* _root;
};
}
红黑树插入代码测试
检验红黑树不能去看树的高度！我们要从规则入手,分别检验这四个规则是否一一符合！
namespace MySTL { enum Color { RED, BLACK }; template<class K,class V> struct RBTreeNode { typedef RBTreeNode<K,V> Node; RBTreeNode(const std::pair<K,V>& kv) :_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_color(RED) ,_kv(kv) {} Node* _left; Node* _right; Node* _parent; std::pair<K,V> _kv; Color _color; }; template<class K,class V> class RBTree { typedef RBTreeNode<K,V> Node; public: bool Isbalance() { //不能通过树的高度来判断是否是红黑树 //空树也是红黑树 if(_root == nullptr) return true; //判断等于没有意义！因为即使相等也不一定是平衡的！ //不是红的就是黑的我们不用检查因为枚举就已经保证了！ if(_root->_color != BLACK) return false; //检查黑节点的个数是否相同！ //先随便求一条的黑节点的个数 //然后去进行一次递归遍历！每次遇到黑色节点就+1，等到终点的时候，就判断一下，这个路径的黑色节点数和我们的开始算的那条路径是否相同！ int black = 0; Node* cur = _root; while(cur) { if(cur->_color == BLACK) black++; cur = cur->_left; }//计算出了一条路径的黑色节点的个数！ //我们可以将判断连续的红节点的函数和这个函数合并！ //因为我们只需要遍历一次树就可以了！ return check(_root,0,black); } private: bool check(Node* root,int blacksum,const int& ref) { if(root == nullptr) { if(blacksum != ref) { std::cout << "黑节点的个数不相同" << std::endl; return false; } return true; } //遇到黑色节点就+1 if(root->_color == BLACK) blacksum++; //检查连是否有连续的红节点！ //对整个树进行遍历！ //我们最好去检查一个节点的父亲！ //因为检查一个节点的子节点，我们还得去判断是不是个空节点！ //如果这个节点是红色！那么就检查它的父节点是不是红色的！ if(root->_color == RED && root->_parent->_color == RED) { std::cout << "连续的红节点" << std::endl; return false; } return check(root->_left,blacksum,ref) && check(root->_right,blacksum,ref); } private: Node* _root; }; }==如何验证求每一个路径的黑色节点相同？==
先随便一条路径的黑色节点！
然后去进行一次递归遍历！每次遇到黑色节点就+1，等到终点的时候，就判断一下，这个路径的黑色节点数和我们的开始算的那条路径是否相同！
上面的我们将检查连续红节点和，检查每个路径具有相同黑色节点数放在了同一个函数里面！
我们也可以拆开来写
//判断每个路径有相同的黑节点数 bool count(Node* root,int blacksum,const int& ref) { if(root == nullptr) { if(blacksum != ref) { std::cout << "黑节点的个数不相同" << std::endl; return false; } return true; } //遇到黑色节点就+1 if(root->_color == BLACK) blacksum++; return count(root->_left,blacksum,ref) && count(root->_right,blacksum,ref); }//判断连续红节点 bool check(Node* root) { if(root == nullptr) return true; if(root->_color == RED && root->_parent->_color == RED) { std::cout << "连续的红节点" << std::endl; return false; } return check(root->_left) && check(root->_right); }namespace MySTL { void randomtest() { srand((unsigned int)time(NULL)); const int N = 1000; RBTree<int, int> t; for (int i = 0; i < N; i++) { int key = rand() % N; t.insert(std::make_pair(key, key)); cout << "insert" << e << ":" << endl; } std::cout << t.Isbalance() << std::endl; } }可以使用上面代码进行测试！
红黑树的删除
红黑树的删除我们这里就不进行讲解
有兴趣可以参考
http://www.cnblogs.com/fornever/archive/2011/12/02/2270692.html
红黑树与AVL树的比较
红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O($log_2 N$)，红黑树不追 求绝对平衡，其只需保证最长路径不超过最短路径的2倍，==相对而言，降低了插入和旋转的次数， 所以在经常进行增删的结构中性能比AVL树更优==，而且红黑树实现比较简单，所以实际运用中红 黑树更多。