目录
1.红黑树概念
- 红黑树是一种二叉搜索树，但在每个结点上增加了一个存储位用于表示结点的颜色，这个颜色可以是红色的，也可以是黑色的，因此我们称之为红黑树。
- 红黑树通过对任何一条从根到叶子的路径上各个结点着色方式的限制，确保没有一条路径会比其他路径长出两倍，因此红黑树是近似平衡的。
2.红黑树的性质
(1)红黑树有以下五点性质：
- 每个结点不是红色就是黑色。
- 根结点是黑色的。
- 如果一个结点是红色的，则它的两个孩子结点是黑色的。(没有连续的红色节点)
- 对于每个结点，从该结点到其所有后代叶子结点的简单路径上，均包含相同数目的黑色结点。(每条路径上都包含相同的黑色节点)
- 每个叶子结点都是黑色的（此处的叶子结点指定是空结点）。(遇到空才算一条路径)
(2)红黑树如何确保从根到叶子的最长可能路径不会超过最短可能路径的两倍？
- 根据没有连续的红色节点和每条路径上有相同的黑色节点
- 最短路径:全是黑的
- 最长路径:一黑一红，红色节点和黑色节点的数量相同
- 正常红黑树中，不—定有全黑的最短路径和一黑—红的最长路径这个只是我们理想情况。
3.红黑树结点定义
- 这里直接实现KV模型的红黑树，为了方便后序的旋转操作，将红黑树的结点定义为三叉链结构，除此之外还新加入了一个成员变量，用于表示结点的颜色
template<class K, class V>
struct RBTreeNode
{
//三叉链
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
//存储的键值对
pair<K, V> _kv;
//结点的颜色
int _col; //红/黑
//构造函数
RBTreeNode(const pair<K, V>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _col(RED)
{}
};- 使用枚举来定义结点的颜色，这样可以增加代码的可读性和可维护性，并且便于后序的调试操作。
//枚举定义结点的颜色
enum Colour
{
RED,
BLACK
};
为什么构造结点时，默认将结点的颜色设置为红色？
- 若我们插入的是黑色结点，那么插入路径上黑色结点的数目就比其他路径上黑色结点的数目多了一个，即破坏了红黑树的性质4，此时我们就需要对红黑树进行调整。
- 若我们插入红黑树的结点是红色的，此时如果其父结点也是红色的，那么表明出现了连续的红色结点，即破坏了红黑树的性质3，此时我们需要对红黑树进行调整；但如果其父结点是黑色的，那我们就无需对红黑树进行调整，插入后仍满足红黑树的要求。
- 插入黑色结点，一定破坏红黑树的性质4，必须对红黑树进行调整。(影响很大)
- 插入红色结点，可能破坏红黑树的性质3，可能对红黑树进行调整。(影响不大)
4.红黑树的插入
红黑树插入结点的逻辑分为三步：
- 按二叉搜索树的插入方法，找到待插入位置。
- 将待插入结点插入到树中。
- 若插入结点的父结点是红色的，则需要对红黑树进行调整。
其中前两步与二叉搜索树插入结点时的逻辑相同，红黑树的关键在于第三步对红黑树的调整。
约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点
注意:此处所看到的树可能是一颗完整的树，也可能是一颗子树
红黑树在插入结点后是如何调整
- parent颜色是黑色，不需要调整，插入完成
- parent颜色是红色，违反规则3，需要处理
- 因为插入结点的父结点是红色的，说明父结点不是根结点（根结点是黑色的），因此插入结点的祖父结点（父结点的父结点）就一定存在。
- 红黑树调整时具体应该如何调整，主要是看插入结点的叔叔（插入结点的父结点的兄弟结点），根据插入结点叔叔的不同，可将红黑树的调整分为三种情况。
(1)叔叔存在且为红 ，cur为红，p为红，g为黑
- 此时为了避免出现连续的红色结点，我们可以将父结点变黑，但为了保持每条路径黑色结点的数目不变，因此我们还需要将祖父结点变红，再将叔叔变黑。这样一来既保持了每条路径黑色结点的数目不变，也解决了连续红色结点的问题。(p,u变黑，g变红)
- 但调整还没有结束，因为此时祖父结点变成了红色，如果祖父结点是根结点，那我们直接再将祖父结点变成黑色即可，此时相当于每条路径黑色结点的数目都增加了一个。
- (如果g是根节点，调整完成后，需要将g改为黑色)
- 但如果祖父结点不是根结点的话，我们就需要将祖父结点当作新插入的结点，再判断其父结点是否为红色，若其父结点也是红色，那么又需要根据其叔叔的不同，进而进行不同的调整操作。
- (如果g是子树，g一定有双亲，且g的双亲如果是红色，需要继续向上调整)
(2) 叔叔存在且为黑/不存在，cur为红，p为红，g为黑
说明: u的情况有两种
- 1.如果u节点不存在，则cur一定是新插入节点，因为如果cur不是新插入节点，则cur和p一定有一个节点的颜色是黑色，就不满足性质4:每条路径黑色节点个数相同。
- ⒉.如果u节点存在，则其一定是黑色的，那么cur节点原来的颜色一定是黑色的，现在看到其是红色的原因是因为cur的子树在调整的过程中将cur节点的颜色由黑色改成红色。
- p为g的左孩子，cur为p的左孩子，则进行右单旋转
- p为g的右孩子，cur为p的右孩子，则进行左单旋转
- p、g变色--p变黑，g变红
(3)叔叔存在且为黑/不存在，cur为红，p为红，g为黑
- 情况2,3其实是一样的，只不过: 2是直线，3是折线
- p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；
- p为g的右孩子，cur为p的左孩子，则针对p做右单旋转;
- 最后转化为了情况2
(4)代码
//插入函数
pair<Node*, bool> Insert(const pair<K, V>& kv)
{
if (_root == nullptr) //若红黑树为空树，则插入结点直接作为根结点
{
_root = new Node(kv);
_root->_col = BLACK; //根结点必须是黑色
return make_pair(_root, true); //插入成功
}
//1、按二叉搜索树的插入方法，找到待插入位置
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (kv.first < cur->_kv.first) //待插入结点的key值小于当前结点的key值
{
//往该结点的左子树走
parent = cur;
cur = cur->_left;
}
else if (kv.first > cur->_kv.first) //待插入结点的key值大于当前结点的key值
{
//往该结点的右子树走
parent = cur;
cur = cur->_right;
}
else //待插入结点的key值等于当前结点的key值
{
return make_pair(cur, false); //插入失败
}
}
//2、将待插入结点插入到树中
cur = new Node(kv); //根据所给值构造一个结点
Node* newnode = cur; //记录新插入的结点（便于后序返回）
if (kv.first < parent->_kv.first) //新结点的key值小于parent的key值
{
//插入到parent的左边
parent->_left = cur;
cur->_parent = parent;
}
else //新结点的key值大于parent的key值
{
//插入到parent的右边
parent->_right = cur;
cur->_parent = parent;
}
//3、若插入结点的父结点是红色的，则需要对红黑树进行调整
while (parent&&parent->_col == RED)
{
Node* grandfather = parent->_parent; //parent是红色，则其父结点一定存在
if (parent == grandfather->_left) //parent是grandfather的左孩子
{
Node* uncle = grandfather->_right; //uncle是grandfather的右孩子
if (uncle&&uncle->_col == RED) //情况1：uncle存在且为红
{
//颜色调整
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//继续往上处理
cur = grandfather;
parent = cur->_parent;
}
else //情况2+情况3：uncle不存在 + uncle存在且为黑
{
if (cur == parent->_left)
{
RotateR(grandfather); //右单旋
//颜色调整
grandfather->_col = RED;
parent->_col = BLACK;
}
else //cur == parent->_right
{
RotateLR(grandfather); //左右双旋
//颜色调整
grandfather->_col = RED;
cur->_col = BLACK;
}
break; //子树旋转后，该子树的根变成了黑色，无需继续往上进行处理
}
}
else //parent是grandfather的右孩子
{
Node* uncle = grandfather->_left; //uncle是grandfather的左孩子
if (uncle&&uncle->_col == RED) //情况1：uncle存在且为红
{
//颜色调整
uncle->_col = parent->_col = BLACK;
grandfather->_col = RED;
//继续往上处理
cur = grandfather;
parent = cur->_parent;
}
else //情况2+情况3：uncle不存在 + uncle存在且为黑
{
if (cur == parent->_left)
{
RotateRL(grandfather); //右左双旋
//颜色调整
cur->_col = BLACK;
grandfather->_col = RED;
}
else //cur == parent->_right
{
RotateL(grandfather); //左单旋
//颜色调整
grandfather->_col = RED;
parent->_col = BLACK;
}
break; //子树旋转后，该子树的根变成了黑色，无需继续往上进行处理
}
}
}
_root->_col = BLACK; //根结点的颜色为黑色（可能被情况一变成了红色，需要变回黑色）
return make_pair(newnode, true); //插入成功
}
//左单旋
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
//1、建立parent和subRL之间的关系
parent->_right = subRL;
if (subRL) //subRL可能为空
subRL->_parent = parent;
//2.记录pparent
Node* pparent = parent->_parent;
//3.建立parent和subR的关系
subR->_left = parent;
parent->_parent = subR;
//4.建立pparent和subR的关系
if (pparent == nullptr) //parent为根，是一颗单独的树
{
_root = subR;
subR->_parent = nullptr; //subR的_parent指向需改变
}
else
{
if (parent == pparent->_left)
{
pparent->_left = subR;
}
else //parent == pparent->_right
{
pparent->_right = subR;
}
subR->_parent = pparent;
}
}
//右单旋
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
//1.建立parent和subLR的关系
parent->_left = subLR;
if (subLR) //subLR可能为空
{
subLR->_parent = parent;
}
//2.记录pparent
Node* pparent = parent->_parent;
//3.建立subL和parent的关系
subL->_right = parent;
parent->_parent = subL;
//4.建立pparen和subL的关系
if (parent == _root) //parent是一颗独立的树
{
_root = subL;
_root->_parent = nullptr;
}
else //parent是一颗子树，
{
if (pparent->_left == parent)
{
pparent->_left = subL;
}
else
{
pparent->_right = subL;
}
subL->parent = pparent;
}
}
//左右双旋
void RotateLR(Node* parent)
{
RotateL(parent->_left);
RotateR(parent);
}
//右左双旋
void RotateRL(Node* parent)
{
RotateR(parent->_right);
RotateL(parent);
}
5.红黑树验证
(1)验证二叉树
- 红黑树也是一种特殊的二叉搜索树，获取二叉树的中序遍历序列，来判断该二叉树是否满足二叉搜索树的性质。
//中序遍历
void Inorder()
{
_Inorder(_root);
}
//中序遍历子函数
void _Inorder(Node* root)
{
if (root == nullptr)
return;
_Inorder(root->_left);
cout << root->_kv.first << " ";
_Inorder(root->_right);
}
(2)验证红黑树，是否满足那几个性质
//判断是否为红黑树
bool ISRBTree()
{
if (_root == nullptr) //空树是红黑树
{
return true;
}
if (_root->_col == RED)
{
cout << "error：根结点为红色" << endl;
return false;
}
//找最左路径作为黑色结点数目的参考值
Node* cur = _root;
int BlackCount = 0;
while (cur)
{
if (cur->_col == BLACK)
BlackCount++;
cur = cur->_left;
}
int count = 0;
return _ISRBTree(_root, count, BlackCount);
}
//判断是否为红黑树的子函数
bool _ISRBTree(Node* root, int count, int BlackCount)
{
if (root == nullptr) //该路径已经走完了
{
if (count != BlackCount)
{
cout << "error：黑色结点的数目不相等" << endl;
return false;
}
return true;
}
if (root->_col == RED&&root->_parent->_col == RED)
{
cout << "error：存在连续的红色结点" << endl;
return false;
}
if (root->_col == BLACK)
{
count++;
}
return _ISRBTree(root->_left, count, BlackCount)
&& _ISRBTree(root->_right, count, BlackCount);
}
6.红黑树的查找
- 本质还是搜索二叉树的查找
- 若树为空树，则查找失败，返回nullptr。
- 若key值小于当前结点的值，则应该在该结点的左子树当中进行查找。
- 若key值大于当前结点的值，则应该在该结点的右子树当中进行查找。
- 若key值等于当前结点的值，则查找成功，返回对应结点。
//查找函数
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (key < cur->_kv.first) //key值小于该结点的值
{
cur = cur->_left; //在该结点的左子树当中查找
}
else if (key > cur->_kv.first) //key值大于该结点的值
{
cur = cur->_right; //在该结点的右子树当中查找
}
else //找到了目标结点
{
return cur; //返回该结点
}
}
return nullptr; //查找失败
}
7.红黑树和AVL树比较
红黑树和AVL树都是高效的平衡二叉树，增删查改的时间复杂度都是O(logN)，但红黑树和AVL树控制二叉树平衡的方式不同：
- AVL树是通过控制左右高度差不超过1来实现二叉树平衡的，实现的是二叉树的严格平衡。
- 红黑树是通过控制结点的颜色，从而使得红黑树当中最长可能路径不超过最短可能路径的2倍，实现的是近似平衡。
相对于AVL树来说，红黑树降低了插入结点时需要进行的旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，实际运用时也大多用的是红黑树。
本文含有隐藏内容，请 开通VIP 后查看