红黑树详解及代码实现(C++)-创新互联
红黑树是一种二叉搜索树，但在每个节点上增加一个存储位标识节点的颜色，RED或BLACK。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而接近平衡。（可以看出红黑树的控制平衡的条件没有AVL树那么严格）
创新互联公司主要从事成都做网站、成都网站制作、网页设计、企业做网站、公司建网站等业务。立足成都服务越秀,十年网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:18980820575红黑树的性质
红黑树一些操作要点 定义方面1.每个结点不是黑色就是红色
2.根节点是黑色的
3.如果一个结点是红色的，则它的两个孩子结点是黑色的
4.对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
5.每个叶子节点都是黑色的（这里的叶子结点指的是空结点）
为了满足根节点是黑色，我们增加了一个头结点并变成黑色，这个头结点的左指向最小结点，右指向大节点。
插入方面红黑树是在二叉搜索树上加上了颜色限制，因此红黑树的插入可以分为两步：
1.按照二叉搜索树的方式插入
2.检测新节点插入后，红黑树的性质是否遭到了破坏。
由于新节点的默认颜色是红色，此时我们就可能双亲结点颜色，如果双亲结点是黑色，则满足红黑树性质；但如果双亲结点时红色时，就不满足性质三。
接下来我们来细看这三种情况
（cur是当前节点，p为父节点，g为祖父节点，u为叔叔结点）
情况一：cur为红，p为红，g为黑，u存在且为红
此时又可以分为，该树是一颗完整的树还是一棵子树
当它是一棵完整的子树时，g也就是根节点必须时黑色，不为黑要改成黑色
当它是一棵子树时，g不是根节点，g就必须有双亲结点，此时就有两个连续的红色结点，这是就必须向上调整
简述一下解决方案就是：将p ，u改为黑，g改成红，然后把g当成cur,继续向上调整
情况二：cur为红，p为红，g为黑，u不存在/u存在且为黑（外侧）
此时我们主要看u这两种情况：
1.如果u不存在，则cur一定是新插入结点，因为如果不是新插入结点，为了满足性质4，每条路径上的黑色节点个数相同，则cur和p一定有一个是黑色结点。
2.如果u存在，则其一定是黑色的，那么cur结点原来的颜色一定是黑色的，现在是红色的原因是，cur的子树在调整的过程中将cur结点的颜色由黑变红
现在看下子树旋转变色的过程
1.p为g的左孩子，cur为p的左孩子，则进行右单旋
2.p为g的右孩子，cur为p的右孩子，则进行左单旋
p,g变色----p变黑，g变红
情况三：cur为红，p为红，g为黑，u不存在/u存在且为黑（内侧）
1.p为g的左孩子，cur为p的右孩子，则针对p做左单旋
2.p为g的右孩子，cur为p的左孩子，则针对p做右单旋
红黑树的验证也分为两步：
1.验证是否满足二叉搜索数（中序遍历是否为有序序列）
2.检测是否满足红黑数的五种性质
#pragma once
#include#include
#include
using namespace std;
enum Colour
{RED,
BLACK
};
templatestruct RBTreeNode
{RBTreeNode* _left;
RBTreeNode* _right;
RBTreeNode* _parent;
pair_kv;
Colour _col;
RBTreeNode(const pair& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
{}
};
templatestruct RBTree
{typedef RBTreeNodeNode;
public:
//按照二叉搜索树来插入新节点
//如果不满足那五个条件就就进行旋转改色处理
bool Insert(const pair& kv)
{if (_root == nullptr)
{ _root = new Node(kv);
_root->_col = BLACK;
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{ if (cur->_kv< kv)
{ parent = cur;
cur = cur->_right;
}
else if (cur->_kv >kv)
{ parent = cur;
cur = cur->_left;
}
else
{ return false;
}
}
cur = new Node(kv);
cur->_col = RED;
if (parent->_kv.first< kv.first)
{ parent->_right = cur;
}
else
{ parent->_left = cur;
}
cur->_parent = parent;
while (parent && parent->_col == RED)
{ Node* grandfather = parent->_parent;
assert(grandfather);
assert(grandfather->_col == BLACK);
if (parent == grandfather->_left)
{ Node* uncle = grandfather->_right;
//uncle存在且为红
if (uncle && uncle->_col == RED)
{parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//继续向上处理
cur = grandfather;
parent = cur->_parent;
}
else
{//情况二三，不存在或者存在且为黑
//情况二：右单旋+变色
// g
// p u
// c
if (cur == parent->_left)
{RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{//左右单旋+变色
// g
// p u
// c
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else//(parent==grandfather->_right)
{ Node* uncle = grandfather->_left;
//情况一
if (uncle && uncle->_col == RED)
{parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{//情况二：左单旋+变色
// g
// u p
// c
if (cur == parent->_right)
{RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{//情况三：右左单旋+变色
// g
// u p
// c
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return true;
}
void InOrder()
{_InOrder(_root);
cout<< endl;
}
bool IsBalance()
{if (_root == nullptr)
{ return true;
}
if (_root->_col == RED)
{ cout<< "根节点不是黑色"<< endl;
return false;
}
//看黑色结点数
int bechmark = 0;
return PrevCheck(_root, 0, bechmark);
}
private:
bool PrevCheck(Node* root, int blacknum, int& benchmark)
{if (root == nullptr)
{ if (benchmark == 0)
{ benchmark = blacknum;
return true;
}
if (blacknum != benchmark)
{ cout<< "某条黑色节点数不对"<< endl;
return false;
}
else
{ return true;
}
}
if (root->_col == BLACK)
{ blacknum++;
}
if (root->_col == RED && root->_parent->_col == RED)
{ cout<< "存在连续的红色结点"<< endl;
return false;
}
return PrevCheck(root->_left, blacknum, benchmark)
&& PrevCheck(root->_right, blacknum, benchmark);
}
void _InOrder(Node* root)
{if (_root == nullptr)
{ return;
}
_InOrder(root->_left);
cout<< root->_kv.first<< ":"<< root->_kv.second<< endl;
_InOrder(root->_right);
}
void RotateL(Node* parent)
{Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
Node* ppNode = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
if (_root == parent)
{ _root = subR;
subR->_parent = nullptr;
}
else
{ if (ppNode->_left == parent)
{ ppNode->_left = subR;
}
else
{ ppNode->_right = subR;
}
subR->_parent == ppNode;
}
}
void RotateR(Node* parent)
{Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
{ subLR->_parent == parent;
}
Node* ppNode = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (_root == parent)
{ _root = subL;
subL->_parent = nullptr;
}
else
{ if (ppNode->_left == parent)
{ ppNode->_left = subL;
}
else
{ ppNode->_right = subL;
}
subL->_parent = ppNode;
}
}
private:
Node* _root = nullptr;
};
红黑树和AVL数都是高效平衡二叉树，增删查改的时间复杂度都是O(logn)，不存在什么，最坏的时间复杂度。
红黑树不追求绝对平衡，只需保证最长路径不超过最短路径的2倍，相较而言降低了插入和旋转的次数，因此增删效率会比AVL数高一点，实际上使用红黑树可能会更多一点。
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
分享题目：红黑树详解及代码实现(C++)-创新互联
URL网址：http://6mz.cn/article/coodse.html