红黑树C++实现-创新互联
目录
创新互联公司坚持“要么做到,要么别承诺”的工作理念,服务领域包括:网站设计制作、成都做网站、企业官网、英文网站、手机端网站、网站推广等服务,满足客户于互联网时代的万山网站设计、移动媒体设计的需求,帮助企业找到有效的互联网解决方案。努力成为您成熟可靠的网络建设合作伙伴!一、红黑树的概念
二、红黑树的性质
三、红黑树节点的定义
四、红黑树的插入
4.1 插入节点
4.2 插入节点的颜色
4.3 调整情况1
4.4 调整情况2
4.5 调整情况3
4.6 调整情况总结
五、调整的实现
5.1 调整的步骤分析
5.2 代码实现
六、树的平衡判断
七、源代码+测试代码
一、红黑树的概念
红黑树,是一种二叉搜索树,但在每个节点上增加一个存储位表示结点的颜色,可以是 Red 或 Black 。通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确没有一条路径会比其他路径长出两倍,因而是接近平衡的。
二、红黑树的性质
- 每个节点不是红色就是黑色
- 根节点是黑色的
- 如果一个节点是红色的,则它的两个孩子结点是黑色的
- 对于每个节点,从该节点到其后代叶节点的简单路径上,均包含相同数目的黑色节点。
- 每个叶子节点都是黑色的(此处的叶子节点指的是空节点)
解读:
性质三:保证树中没有连续的红色节点
性质四:每条路径上黑色节点的数目相同
满足以上性质,红黑树就能保证:其最长路径中节点个数不会超过最短路径节点个数的两倍
其中,其极限最短:全黑。极限最长:一黑一红……
三、红黑树节点的定义因为性质一,节点的颜色不是红就是黑,所以我们可以使用枚举来清晰的区分。
四、红黑树的插入 4.1 插入节点红黑树本质也是二叉搜索树,所以插入的方式是相同的。只是调整平衡的方式不同。插入的代码如下:
bool Insert(const pair& kv)
{
if (!_root)
{
_root = new Node(kv);
_root->_col = BLACK;
return true;
}
Node* parent = nullptr;
Node* cur = _root;
//找插入的位置
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);
if (parent->_kv.first >kv.first)
{
parent->_left = cur;
}
else
{
parent->_right= cur;
}
cur->_parent = parent;
}
4.2 插入节点的颜色接下来我们就要分析,插入的节点默认应该是红色还是黑色。
首先分析插入黑节点。如下:
插入黑节点后,直接就破坏了红黑树的规则四,因为每条路径上的黑色节点数不再相同了,所以说插入黑节点是一定会出错的。
接下来我们看看插入红节点。
此中情况下,破坏了规则三,其红节点下必须是黑节点。
在这种情况下,插入红节点,既没有破坏规则三,也没有破坏规则四。所以说,插入红节点有几率会破坏规则,而插入黑节点一定会破坏规则,且破坏了整棵树,所以我们默认插入红节点。
那如果出现以上插入红节点破坏规则我们要怎么处理呢?
我们采取 变色+旋转 的策略,以上这种情况我们只需要变色即可解决。如图所示:
4.3 调整情况1因为新节点的默认颜色是红色,因此:如果其双亲节点的颜色是黑色,没有违反红黑树任何性质,则不需要调整;
但当新插入节点的双亲结点颜色为红色时,就违反了性质三不能有连续在一起的红色节点,此时就需要对红色数分情况来解决。
即双亲黑色不调整,双亲红色则调整。
情况一:cur 为红,parent为红,grandfather为黑,uncle存在且为红.
解决方式:将p,u 改为黑,g改为红,然后把 g 当作 cur,继续向上调整。
4.4 调整情况2情况二:cur 为红,p 为红,g 为黑,u 不存在/ u 存在且为黑。
- 如果 u 节点不存在,则 cur 一定是新插入节点,因为如果 cur 不是新插入节点,则 cur 和 p 一定有一个节点的颜色是黑色,就不满足性质4:每条路径黑色节点的个数相同。
- 如果 u 节点存在,则其一定是黑色的,那么 cur 节点原来的颜色一定是黑色的,现在看到其是红色的原因是因为 cur 的子树在调整的过程中将 cur 节点的颜色由黑色改成红色。
此时这种情况,单纯的变色是无法解决的,我们就要采取旋转+变色的方式。
此时我们的解决策略是将 p 变黑,g 变红,然后让其对 g 进行右单旋。
4.5 调整情况3情况三:cur 为红,p 为红,g 为黑,u 不存在 / u 存在且为黑
调整策略:
4.6 调整情况总结p 为 g 的左孩子,cur 为 p 的右孩子,则针对 p 进行左单旋,则转变为情况 2,然后再进行情况 2 的右单旋+变色即可。
在学习了AVL 树 之后,这三种情况其实也都能理解,接下来我们对其做一个总结。
五、调整的实现 5.1 调整的步骤分析红黑树的关键在于叔叔。因为知道叔叔节点的情况,可以了解到另一棵子树的高度情况。
三种情况:
- u 存在且为红,变色并继续向上处理
- u 不存在或为黑,进行 单旋+变色
- u 不存在或为黑,插入方式为折线,进行 双旋+变色。
5.2 代码实现
- 只有当cur 为红,p 为红,g 为黑,则进行调整。(p为黑不用调整,p 为红,则grandfather必然为黑,要不然此时不为红黑树)
- 查看 uncle 的位置,同时也是判断插入节点在 g 的左子树还是右子树。
- 情况1,uncle存在且为红,进行情况一的调整(变色+继续往上更新)。
- 如果uncle不存在或为黑,则为情况二或三
- 如果插入在边侧,则进行单旋+变色
- 如果插入在内侧,则进行双旋+变色。
以下只有调整的代码,没有截取插入的代码。
//1.因为插入的节点为红色, 如果parent也为红色,进行处理
while (parent && parent->_col == RED)
{
Node* grandfater = parent->_parent;
//2.判断爷节点的合法性
assert(grandfater);
assert(grandfater->_col == BLACK);
//3.查看叔叔
//4.首先判断叔叔位于grandfater的left 还是 right
if (grandfater->_left == parent)
{
Node* uncle = grandfater->_right;
//5.情况1,叔叔存在 && 叔叔为红色
if (uncle && uncle->_col == RED)
{
//6.将父、树变黑,祖父变红
parent->_col = uncle->_col = BLACK;
grandfater->_col = RED;
//7.并继续往上处理
cur = grandfater;
parent = cur->parent;
}
//8.情况2+情况3 uncle不存在或为黑
else
{
//9.判断单旋还是双旋
// g
// p u
// c 右单旋+变色
if (cur == parent->_left)
{
RotateR(grandfater);
parent->_col = BLACK;
grandfater->_col = RED;
}
// g 左右双旋+变色
// p u
// c
else
{
RotateL(parent);
RotateR(grandfater);
cur->_col = BLACK;
grandfater->_col = RED;
}
break;
}
}
else
{
Node* uncle = grandfater->_left;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfater->_col = RED;
//继续往上处理
cur = grandfater;
parent = cur->parent;
}
else
{
//9.判断单旋还是双旋
// g
// u p
// c 左单旋+变色
if (cur == parent->_right)
{
RotateL(grandfater);
parent->_col = BLACK;
grandfater->_col = RED;
}
// g 右左双旋+变色
// u p
// c
else
{
RotateR(parent);
RotateL(grandfater);
cur->_col = BLACK;
grandfater->_col = RED;
}
break;
}
}
}
//因为以上会将祖父变红,直接将_root变黑
_root->_color = BLACK;
return true;
好的,实现了插入之后,我们来使用一段测试代码测试一下 Insert
六、树的平衡判断实现 Insert 之后,只能证明当前的结构是一棵搜索树,而不能证明其是否为红黑树,接下来我们还要编写一个Balanceu验证平衡。
所以这个判定平衡的函数应该按照红黑树的规则,来进行判定该树是否符合红黑树的性质。即,算每条路径上的黑节点数量,如果路径上的黑节点数量相同,则说明是红黑树。
实现步骤:
- 计算最左/右边路径上的黑节点个数,将该值设为基准值。
- 走前序遍历,遇到黑节点则将将计数器++
- 如果当前节点的为红,并且父节点也为红则直接返回false。
- 如果该路径上的黑节点总数等于基准值,则返回true,反之返回false。
代码如下:
bool IsBalance()
{
if (_root == nullptr)
{
return true;
}
if (_root->_col == RED)
{
cout<< "根节点不是黑色"<< endl;
return false;
}
//设置基准值,以来校验路径上的黑节点
int benchmark = 0;
Node* cur = _root;
//计算左侧路径上的黑色节点数量
while (cur)
{
if (cur->_col == BLACK)
{
++benchmark;
}
cur = cur->_left;
}
return PrevCheck(_root, 0, benchmark);
}
bool PrevCheck(Node* root, int blackNum, int Benchmark)
{
if (root == nullptr)
{
if (blackNum != Benchmark)
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);
}
以上检查方式就按照红黑树的三条重要性质进行了检查,
1.根节点为黑色;2.不存在连续的红节点;3.每条路径上的黑节点个数相同。
满足以上三点才能证明该结构为红黑树。
接下来我们进入测试。
测试一:
测试二:
注意一件事情,我们使用的是键值对的形式进行插入的,如果 k 存在了,则不会进行插入,并且红黑树中的排序是按照 k 的大小进行排序的,所以使用 find 函数时,要按 pair.first 查找,因为 pair.second并按搜索树的规则存储的。
七、源代码+测试代码红黑树代码(实现了插入、查找、中序遍历、高度、平衡检测)
#includeusing namespace std;
enum Color { RED, BLACK };
//节点的定义
templatestruct RBTreeNode
{
RBTreeNode* _left;
RBTreeNode* _right;
RBTreeNode* _parent;
pair_kv;
Color _col;
RBTreeNode(const pair& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _col(RED)
{}
};
//红黑树
templateclass RBTree
{
typedef RBTreeNodeNode;
public:
bool Insert(const pair& kv)
{
if (!_root)
{
_root = new Node(kv);
_root->_col = BLACK;
return true;
}
Node* parent = nullptr;
Node* cur = _root;
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);
if (parent->_kv.first >kv.first)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = parent;
while (parent && parent->_col == RED)
{
Node* grandfater = parent->_parent;
assert(grandfater);
assert(grandfater->_col == BLACK);
if (grandfater->_left == parent)
{
Node* uncle = grandfater->_right;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfater->_col = RED;
cur = grandfater;
parent = cur->_parent;
}
else
{
if (cur == parent->_left)
{
RotateR(grandfater);
parent->_col = BLACK;
grandfater->_col = RED;
} else
{
RotateL(parent);
RotateR(grandfater);
cur->_col = BLACK;
grandfater->_col = RED;
}
break;
}
}
else
{
Node* uncle = grandfater->_left;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfater->_col = RED;
cur = grandfater;
parent = cur->_parent;
}
else
{
if (cur == parent->_right)
{
RotateL(grandfater);
parent->_col = BLACK;
grandfater->_col = RED;
}
else
{
RotateR(parent);
RotateL(grandfater);
cur->_col = BLACK;
grandfater->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return true;
}
void Inorder()
{
_Inorder(_root);
}
int Height()
{
return _Height(_root);
}
pairFind(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_kv.first >key)
{
cur = cur->_left;
}
else if (cur->_kv.first< key)
{
cur = cur->_right;
}
else
{
return cur->_kv;
}
}
return pair(0, 0);
}
bool IsBalance()
{
if (_root == nullptr)
{
return true;
}
if (_root->_col == RED)
{
cout<< "根节点不是黑色"<< endl;
return false;
}
//设置基准值,以来校验路径上的黑节点
int benchmark = 0;
Node* cur = _root;
while (cur)
{
if (cur->_col == BLACK)
{
++benchmark;
}
cur = cur->_left;
}
return PrevCheck(_root,0, benchmark);
}
private:
bool PrevCheck(Node* root, int blackNum,int Benchmark)
{
if (root==nullptr)
{
//cout<< blackNum<< endl;
if (blackNum == 2) // 3
{ // 7 16
int n = 0; // 11
} //
if (blackNum != Benchmark)
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)
{
_Inorder(root->_left);
cout<< root->_kv.first<< ":"<< root->_kv.second<< endl;
_Inorder(root->_right);
}
}
int _Height(Node* root)
{
if (root == nullptr)
return 0;
return max(_Height(root->_left), _Height(root->_right)) + 1;
}
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
subR->_left = parent;
if (subRL)
subRL->_parent = parent;
Node* ppNode = parent->_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 (ppNode)
{
if (ppNode->_left == parent)
{
ppNode->_left = subL;
}
else
{
ppNode->_right = subL;
}
subL->_parent = ppNode;
}
else
{
_root = subL;
subL->_parent = nullptr;
}
}
//成员变量 _root
Node* _root=nullptr;
};
测试代码
void TestRBTree1()
{
int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
RBTreet1;
for (auto e : a)
{
t1.Insert(e);
}
t1.Inorder();
//检测是否为红黑树
if (t1.IsBalance())
cout<< "Is RedBlackTree"<< endl;
else
cout<< "Not RedBlackTree"<< endl;
//查找 18
cout<< "Find(18):";
int result = t1.Find(18);
cout<< result<< endl;
}
void TestRBTree2()
{
size_t N = 10000000;
RBTreet1;
for (size_t i = 0; i< N; ++i)
{
t1.Insert(i);
}
cout<<"Height:"<< t1.Height()<< endl;
//检测是否为红黑树
if (t1.IsBalance())
cout<< "Is RedBlackTree"<< endl;
else
cout<< "Not RedBlackTree"<< endl;
int result = t1.Find(23451);
cout<< result<< endl;
}
int main()
{
TestRBTree1();
TestRBTree2();
return 0;
}
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
网页题目:红黑树C++实现-创新互联
分享网址:http://pwwzsj.com/article/csjcdj.html