C++实现红黑树核心插入实例代码
一、红黑树概念介绍
二、红黑树模拟实现
（1）红黑树节点
（2）红黑树插入分析(核心)
（3）插入代码思路(如何快速写插入算法)
（4）判断平衡函数
（5）查找函数
（6）测试函数
（7）测试结果
三、红黑树源代码
（1）RbTree.h
（2）Test.cpp
总结
一、红黑树概念介绍概念：
红黑树，也是一种二叉搜索树，它是在每个结点上增加一个存储位表示结点的颜色，可以是红或黑，然后通过对任何一条从根到叶子的路径上各个结点着色方式的限制，保证了没有一条路径会能超过其他路径的俩倍，因而是近似平衡的。map和set的底层数据结构就是用红黑树来封装的。
性质：
1.根节点是黑色的
2.不能出现连续的红色节点
3. 每条路径上有相同数量的黑色节点
4. 每个叶子(空节点)结点都是黑色
5. 每个结点不是红色就是黑色
满足上面的性质，红黑树就能保证：最长路径中节点个数不会超过最短路径节点个数的2倍。
优势：
假设全部的黑色节点有N个 最短路径长度是logN 整棵树的节点数量：[N,2N]，最长路径长度：2logN。假设10亿个节点，AVL：最多查找30次左右；RB：最多查找60次左右。
综合而言，其实对于查找大量数据30次和60次没太大差别，而红黑树不要求绝对平衡，只需保证最长路径不超过最短路径的2倍，相对来说降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优。
二、红黑树模拟实现 （1）红黑树节点enum Color
{
RED=0,
BLACK,
};
template<class K,class V>
struct RbTreeNode
{
RbTreeNode<K, V>* _left;
RbTreeNode<K, V>* _right;
RbTreeNode<K, V>* _parent;
pair<K, V>_kv;
Color _col;
RbTreeNode(const pair<K, V>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _col(RED)
{}
};
里面同样用三叉链，要有左孩子右孩子，父节点，以及pair类的类型来存储kv两个相同或不同类型的值(当我们使用make_pair函数创建一个pair对象，该函数会自动推断参数类型)，并在里面增加一个枚举，用来表示一个节点不是红色就是黑色。关于构造函数里面的颜色初始化为黑色还是红色，在插入会讲解。
（2）红黑树插入分析(核心)插入和前面的AVL插入部分是一样的，在里面如果是根节点，那就把跟点为置为黑色。
那这有一个问题就是节点构造函数里面的一个问题：我们在申请一个新节点时，宁愿新增红色还是黑色？
因为不管是增哪种颜色，本质上是违反规则三还是违反规则四的问题，如果插入黑色，一定违反规则四，但它代价太大，违反规则三就不一定，因为它的父节点可能为红色也可能为黑色，如果在黑色节点下面插入就没影响，反之就会影响。
对于上面的做法会出现下面的两大情况，第一GPC为一一条直线，第二GPC为折线。
如图：
G为祖父节点，P为父亲节点，C为当前节点，U为叔父节点
1、先解决当GPC为一条直线的时候：
（1）如果U存在且为红色，P必须变黑，U也得变黑，左右都增加了黑，那就把G变红,这样久能保持黑色节点不变，因为G现在变成红了，但是G的父节点如果是红色的还得继续处理 ，那就把G当成C节点，继续算它的祖父，再看U，如果U是红再把它变成黑。
它的所对应的抽象图以及具象图：
（2）如果U不存在或者存在且为黑又是两种情况
如果U不存在，再增加红节点，且有连续的红色节点，有可能会超过它的最短路径，只能旋转来降高度。把P变黑，把G给P的左，再把P作为左，同时把原来的G变红，这里就是左单旋加G和P变色。
如下例图：
它所对应的抽象及具象图：
如果U存在且为黑色
U存在且为黑是由第一种请况变化而来，这里发生了右单旋，P的左孩子作为G的左孩子，而G又作为P的右孩子，且P变为黑，G变为红。
对于上面的U不存在或者存在为黑两种情况进行总结： P为G的左孩子时，C为P的左孩子进行右单旋转，如果P为G的右孩子，C为P的右孩子，进行左单旋转。P变为黑色，G变为红色。
旋转的目的就是为了防止最长路径超过最短路径的2倍。GPC为一条线的时候就是左单旋转或右单旋。
2、再解决GPC为折线的情况
（1）U存在且为黑
出现这种折线情况的原因是由第一种情况先变色而产生，然后p变成g的左，c变成p的右，c为红，p为红，g为黑，接着我们先以p为轴进行左旋转进行降低高度，在以g为轴进行右旋，且g变红，c变黑，因为这样才能保证不出现连续红结点且保证每个路径黑色数量一样。以上实际进行了双旋。
（2）U不存在，直接右单旋
（3）插入代码思路(如何快速写插入算法)
（一）先看左面这种大情况
插入C1肯定为红节点，P1如果是红，就需要开始作处理：先利用三叉链，从P1得出G1，进入核心环节：左面的这种情况是P1是G1的左孩子时，里面又要有分两种情况：
（1）如果是U存在且为红，我们把P1和U变为黑，G1变为红，更新C1到G1的位置，继续往上调整；
（2）如果是U不存在或黑(是一种情况)，如果U不存在就不能变黑，而且就算存在为黑说明是一定是由继续往上调整的那一步(情况(1))而来的即继续往上处理，我们还是是增加了节点，就可能导致最长路径超过最短路径的2倍或者一直用情况(1)的方式最终导致每条路径黑色数量不相等。这时候我们就要通过旋转方式降低高度加变色来解决。所以在这里又分两种：G1P1C1为直线和G1P1C1为折线：
如果是C1P1在一条直线上即C1是P1的左孩子，我们以G1为轴进行右单旋(哪边高往哪边降)，G1要变红，P1要变成黑，因为G1下来了P1作为根，不能出现连续的红节点P要变黑，又因为保证黑色数量相等，G1要变红。如果是C1和P1，G1是折线的时候即C1是P1的右孩子，这时候需要先以P1为轴进行左单旋，再以G1为轴进行右单旋，最终C1做了根节点，G1是右孩子，因为P1是红，C1是红不能出现连续红节点，需把C1变黑，但是还要保证黑色数量相等，就把G1变红。最后结束break，只有情况(1)才会继续向上来回处理。
（二）再看右面这种大情况
和（一）情况类似
P2是G2的右孩子，同理那旋转方式就根上面相反。
所以我们的插入函数：
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_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->_right;
}
else if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
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* grandf = parent->_parent;
if (grandf->_left == parent)
{
Node* unc = grandf->_right;
if (unc && unc->_col == RED)//u存在且为红，变色处理
{
parent->_col = BLACK;
unc->_col = BLACK;
grandf->_col = RED;
cur = grandf;//继续往上调整
parent = cur->_parent;
}
else//u不存在或者黑
{
if (parent->_left == cur)
{
RotateR(grandf);
parent->_col = BLACK;
grandf->_col = RED;
}
else
{
RotateL(parent);
RotateR(grandf);
cur->_col = BLACK;
grandf->_col = RED;
}
break;
}
}
else
{
Node* unc = grandf->_left;
if (unc && unc->_col == RED)
{
parent->_col = BLACK;
unc->_col = BLACK;
grandf->_col = RED;
cur = grandf;
parent = cur->_parent;
}
else
{
if (parent->_right == cur)
{
RotateL(grandf);
parent->_col = BLACK;
grandf->_col = RED;
}
else
{
RotateR(parent);
RotateL(grandf);
cur->_col = BLACK;
grandf->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return true;
}
（4）判断平衡函数
bool IsBalance()
{
if (_root && _root->_col == RED)
{
cout << "根节点颜色错误" << endl;
return false;
}
int Bsign = 0;
Node* cur = _root;
while (cur)
{
if (cur->_col == BLACK)
{
++Bsign;
}
cur = cur->_left;
}
return _check(_root, 0, Bsign);
}
bool _check(Node* root, int Bnum, int Bsign)
{
if (root == nullptr)
{
if (Bnum != Bsign)
{
cout << "黑色节点数量不相等" << endl;
return false;
}
return true;
}
if (root->_col == BLACK)
{
++Bnum;
}
if (root->_col == RED && root->_parent && root->_parent->_col == RED)
{
cout << "连续红色节点" << endl;
return false;
}
return _check(root->_left,Bnum,Bsign) && _check(root->_right, Bnum, Bsign);
}
void _Destroy(Node* root)
{
if (root == nullptr)
{
return;
}
_Destroy(root->_left);
_Destroy(root->_right);
delete root;
}
首先不能以最长路径不超过最短路径2倍为准则判断平衡，它只是结果。
还是要以前面说的规则：
第一个：先检查根是不是黑色的；
第二个：再检查连续的红色节点：如果是红色的就去检查儿子，这种方式不行，因为孩子可能不存在，可以改为它的父亲，如果是红一定有父亲，如果父亲为红就存在连续红色节点直接返回假；
还有一个：最重要的规则：判断黑色节点的数量是否相等，我们需要先记录一下黑色数量，我们可以先获取一条路径的黑色数量Bsign，然后以它为标准，如何让每条路径以它标准判断是否相等？我们可以在参数里面的形参传值Bnum，往下递归就会往下传，下一层++不会影响上一层++，因为下一层是上一层的拷贝，只要有一条不相等就返回假。
（5）查找函数Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_kv.first < key)
{
cur = cur->_right;
}
else if (cur->_kv.first > key)
{
cur = cur->_left;
}
else
{
return cur;
}
}
return nullptr;
}
从根开始走，如果比它大，就往右边走，如果比它小，就往左边走，如果相等说明找到，否则返回空。
（6）测试函数void Test()
{
int arr[] = { 33, 22, 6, 1, 3, 5, 66, 7, 16, 14, 16, 3, 7, 11, 9, 36, 18, 14, 15 };
RbTree<int, int> t;
for (auto n : arr)
{
t.Insert(make_pair(n, n));
}
t.Inorder();
cout << endl;
cout << t.IsBalance() << endl;
cout << "高度："<<t.height() << endl;
cout << endl;
cout << "随机数据测试:" << endl;
srand(time(0));
const size_t N = 100000;
RbTree<int, int> r;
for (size_t i = 0; i < N; ++i)
{
size_t x = rand() + i;
r.Insert(make_pair(x, x));
}
cout << r.IsBalance() << endl;
cout <<"高度："<< r.height() << endl;
}
（7）测试结果
#pragma once
#include<iostream>
#include<utility>
#include<ctime>
using namespace std;
enum Color
{
RED=0,
BLACK,
};
template<class K,class V>
struct RbTreeNode
{
RbTreeNode<K, V>* _left;
RbTreeNode<K, V>* _right;
RbTreeNode<K, V>* _parent;
pair<K, V>_kv;
Color _col;
RbTreeNode(const pair<K, V>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _col(RED)
{}
};
template <class K,class V>
class RbTree
{
typedef RbTreeNode<K, V> Node;
public:
~RbTree()
{
_Destroy(_root);
_root = nullptr;
}
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_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->_right;
}
else if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
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* grandf = parent->_parent;
if (grandf->_left == parent)
{
Node* unc = grandf->_right;
if (unc && unc->_col == RED)//u存在且为红，变色处理
{
parent->_col = BLACK;
unc->_col = BLACK;
grandf->_col = RED;
cur = grandf;//继续往上调整
parent = cur->_parent;
}
else//u不存在或者黑
{
if (parent->_left == cur)
{
RotateR(grandf);
parent->_col = BLACK;
grandf->_col = RED;
}
else
{
RotateL(parent);
RotateR(grandf);
cur->_col = BLACK;
grandf->_col = RED;
}
break;
}
}
else
{
Node* unc = grandf->_left;
if (unc && unc->_col == RED)
{
parent->_col = BLACK;
unc->_col = BLACK;
grandf->_col = RED;
cur = grandf;
parent = cur->_parent;
}
else
{
if (parent->_right == cur)
{
RotateL(grandf);
parent->_col = BLACK;
grandf->_col = RED;
}
else
{
RotateR(parent);
RotateL(grandf);
cur->_col = BLACK;
grandf->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return true;
}
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_kv.first < key)
{
cur = cur->_right;
}
else if (cur->_kv.first > key)
{
cur = cur->_left;
}
else
{
return cur;
}
}
return nullptr;
}
void Inorder()
{
_InOrder(_root);
}
int height()
{
return _Height(_root);
}
bool IsBalance()
{
if (_root && _root->_col == RED)
{
cout << "根节点颜色错误" << endl;
return false;
}
int Bsign = 0;
Node* cur = _root;
while (cur)
{
if (cur->_col == BLACK)
{
++Bsign;
}
cur = cur->_left;
}
return _check(_root, 0, Bsign);
}
private:
void RotateL(Node* parent)//左单旋
{
Node* suR = parent->_right;//11的右孩子即22
Node* suRL = suR->_left;//11的右孩子的左孩子即b
Node* ppnode = parent->_parent;//维护父结点的父结点
parent->_right = suRL;//11右孩子链接b
if (suRL)//如果b不为空
suRL->_parent = parent;//更新双亲结点
suR->_left = parent;//22上提，左孩子链接11
parent->_parent = suR;//更新双亲结点
if (ppnode == nullptr)
{
_root = suR;
_root->_parent = nullptr;
}
else
{
if (ppnode->_left == parent)
{
ppnode->_left = suR;
}
else
{
ppnode->_right = suR;
}
suR->_parent = ppnode;
}
}
void RotateR(Node* parent)//右单旋
{
Node* suL = parent->_left;
Node* suLR = suL->_right;
parent->_left = suLR;
if (suLR)
suLR->_parent = parent;
Node* ppnode = parent->_parent;
suL->_right = parent;
parent->_parent = suL;
if (parent == _root)
{
_root = suL;
_root->_parent = nullptr;
}
else
{
if (ppnode->_left == parent)
{
ppnode->_left = suL;
}
else
{
ppnode->_right = suL;
}
suL->_parent = ppnode;
}
}
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_kv.first << " ";
_InOrder(root->_right);
}
int _Height(Node* root)
{
if (root == NULL)
return 0;
int leftH = _Height(root->_left);
int rightH = _Height(root->_right);
return leftH > rightH ? leftH + 1 : rightH + 1;
}
bool _check(Node* root, int Bnum, int Bsign)
{
if (root == nullptr)
{
if (Bnum != Bsign)
{
cout << "黑色节点数量不相等" << endl;
return false;
}
return true;
}
if (root->_col == BLACK)
{
++Bnum;
}
if (root->_col == RED && root->_parent && root->_parent->_col == RED)
{
cout << "连续红色节点" << endl;
return false;
}
return _check(root->_left,Bnum,Bsign) && _check(root->_right, Bnum, Bsign);
}
void _Destroy(Node* root)
{
if (root == nullptr)
{
return;
}
_Destroy(root->_left);
_Destroy(root->_right);
delete root;
}
private:
Node* _root;
};
void Test()
{
int arr[] = { 33, 22, 6, 1, 3, 5, 66, 7, 16, 14, 16, 3, 7, 11, 9, 36, 18, 14, 15 };
RbTree<int, int> t;
for (auto n : arr)
{
t.Insert(make_pair(n, n));
}
t.Inorder();
cout << endl;
cout << t.IsBalance() << endl;
cout << "高度："<<t.height() << endl;
cout << endl;
cout << "随机数据测试:" << endl;
srand(time(0));
const size_t N = 100000;
RbTree<int, int> r;
for (size_t i = 0; i < N; ++i)
{
size_t x = rand() + i;
r.Insert(make_pair(x, x));
}
cout << r.IsBalance() << endl;
cout <<"高度："<< r.height() << endl;
}
（2）Test.cpp
#include"RbTree.h"
int main()
{
Test();
return 0;
}
总结
到此这篇关于C++实现红黑树核心插入的文章就介绍到这了,更多相关C++红黑树核心插入内容请搜索软件开发网以前的文章或继续浏览下面的相关文章希望大家以后多多支持软件开发网！
