数据结构：红黑树（Red Black Tree）
概念
红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。红黑树和AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。它可以在O(log n)时间内（它的查找最坏时间复杂度为O(2lgn)）做查找，插入和删除，这里的n 是树中元素的数目。
数据结构：
#pragma once
#define RED 0
#define BLACK 1
struct Node
{
Node(int key)
{
this->key=key;
}
int key;
int color;
Node* parent;
Node* left;
Node* right;
};
struct Tree
{
Tree()
{
}
Node* root;
Node* nil;
};性质
- 节点是红色或黑色。
- 根节点是黑色。
- 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
下图为一棵简易红黑树：
在这里插入图片描述
自平衡操作
红黑树总是通过旋转和变色操作达到自平衡
左旋： 以某个结点作为旋转结点，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。
//节点左旋
void LEFT_ROTATE(Tree* &T, Node* x){
Node* y;
y = x->right;
x->right = y->left;
if(y->left != T->nil)
y->left->parent = x;
y->parent = x->parent;
if(x->parent == T->nil)
T->root = y;
else if(x == x->parent->left)
x->parent->left = y;
else
x->parent->right = y;
y->left = x;
x->parent = y;
}右旋： 以某个结点作为旋转结点，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。
//节点右旋
void RIGHT_ROTATE(Tree* &T, Node* y){
Node *x;
x = y->left;
y->left = x->right;
if(x->right! = T->nil)
x->right->parent = y;
x->parent = y->parent;
if(y->parent == T->nil)
T->root = x;
else if(y == y->parent->left)
y->parent->left = x;
else
y->parent->right = x;
x->right = y;
y->parent = x;
}变色： 结点的颜色由红变黑或由黑变红。
//红黑树调整
void RB_INSERT_FIXUP(Tree* &T, Node* z){
Node* y;
while(z -> parent -> color == RED){
if(z -> parent == z -> parent -> parent -> left){ //z节点父节点为其祖父节点的左孩子
y = z -> parent -> parent -> right;
if(y -> color == RED){ //case1
z -> parent -> color = BLACK;
y -> color = BLACK;
z -> parent -> parent -> color = RED;
z = z -> parent -> parent;
}
else{
if(z == z -> parent -> right){ //case2
z = z -> parent;
LEFT_ROTATE(T,z);
}
z -> parent -> color = BLACK; //case3
z -> parent -> parent -> color = RED;
RIGHT_ROTATE(T, z -> parent -> parent);
}
}
else{ //z节点父节点为其祖父节点的右孩子
y = z -> parent -> parent -> left;
if(y -> color == RED){ //case 1
z -> parent -> color = BLACK;
y -> color = BLACK;
z -> parent -> parent -> color = RED;
z = z -> parent -> parent;
}
else{
if(z == z -> parent -> left){ //case2
z = z -> parent;
RIGHT_ROTATE(T, z);
}
z -> parent -> color = BLACK; //case3
z -> parent -> parent -> color = RED;
LEFT_ROTATE(T, z -> parent -> parent);
}
}
}
T -> root -> color = BLACK;
}下图是以P为旋转结点进行左旋和右旋操作：
在这里插入图片描述
在这里插入图片描述
红黑树插入
红黑树插入操作分为两部分：查找插入位置；插入自平衡。
- 从根结点开始查找；
- 若根结点为空，则插入结点作为根结点，结束。
- 若根结点不为空，则把根结点作为当前结点；
- 若当前结点为null，则返回当前结点的父结点，结束。
- 若当前结点key等于查找key，则该key所在结点就是插入结点，更新结点的值，结束。
- 若当前结点key大于查找key，把当前结点的左子结点设置为当前结点，重复操作4；
- 若当前结点key小于查找key，把当前结点的右子结点设置为当前结点，重复操作4；
红黑树查找
与二叉平衡树的查找无异
- 从根结点开始查找，把根结点设置为当前结点；
- 若当前结点为空，则返回NULL；
- 若当前结点不为空，用当前结点的key跟查找key作比较；
- 若当前结点key等于查找key，则该key即为查找目标，返回当前结点；
- 若当前结点key大于查找key，把当前结点的左子结点设置为当前结点，重复操作2；
- 若当前结点key小于查找key，把当前结点的右子结点设置为当前结点，重复操作2；
红黑树删除
- 若删除结点无子结点，直接删除。
- 若删除结点只有一个子结点，用子结点替换删除结点。
- 若删除结点有两个子结点，用后继结点（大于删除结点的最小结点，也是删除结点的右子树中的最左结点）替换删除结点。
- 删除结点用其唯一的子结点替换，子结点替换为删除结点后，可以认为删除的是子结点，若子结点又有两个子结点，则转换为操作3，一直自顶向下转换，最终转换为操作1。
在这里插入图片描述
注
由于本人懒惰成性，本文图片均摘自 https://www.jianshu.com/p/e136ec79235c （侵联删）。更详细的红黑树相关操作请参考上述网址，本文仅限个人学习总结之用。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019-07-29，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录