三、红黑树
红黑树比起avl树是哟啊更优一点的。
3.1概念
红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的，不是严格平衡的。
3.2性质
1.每个结点不是红色就是黑色；
2.根节点是黑色的；
3.如果一个节点是红色的，则它的两个孩子结点都必须是黑色的 ，即父子不能同时为红，可为黑；
4.对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点；
5.所有NIL叶子节点都是黑色的，NIL为空节点；
总结一下，最短路径就是全黑，而最长路径就是一黑一红相间；黑色节点的占比范围为[50%,100%]，50%时黑红数量相同，100%时全黑；
优点：avl树需要严格的平衡，有着大量的旋转，而红黑树只需要满足最长路径不超过最短路径的二倍，是不严格的平衡，只需要局部子树没有连续的红节点并且子树的每条路径的黑节点数目相同，所以旋转就相对较少，尽管时间复杂度是avl树的2倍，但是减少了旋转的效率，总的来说是提高了效率。
3.3RB树的模拟实现
3.3.1插入原理
先实现二叉搜索树，之后插入会遇到的情况：
1.插入时选择插入红色，因为黑色需要每一个路径都进行更新，而红色只需要调整这一个路，不会影响其他路径；
2.如果父节点是黑的，就不需要调整了，如果是红的就需要修改，如果父节点是红色的那么他一定不是根节点，根节点是没有爷爷的，而且爷爷一定是黑色的；
3.红黑树要看的是叔叔即父节点的兄弟节点，如果叔叔存在且是红色，那么父亲和叔叔变黑，爷爷变红，这样就保证了父亲和叔叔这两条路径一定是黑色节点数保持不变，且连续的红节点问题暂时的解决了，仅仅解决的是局部的问题，还需要继续向上解决问题。
4.继续向上处理分为三种情况：1.爷爷就是根节点，没有父亲了，只需要将爷爷再变黑即可；2.有父亲，但是父亲是黑色，直接结束；3.有父亲，父亲是红色，重复上述过程，cur=grandfather，parent=cur->parent,grandfather=parnet->parent;
5.当黑色节点多时，插入红色节点就方便了。
6.对于叔叔如果不存在，旋转加变色；叔叔存在为红色，父亲叔叔变黑，爷爷变红；如果叔叔存在为黑色，旋转加变色；
总结：
1.如果父亲是黑色，就停止了，父亲是根，父亲变黑停止；
2.剩下的需要调整的情况一定是，cur与parent是红色的，grandfather是黑色的，否则就是出错了；
3.接下来就需要讨论uncle，如果uncle存在且为红，p与u变为黑，g变为红，g变成cur继续向上调整，重复1、2；
如果cur为新增的节点abcde为空，就是cur为红不断地向上更新；如果cde为每条路径只有一个黑节点的红黑树，每个有四种情况如下，此时cur为黑色，a和b节点都是红色且没有子节点，选择在ab位置插入4种，一共有4*4*4*4=256种可能；
如果如果cde为每条路径只有两个黑节点的红黑树，则需要变2层才能结束；
4.如果uncle存在且为黑或者uncle不存在，uncle为黑色，cur不可能为红色新增，一定为黑色，且有两个红节点；
c是每条路径包含是一个黑色节点的红黑树，de是红节点或者为空；4*2*2*4=64种；
#pragma once
#include <cassert>
namespace RbTree
{
enum Colour
{
RED,
BLACK,
};
template <class K, class V>
struct RBTreeNode
{
RBTreeNode(const pair<K, V>& kv) : kv_(kv), left_(nullptr), right_(nullptr), parent_(nullptr), col_(BLACK) {}
pair<K, V> kv_;
RBTreeNode<K, V>* left_;
RBTreeNode<K, V>* right_;
RBTreeNode<K, V>* parent_;
Colour col_;
};
template <class K, class V>
class RBTree
{
typedef RBTreeNode<K, V> node;
public:
//普通成员函数
bool insert(const pair<K, V>& kv);
void rotatel(node* parent);
void rotater(node* parent);
void rotaterl(node* parent);
void rotatelr(node* parent);
void inorder()
{
_inorder(root_);
}
bool isrbtree()
{
return _isrbtree(root_);
}
bool checkcolour(node* root, int blacknum, int reference);
private:
//私有成员
void _inorder(node* root);
bool _isrbtree(node* root);
node* root_ = nullptr;
};
template <class K, class V>
void RBTree<K, V>::rotatel(node* parent)
{
node* cur = parent->right_;
node* curleft = cur->left_;
parent->right_ = curleft;
node* ppnode = parent->parent_;
if (curleft)
curleft->parent_ = parent;
parent->parent_ = cur;
cur->left_ = parent;
if (parent == root_)
{
root_ = cur;
cur->parent_ = nullptr;
}
else
{
if (ppnode->left_ == parent)
{
ppnode->left_ = cur;
}
else
{
ppnode->right_ = cur;
}
cur->parent_ = ppnode;
}
}
template <class K, class V>
void RBTree<K, V>::rotater(node* parent)
{
node* cur = parent->left_;
node* curright = cur->right_;
node* ppnode = parent->parent_;
parent->left_ = curright;
cur->right_ = parent;
if (curright)
curright->parent_ = parent;
parent->parent_ = cur;
if (parent == root_)
{
root_ = cur;
cur->parent_ = nullptr;
}
else
{
if (ppnode->left_ == parent)
{
ppnode->left_ = cur;
}
else
{
ppnode->right_ = cur;
}
cur->parent_ = ppnode;
}
}
template <class K, class V>
void RBTree<K, V>::rotaterl(node* parent)
{
rotater(parent->right_);
rotatel(parent);
}
template <class K, class V>
void RBTree<K, V>::rotatelr(node* parent)
{
rotatel(parent->left_);
rotater(parent);
}
template <class K, class V>
bool RBTree<K, V>::insert(const pair<K, V>& kv)
{
if (root_ == nullptr)
{
root_ = new node(kv);
root_->col_ = BLACK;
return true;
}
node* cur = root_;
node* parent = cur;
while (cur)
{
if (kv.first > cur->kv_.first)
{
parent = cur;
cur = cur->right_;
}
else if (kv.first < cur->kv_.first)
{
parent = cur;
cur = cur->left_;
}
else
{
return false;
}
}
cur = new node(kv);
cur->col_ = RED;
if (kv.first > parent->kv_.first)
{
parent->right_ = cur;
}
else
{
parent->left_ = cur;
}
cur->parent_ = parent;
while (parent && parent->col_ == RED)
{
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 = cur->parent_;
}
else
{
// 叔叔不存在或者叔叔存在且为黑
if (cur == parent->left_)
{
// 右单旋
rotater(grandfather);
parent->col_ = BLACK;
grandfather->col_ = RED;
}
else
{
// 左右双旋
rotatelr(grandfather);
cur->col_ = BLACK;
grandfather->col_ = RED;
}
break;
}
}
else if (grandfather->right_ == parent)
{
node* uncle = grandfather->left_;
// 叔叔存在且为红
if (uncle && uncle->col_ == RED)
{
// 变色+向上处理
parent->col_ = uncle->col_ = BLACK;
grandfather->col_ = RED;
// 继续向上处理
}
else
{
// 叔叔不存在或者叔叔存在且为黑
if (cur == parent->right_)
{
// 左单旋
rotatel(grandfather);
parent->col_ = BLACK;
grandfather->col_ = RED;
}
else
{
// 右左双旋
rotaterl(grandfather);
cur->col_ = BLACK;
grandfather->col_ = RED;
}
break;
}
}
else
{
assert(false);
}
}
// 如果父亲不存在，说明cur为根，就要将cur置为黑色，如果父亲存在且为黑色则不需要处理；
root_->col_ = BLACK;
return true;
}
template <class K, class V>
void RBTree<K, V>::_inorder(node* root)
{
if (root == nullptr)
{
return;
}
_inorder(root->left_);
cout << root->kv_.first << ":" << root->kv_.second << endl;
_inorder(root->right_);
}
template<class K, class V>
bool RBTree<K, V>::checkcolour(node* root, int blacknum, int reference)
{
if (root == nullptr)
{
if (blacknum != reference)
{
return false;
}
return true;
}
if (root->col_ == BLACK)
{
blacknum++;
}
if (root->col_ == RED && root->parent_->col_ == RED)
{
cout << root->kv_.first << "出现连续红色节点" << endl;
return false;
}
return checkcolour(root->left_, blacknum, reference) && checkcolour(root->right_, blacknum, reference);
}
template<class K, class V>
bool RBTree<K, V>::_isrbtree(node* root)
{
if (root == nullptr)
{
return true;
}
if (root->col_ != BLACK)
{
return false;
}
int reference = 0;
node* cur = root_;
while (cur)
{
if (cur->col_ == BLACK)
{
reference++;
}
cur = cur->left_;
}
return checkcolour(root, 0, reference);//检查连续的红色
}
}
3.4红黑树的应用
1.C++ STL库 – map/set、mutil_map/mutil_set；
2.Java 库；
3.linux内核；
4.其他一些库；