您好，登录后才能下订单哦！
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
这篇文章主要介绍“C++数据结构之红黑树如何实现”，在日常操作中，相信很多人在C++数据结构之红黑树如何实现问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”C++数据结构之红黑树如何实现”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！
红黑树在表意上就是一棵每个节点带有颜色的二叉搜索树，并通过对节点颜色的控制，使该二叉搜索树达到尽量平衡的状态。所谓尽量平衡的状态就是：红黑树确保没有一条路径比其他路径长两倍。
和AVL树不同的是，AVL树是一棵平衡树，而红黑树可能平衡也可能不平衡(因为是尽量平衡的状态)
要实现一棵红黑树，即要红黑树确保没有一条路径比其他路径长两倍。通过对节点颜色的约定来实现这一目标。
1.根节点是黑色的。
2.如果一个节点是红色的，则它的两个孩子都是黑色的。
3.对于每个节点，从该节点到其所有后代节点的简单路径上，均包含相同数量的黑色节点。
实现了这三条颜色规则的二叉搜索树，即也实现了没有一条路径比其他路径长两倍，即实现了一棵红黑树。
1、调整平衡的实现机制不同
红黑树根据节点颜色(同一父节点出发到叶子节点，所有路径上的黑色节点数目一样)，一些约定和旋转实现。
AVL根据树的平衡因子(所有节点的左右子树高度差的绝对值不超过1)和旋转决定。
2、红黑树的插入效率更高
红黑树是用非严格的平衡来换取增删节点时候旋转次数的降低，任何不平衡都会在三次旋转之内解决，红黑树并不追求“完全平衡”，它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能
而AVL是严格平衡树(高度平衡的二叉搜索树)，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多。所以红黑树的插入效率更高
3、AVL查找效率高
如果你的应用中，查询的次数远远大于插入和删除，那么选择AVL树，如果查询和插入删除次数几乎差不多，应选择红黑树。即，有时仅为了排序（建立-遍历-删除），不查找或查找次数很少，R-B树合算一些。
实现一棵红黑树，本质是实现它的插入函数，使插入函数可以实现红黑树的颜色约定，它的实现分为两步，即先找到插入的位置，再控制平衡。插入函数返回值设计为bool，插入成功返回true，失败返回false。控制平衡时，需要关注四个节点，即新插入的节点，它的父节点，它的叔叔节点，它的祖父节点。
当为第一个节点的时候，颜色设为黑，直接插入。
当插入的不是第一个节点时，颜色设为红，需要根据二叉搜索树的性质找到插入位置。并实现三叉链。
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);
cur->_col= Red;
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
cur->_parent = parent;
}
else
{
parent->_left = cur;
cur->_parent = parent;
}(1)当父节点为黑
当父节点为黑的时候，由于插入的子节点的颜色为红，对三个约定没有任何影响，因此不需要调整平衡。
(2)判断父节点在祖父节点的位置
通过判断父节点在祖父节点的位置，来定义叔叔节点的位置，以及之后的旋转方向的判断。
while (parent && parent->_col == Red)
{
Node* grandfather = parent->_parent;
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
//三种情况的处理
}
else
{
Node* uncle = grandfather->_left;
//三种情况的处理
}首先需要使用大循环，这个循环是为情况1而准备的，情况2和3直接跳出循环即可，因为只有情况1对上层循环有影响。
下面我们以父节点在祖父节点的左侧为例，右侧同理。
(3)叔叔节点存在且为红
解决方案：将父节点和叔叔节点设为黑，将祖父节点设为红。然后将祖父节点作为新节点继续向上平衡。如果祖父节点是根节点，那么需要再将其置为黑。
注意，这种情况和其他情况不同的是，需要将祖父节点作为新插入的节点继续向上遍历，这说明需要一个循环。而其他类型的情况直接break跳出这个循环即可。
//第一种情况
if (uncle && uncle->_col == Red)
{
parent->_col = uncle->_col = Black;
grandfather->_col = Red;
cur = grandfather;
parent = cur->_parent;
}这种情况只需要控制颜色即可，但是要继续向上循环。
(4)父节点为红，叔叔不存在或存在且为黑，新插入的节点在父节点左侧
解决方案：对祖父节点右旋操作，并将祖父节点置为红，父节点置为黑。
关于旋转的细节，我在AVL树中有详细的解释：C++手撕AVL树
//第二种情况，右单旋
if (cur == parent->_left)
{
RotateR(grandfather);
parent->_col = Black;
grandfather->_col = Red;
}(5)父节点为红，叔叔不存在或存在且为黑，新插入的节点在父节点右侧
解决方案：进行双旋，即对父节点进行左单旋，祖父节点进行右单旋。将子节点置为黑，将祖父节点置为红。
else
{
RotateL(parent);
RotateR(grandfather);
cur->_col = Black;
grandfather->_col = Red;
}(6)最后置黑
每一次插入都对根节点置为黑操作，因为第一种情况可能导致根节点不是黑。同时对根节点置黑也并不违反三条规定。
当我们处理完父节点在祖父节点的左侧后，处理父节点在祖父节点的右侧。
全部处理之后，我们的插入代码就完成了，接下来要对整个树进行测试，即对三个约定来进行测试：
1.当根节点为红时，返回false。
2.判断一个节点和其父节点的颜色是否都为红，若都为红返回false。
3.以最左的一条路径上的根节点数量为基准，通过递归遍历每一条路径上的根节点的数量，当每条路径遍历节点到空时，将两者进行比较，如果最终结果不相等则返回false。
bool IsBalance()
{
if (_root && _root->_col == Red)
{
cout << "根节点不是黑色的" << endl;
return false;
}
int banchmark = 0;
//以最右边一条路径为基准
Node* left = _root;
while (left)
{
if (left->_col == Black)
{
++banchmark;
}
left = left->_left;
}
int blackNum = 0;
return _IsBalance(_root, banchmark, blackNum);
}
bool _IsBalance(Node* root, int banchmark, int blackNum)
{
if (root == nullptr)
{
if (banchmark != blackNum)
{
cout << "黑色根节点数目不相等" << endl;
return false;
}
return true;
}
if (root->_col == Red && root->_parent->_col == Red)
{
cout << "出现连续的红色节点" << endl;
return false;
}
if (root->_col == Black)
{
++blackNum;
}
return _IsBalance(root->_left, banchmark, blackNum) && _IsBalance(root->_right, banchmark, blackNum);
}#define _CRT_SECURE_NO_WARNINGS 1
#include"RBtree.h"
#include<vector>
int main()
{
RBTree<int, int> t;
vector<int> v;
srand(time(0));
int N = 100000;
int count = 0;
for (int i = 0; i < N; i++)
{
v.push_back(rand());
}
for (auto e : v)
{
pair<int,int> kv(e, e);
t.insert(kv);
if (t.IsBalance())
{
cout << "insert" << e << endl;
count++;
cout << count << endl;
}
else
{
cout << e << "插入失败" << endl;
cout << "不是平衡的" << endl;
break;
}
}
}#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
enum Color
{
Red,
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(pair<K, V>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _col(Red)
, _kv(kv)
{}
};
template<class K,class V>
struct RBTree
{
typedef RBTreeNode<K, V> Node;
private:
Node* _root;
public:
RBTree()
:_root(nullptr)
{}
bool IsBalance()
{
if (_root && _root->_col == Red)
{
cout << "根节点不是黑色的" << endl;
return false;
}
int banchmark = 0;
//以最右边一条路径为基准
Node* left = _root;
while (left)
{
if (left->_col == Black)
{
++banchmark;
}
left = left->_left;
}
int blackNum = 0;
return _IsBalance(_root, banchmark, blackNum);
}
bool _IsBalance(Node* root, int banchmark, int blackNum)
{
if (root == nullptr)
{
if (banchmark != blackNum)
{
cout << "黑色根节点数目不相等" << endl;
return false;
}
return true;
}
if (root->_col == Red && root->_parent->_col == Red)
{
cout << "出现连续的红色节点" << endl;
return false;
}
if (root->_col == Black)
{
++blackNum;
}
return _IsBalance(root->_left, banchmark, blackNum) && _IsBalance(root->_right, banchmark, blackNum);
}
//右单旋
void RotateR(Node* parent)
{
Node* cur = parent->_left;
Node* curL = cur->_left;
Node* curR = cur->_right;
Node* parentParent = parent->_parent;
parent->_left = curR;
if (curR)
curR->_parent = parent;
cur->_right = parent;
parent->_parent = cur;
if (parent == _root)
{
_root = cur;
_root->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = cur;
cur->_parent = parentParent;
}
else if (parentParent->_right == parent)
{
parentParent->_right = cur;
cur->_parent = parentParent;
}
else
{
assert(false);
}
}
}
//左单旋
void RotateL(Node* parent)
{
Node* cur = parent->_right;
Node* curL = cur->_left;
Node* parentParent = parent->_parent;
parent->_right = curL;
if (curL)
curL->_parent = parent;
cur->_left = parent;
parent->_parent = cur;
if (parent == _root)
{
_root = cur;
_root->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = cur;
cur->_parent = parentParent;
}
else if (parentParent->_right == parent)
{
parentParent->_right = cur;
cur->_parent = parentParent;
}
else
{
assert(false);
}
}
}
bool insert(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);
cur->_col= Red;
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
cur->_parent = parent;
}
else
{
parent->_left = cur;
cur->_parent = parent;
}
while (parent && parent->_col == Red)
{
Node* grandfather = parent->_parent;
if (parent == grandfather->_left)
{
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
{
RotateL(parent);
RotateR(grandfather);
cur->_col = Black;
grandfather->_col = Red;
}
break;
}
_root->_col = Black;
}
else
{
Node* uncle = grandfather->_left;
//第一种情况
if (uncle && uncle->_col == Red)
{
parent->_col = uncle->_col = Black;
grandfather->_col = Red;
cur = grandfather;
parent = cur->_parent;
}
else
{
//第二种情况，左单旋
if (cur == parent->_right)
{
RotateL(grandfather);
parent->_col = Black;
grandfather->_col = Red;
}
//第三种情况，右左双旋
else
{
RotateR(parent);
RotateL(grandfather);
cur->_col = Black;
grandfather->_col = Red;
}
break;
}
_root->_col = Black;
}
}
}
};到此，关于“C++数据结构之红黑树如何实现”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注亿速云网站，小编会继续努力为大家带来更多实用的文章！
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。