【C++】红黑树
目录
一、认识红黑树：
1、红黑树概念：
1、红黑树也是一颗搜索二叉树，它将每一个节点加上了颜色的属性（黑色和红色），通过对从根到任何一个空节点的路径上每一个节点的着色的限制，来保证最长的路径不会长于最短路径的两倍。
2、与AVL树不同，红黑不用进行多次的翻旋转，也就是说不用像AVL树那样限制得极度苛刻，也就是说高度会比AVL树高一点，也就是搜索效率可能会低，但是那几乎几十次搜索次数在如今的计算机中几乎可以忽略不计，但是红黑树不像AVL树那样动不动就旋转，旋转次数较少，所以红黑树的插入和删除优先于AVL树。
接下来看看红黑树的全貌：
2、红黑树的性质：
1、每个结点不是红色就是黑色
2、根节点是黑色的
3、如果一个节点是红色的，则它的两个孩子结点是黑色的（没有连续的红节点）
4、对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点 5、每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
如下图所示：
最长路径：红黑相间的路径
最短路径：全是黑节点的路径
如上所示，如果是AVL树就必须要进行旋转了，但是如果是红黑树，并没有违背性质，就不需要进行旋转，这样，在很复杂的插入和删除场景中，红黑树的旋转次数就大大少于AVL树，所以在实际中红黑树性能更好，适用性更强。
3、红黑树节点的定义：
和AVL树总体差不多，都是通过三个指针控制的，相比于AVL树，红黑树是通过颜色来进行旋转插入等的判断的。
以下是单个节点的代码实现：
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(const pair<K, V>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, col(RED)
{}
};二、红黑树的插入：
1、插入注意事项：
1、插入节点的时候，可以是红色节点或者是黑色节点
如果是红色节点：那么如果这个新节点的父节点是黑色的就没问题，但是如果是红色的父节点那么就违反了红黑树的第三性质
如果是黑色节点：那么新插入的节点所在的路径黑色节点的个数多了一个，但是其他节点的个数都没变，就必然违反了红黑树的第四性质。
所以在插入的过程中就将新插入的节点标记为红色，这样进行操作的时候就方便一些。
2、插入理解：
1、当新插入的红节点的父节点是黑色的时候不需要进行其他操作，不违反任意规则
2、当新插入的红节点的父节点是红色的时候，这个时候就要找对应的“叔叔”节点了（也就是新节点的父节点的父节点的另一个子节点的颜色）
情况一：当新插入节点的uncle存在，且是红节点
思路：
插入后看，如果父节点是红色的，那么将父节点的颜色变为黑色，那么父亲所在这个路径就会多一个黑节点出来，这个时候就将祖父的节点变为红色，父节点所在的路径有的黑节点就不变了，但是uncle的节点就会多一个黑节点，这样的话就将uncle的节点变为黑色就可以了
在处理完后，将grandfather修改为cur，之后继续判断cur的父亲继续向上处理：
继续向上处理规则：
1、grandfather没有父亲，grandfather就是根，将grandfather变黑即可
2、grandfather有父亲，父亲是黑色的，就结束了
3、grandfather有父亲，父亲是红色的就和上面类似的处理
对应的抽象图：
上述以及下面的各个抽象图关注的不在是高度了，关注的是每一颗树的黑色节点的数量，当黑色节点的数量为1的时候，就存在四种情况：
情况二：当新插入节点的uncle不存在
思路：
如果parent在grandfather的左边，cur在parent的左边
将grandfather进行右单旋，然后将parent变黑，grandfather变红。
思路：
如果parent在grandfather的左边，cur在parent的右边
将parent进行左单旋，再将grandfather进行右单旋，然后将cur变黑，grandfather变红。
当uncle存在且为黑：
如下：
c中每条路径包含一个黑色节点的红黑树，d和e可能是空树或者是红节点
思路：
首先在插入后向上调整的过程中才可能存在这种情况，这个时候先进行变色向上调整，碰到uncle是黑色的时候先判断是单旋还是双旋，之后进行对应的旋转，最后进行变色处理即可。
以下就是双旋的抽象图
在上述中判断是单旋或者双旋是通过指针的指向来判断的
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->_left;
}
else if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else
{
return false;
}
}
//走到这就是找到了
cur = new Node(kv);
cur->col = RED;
//再连接到这个红黑树中
if (parent->_kv.first > cur->_kv.first)
{
parent->_left = cur;
}
else//parent->_kv.first < cur->_kv.first
{
parent->_right = cur;
}
cur->_parent = parent;
//已经连接完成后
while (parent && parent->col == RED)
{
//这里祖父必定存在，因为如果进循环后parent就是red，然而red不可能为根节点，所以parent的parent必定存在
Node* grandfather = parent->_parent;
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
if (uncle && uncle->col == RED)
{
//修改颜色
uncle->col = BLACK;
parent->col = BLACK;
grandfather->col = RED;
//修改cur
cur = grandfather;
//修改parent继续指向cur的parent
parent = cur->_parent;
}
else//uncle不存在或者uncle为黑色就需要旋转了
{
if (cur == parent->_left)
{
RotateR(grandfather);
parent->col = BLACK;
grandfather->col = RED;
}
else//cur == parent->_right
{
RotateL(parent);
RotateR(grandfather);
cur->col = BLACK;
grandfather->col = RED;
}
break;
}
}
else//parent == grandfather->_right
{
Node* uncle = grandfather->_left;
if (uncle && uncle->col == RED)
{
//修改颜色
uncle->col = BLACK;
parent->col = BLACK;
grandfather->col = RED;
//修改cur
cur = grandfather;
//修改parent继续指向cur的parent
parent = cur->_parent;
}
else//uncle不存在或者uncle为黑色就需要旋转了
{
if (cur == parent->_right)
{
RotateL(grandfather);
parent->col = BLACK;
grandfather->col = RED;
}
else//cur == parent->_right
{
RotateR(parent);
RotateL(grandfather);
cur->col = BLACK;
grandfather->col = RED;
}
break;
}
}
}
_root->col = BLACK;
return true;
}红黑树中的旋转和AVL树基本思路是一样的，只不过一个改变的平衡因子一个改变的是着色
//左单旋
void RotateL(Node* parent)
{
Node* cur = parent->_right;
Node* curleft = cur->_left;
parent->_right = curleft;
if (curleft)
{
curleft->_parent = parent;
}
cur->_left = parent;
//将parent的父节点保存起来
Node* pparent = parent->_parent;
parent->_parent = cur;
if (parent == _root)
{
_root = cur;
cur->_parent = nullptr;
}
else
{
if (pparent->_kv.first < cur->_kv.first)
{
pparent->_right = cur;
}
else //if (pparent->_kv.first > cur->_kv.first)
{
pparent->_left = cur;
}
cur->_parent = pparent;
}
}
//右单旋
void RotateR(Node* parent)
{
Node* cur = parent->_left;
Node* curright = cur->_right;
parent->_left = curright;
if (curright)
{
curright->_parent = parent;
}
cur->_right = parent;
//将parent的父节点保存起来
Node* pparent = parent->_parent;
parent->_parent = cur;
if (parent == _root)
{
_root = cur;
cur->_parent = nullptr;
}
else
{
if (pparent->_kv.first < cur->_kv.first)
{
pparent->_right = cur;
}
else //if (pparent->_kv.first > cur->_kv.first)
{
pparent->_left = cur;
}
cur->_parent = pparent;
}
}三、红黑树的检查：
与AVL树不同的是，红黑树的检查是通过检查红黑树的性质有没有被违反的，主要是检查性质3和4。
性质三检查：
思路：
如果是找孩子节点是黑色的话不方便操作，所以可以反过来，每一个红节点的父节点存在，并且其父节点的颜色是红的就证明出现了连续的红节点，返回错误。接着依次向左子树和右子树递归。
性质四检查：
思路：
首先以一条路径上的黑节点的个数求基准值，接着每到空节点后，在返回上一层函数栈帧之前进行判断，如果这个基准值和这条路径上黑色节点的个数不同就返回错误。
bool CheckColor(Node* root, int blacknum, int benchmark)
{
if (root == nullptr)
{
if (blacknum != benchmark)
{
cout << "黑色节点的数量不匹配" << endl;
return false;
}
return true;
}
if (root->col == BLACK)
{
++blacknum;
}
if (root->col == RED && root->_parent && root->_parent->col == RED)
{
cout << root->_kv.first << "出现连续红色节点" << endl;
return false;
}
return CheckColor(root->_left, blacknum, benchmark)
&& CheckColor(root->_right, blacknum, benchmark);
}
bool IsRBTree()
{
return _IsRBTree(_root);
}
bool _IsRBTree(Node* root)
{
if (root == nullptr)
return true;
if (root->col == RED)
{
return false;
}
//基准值
int benchmark = 0;
Node* cur = _root;
while (cur)
{
if (cur->col == BLACK)
++benchmark;
cur = cur->_left;
}
return CheckColor(root, 0, benchmark);
}最后在主函数中进行随机值判断检查
四、红黑树和AVL树的比较：
红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O(log_2 N)，AVL树过于追求平衡了（高度差不超过1），红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数， 所以在经常进行增删的结构中性能比AVL树更优，实际运用中红黑树更多。
原文地址：https://blog.csdn.net/2303_80828380/article/details/142718549
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！