顾得泉：个人主页
个人专栏：《Linux操作系统》 《C++从入门到精通》 《LeedCode刷题》
键盘敲烂，年薪百万！
一、红黑树的概念与性质
1.概念
2.性质
二、红黑树结构
为了后续实现关联式容器简单，红黑树的实现中增加一个头结点，因为跟节点必须为黑色，为了与根节点进行区分，将头结点给成黑色，并且让头结点的 pParent 域指向红黑树的根节点，pLeft域指向红黑树中最小的节点，_pRight域指向红黑树中最大的节点，如下：
三、红黑树的相关实现
1. 红黑树节点的定义
想要实现一颗红黑树 ，首先我们得有树的节点，而树的节点中我们需要存：该节点的父节点、该节点的右孩子、该节点的左孩子、树节点的颜色以及数据类型；代码如下：
enum COLOUR
{
RED,
BLACK
};
template<class K, class V>
struct RBTreeNode
{
RBTreeNode<K, V>* _parent;
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
COLOUR _col;
pair<K, V> _kv;
RBTreeNode(const pair<K, V>& kv)
:_parent(nullptr)
, _left(nullptr)
, _right(nullptr)
, _kv(kv)
, _col(RED)
{}
};2. 红黑树的定义
红黑树的定义如下：
template<class K, class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
private:
Node* _root = nullptr;
};3. 红黑树的插入
因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论：
约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点
情况一
cur为红，p为红，g为黑，u存在且为红
情况二
cur为红，p为红，g为黑，u不存在/u存在且为黑
情况三
cur为红，p为红，g为黑，u不存在/u存在且为黑
4.代码实现
template<class K, class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
public:
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = BLACK;
return true;
}
// 找到插入位置
Node* cur = _root, * parent = nullptr;
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 > cur->_kv.first)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = parent;
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
// g
// p u
// c
if (grandfather->_left == parent)
{
Node* uncle = grandfather->_right;
// 情况1、uncle 存在且为红
// 不需要旋转
if (uncle && uncle->_col == RED)
{
// 变色
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
// 继续往上更新处理
cur = grandfather;
parent = cur->_parent;
}
else
{
// 情况2.1
// 单旋
// g
// p
// c
if (cur == parent->_left)
{
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
// 情况3.1
// 双旋
// g
// p
// c
else
{
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
// grandfather->_right == parent
// g
// u p
// c
else
{
Node* uncle = grandfather->_left;
// uncle 存在且为红
// 不需要旋转
if (uncle && uncle->_col == RED)
{
// 变色
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
// 继续往上处理
cur = grandfather;
parent = cur->_parent;
}
// uncle 存在且为黑 或者 uncle 不存在
else
{
// 情况2.2
// 单旋
// g
// u p
// c
if (cur == parent->_right)
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
// 情况3.2
// 双旋
// g
// u p
// c
else
{
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)
return false;
// 先统计一条路径的黑色节点，与其它路径的比较
int refVal = 0;
Node* cur = _root;
while (cur)
{
if (cur->_col == BLACK)
{
refVal++;
}
cur = cur->_left;
}
int blacknum = 0;
return Check(_root, blacknum, refVal);
}
// 获取树的高度
int Height()
{
return _Height(_root);
}
// 获取树的节点数
size_t Size()
{
return _Size(_root);
}
// 查找
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 NULL;
}
private:
// 获取树的节点个数
size_t _Size(Node* root)
{
if (root == NULL)
return 0;
return _Size(root->_left)
+ _Size(root->_right) + 1;
}
// 获取树的高度
int _Height(Node* root)
{
if (root == nullptr)
return 0;
int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
// 检查是否符合红黑树规则
bool Check(Node* root, int blacknum, int refVal)
{
if (root == nullptr)
{
if (blacknum != refVal)
{
cout << "存在黑色节点数量不相等的路径" << endl;
return false;
}
return true;
}
if (root->_col == RED && root->_parent->_col == RED)
{
cout << "有连续的红色节点" << endl;
return false;
}
if (root->_col == BLACK)
{
blacknum++;
}
return Check(root->_left, blacknum, refVal)
&& Check(root->_right, blacknum, refVal);
}
// 按中序遍历打印树的节点
void _Inorder(Node* root)
{
if (root == nullptr)
return;
_Inorder(root->_left);
cout << root->_kv.first << " ";
_Inorder(root->_right);
}
// 左单旋
void RotateL(Node* parent)
{
Node* subR = parent->_right, * subRL = subR->_left;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
subR->_left = parent;
Node* parentParent = parent->_parent;
parent->_parent = subR;
// 如果 parent 是根节点，就直接更新 subR 为根节点，并将 subR 的_parent指向空
if (_root == parent)
{
_root = subR;
subR->_parent = nullptr;
}
// 否则，先判断 parent 是 parentParent 的右还是左，再将parentParent的左或者右连接subR
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subR;
}
else
{
parentParent->_right = subR;
}
subR->_parent = parentParent;
}
}
// 右单旋
void RotateR(Node* parent)
{
Node* subL = parent->_left, * subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
subL->_right = parent;
Node* parentParent = parent->_parent;
parent->_parent = subL;
if (_root == parent)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subL;
}
else
{
parentParent->_right = subL;
}
subL->_parent = parentParent;
}
}
private:
Node* _root = nullptr;
};四、红黑树与AVL树的比较
红黑树和AVL树都是自平衡二叉查找树，它们都能在插入和删除操作后通过旋转来维持树的平衡，保证查找、插入和删除操作的时间复杂度大致为( O(\log n) )。然而，它们在实现方式和具体性能上存在一些差异：
平衡性：
旋转操作：
空间开销：
应用场景：
结语：C++关于如何实现红黑树的分享到这里就结束了，希望本篇文章的分享会对大家的学习带来些许帮助，如果大家有什么问题，欢迎大家在评论区留言~~~