红黑树(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为旋转结点进行左旋和右旋操作:
红黑树插入操作分为两部分:查找插入位置;插入自平衡。
与二叉平衡树的查找无异
由于本人懒惰成性,本文图片均摘自 https://www.jianshu.com/p/e136ec79235c (侵联删)。更详细的红黑树相关操作请参考上述网址,本文仅限个人学习总结之用。