红黑树
2015-02-07 17:28:01 最后更新: 2015-02-10 20:16:23 访问数量：2843
简介
我们知道，对于一棵高度为h的二叉查找树上的各种基本操作而言，其时间复杂度都是O(h)的，因此，怎样减小树的高度成为了降低时间复杂度的必要手段，因此，我们需要去找寻一种新的数据结构，让构造的二叉查找树接近满二叉树
红黑树就是一种基于二叉查找树的改进型数据结构，可以保证任何一个子树的高度不会比另一个高一倍以上，同时，就可以保证其上的基本操作的最坏时间复杂度为O(logn)
红黑树的五个条件
- 每个节点都有一个color域，要么为红，要么为黑
- 根节点是黑的
- 每个NULL节点都是黑的
- 如果一个节点是红的 ，那他的左右孩子都必须是黑的
- 对每个节点，从他开始到他的所有子孙的节点的路径上所包含的黑节点数目必须是相同的
旋转
对于红黑树，最关键的技术就是旋转
如图我们可以知道，A < X < B < Y < C，在旋转前后，完全符合二叉查找树的构造原则，但是，对于A、X、Y、C三个节点而言，高度发生了变化，通过不断的旋转，任意一颗二叉树最后都可以转化为完全二叉树
插入节点
因为红黑树是一棵特殊的二叉查找树，所以我们可以按照二叉查找树的插入方法对红黑树进行元素的插入
如果插入的元素的颜色设置为黑色，则会使各个支路的黑节点数量变得不同，而检测黑节点数量是件不太容易的事，因此我们应该将新插入的节点设置为红色，这样，对于原则中的1、3、5都不会影响，而不再成立的可能是2 -- 即当被插入元素为根节点时，或4 -- 即当被插入元素的父亲为红色时，如果被插入元素是根节点，那么其父亲一定是黑色，原则4保持正确，而如果被插入元素的父亲是红色，那被插入元素一定不是根节点，因此，2保持正确，所以，5个红黑树的构造原则中只有2或者4中的一个会被违反
当原则2被违反时，处理方法是很简单的，直接将root设置为黑色就可以了
而当原则4被违反时，处理方法就比较复杂了
根据被插入节点的叔叔的颜色，可以分为两种情况：
叔叔为红色
如图所示，这种情况中，我们已经知道被插入节点的父亲为红色，那么被插入节点的爷爷一定是黑色，而如果被插入节点的叔叔为黑色，那么只要将被插入节点的爷爷设置为红色，将被插入节点的叔叔和父亲都设置为黑色，这样，对于这个局部来说，5个原则全部满则，但是被插入节点的爷爷此时可能又会违反2或4，这个时候将被插入节点的爷爷看作是新的被插入节点重新进行即可
这样新的“被插入节点”会不断向上，直到完全符合5个原则，或者新的“被插入节点”是根节点，那么，最终将根节点变为黑色就可以了
叔叔为黑色
如图所示，对于新插入的节点B，如果他的父亲是红色，他的叔叔是黑色，那么他的叔叔一定是NULL节点，否则在B插入之前的这个局部就会违反原则4，因此经过旋转后到第三幅图即可
在整个算法的开始的地方有一个地方需要注意，那就是只有被插入节点的叔叔、父亲、爷爷都是存在的时候我们才能使用他们的各个域，那么他们是否存在呢？因为插入前，根节点为黑色，而被插入节点的父亲为红色，所以被插入节点的父亲一定不是根节点，所以被插入节点的父亲和爷爷都一定是存在的
删除节点
删除元素相对于元素的添加操作来说稍显复杂一些，首先我们的元素删除算法仍然使用二叉查找树的删除算法
根据二叉查找树的分析，我们可以知道对于被删除元素来说最多只会有一个子树，因此可以直接连接
如果被删除元素是红色，那么所有的五条红黑树的原则将都不会被破坏，因此只有当删除的元素为黑色时，我们才要进行处理
所以被删除元素的一条支路上首先存在的问题是将会比别的支路少一个黑节点就会破坏条件5，另外，由于黑叶子的父亲和孩子可能都是红色的，所以删除后还可能破坏条件4
所以我们不得不在考虑被删除元素的支路的同时考虑到他的兄弟支路
下面我们分各种情况进行探讨，这里，我们规定被删除元素为 y ，他的叶子为 x ，删除操作后 x 的兄弟为 w，并且只有y为黑色的情况我们才会进行下述探讨
因为 y 是黑色的，而删除前的红黑树符合红黑树的五个条件，因为 w 的支路上一定会比 x 支路上的黑叶子数多 1 个，所以 w 一定不为 NIL
X 为红色
如图所示，只要将 X 着为黑色即可，既可以让 X 路的黑叶子数目加 1，也可以解决可能的破坏条件 4 的情况
这个是最简单的情况
X 为黑色
当 X 为黑色的时候，条件 4 不会被破坏，只需要解决条件 5 即可，要解决破坏条件 5 的情况，我们需要知道 W 的颜色情况
- W 为红色
如果 W 为红色，则 w 的两个孩子一定都不为 NIL，并且一定都是黑色的
如图所示，经过旋转与重新着色，很容易得道右边的情况，对于右边的情况，任何一条支路的黑叶子树与原情况相同，X 支路仍然缺少一个黑叶子，但是此时，X 的兄弟已经从原来的红色的变成了现在的黑色（由原来的 W 变成了 W 的左孩子），因此我们进入了新的情况
- W 为黑色
当 W 为黑色时，他的两个孩子就会有几种情况：均为黑色、左红右黑、左黑右红
- W 的左右叶子均为黑色
如图所示，我们将 W 着为红色，这样对于x的父亲 Z 来说，整个少了1个黑叶子，这样我们只要对 Z 进行递归，最终当 X 为 root 时，我们只要简单的将 X 设置为黑色即可
- W 为左红右黑
如图所示，经过简单的旋转与重新着色，各个支路的黑叶子数没有发生变化，但是此时，X 的兄弟变成了 W 的左孩子 A，并且进入下一情况，A 的孩子为左黑右红
- W 为左黑右红
如图所示，经过旋转与重新着色，各个支路的黑叶子数没有变化，X 路的黑叶子数增加了 1，整个红黑树符合红黑树的 5 个条件，操作完成！
当然，我们对于这一情况可以发现，节点B的颜色对于结果来说并没有影响，因此，对于下一种情况，解法是相同的
- W 左右均为红色
程序示例
* file: function.h
* author: 龙泉居士
* date: 2013-01-27 20:02
*/
#ifndef FUNCTION_H_20130120
#define FUNCTION_H_20130120
#include <vector>
using std::vector;
class RB_tree
{
struct Node
{
Node();
Node(int);
int value;
bool isblack;
Node *left;
Node *right;
Node *father;
};
Node *root;
void left_roll (Node*);
void right_roll (Node*);
void in_fixup (Node*);
void re_fixup (Node*, Node*);
public:
RB_tree ();
RB_tree (vector<int>);
void insert (int);
void remove (int);
void remove (Node*);
void clear();
Node *find (int);
int get_value(Node *);
void pre_print();
void mid_print();
~RB_tree();
};
#endif
/*
* file: function.cc
* author: 龙泉居士
* date: 2013-01-27 20:03
*/
#include <iostream>
#include <stack>
#include <vector>
#include "function.h"
using namespace std;
RB_tree::Node::Node():isblack(false), left(NULL), right(NULL), father(NULL) {}
RB_tree::Node::Node(int v):value(v), isblack(false), left(NULL), right(NULL), father(NULL) {}
RB_tree::RB_tree():root(NULL) { }
RB_tree::RB_tree(vector<int> ivec):root(NULL)
{
for (size_t i=0; i<ivec.size(); ++i)
insert (ivec.at(i));
}
void RB_tree::left_roll (RB_tree::Node *x)
{
if (x == NULL || x->right == NULL)
return;
RB_tree::Node *y = x->right;
x->right = y->left;
if (y->left != NULL)
y->left->father = x;
y->left = x;
y->father = x->father;
if (root == x)
root = y;
else
{
if (x == x->father->left)
x->father->left = y;
else
x->father->right = y;
}
x->father = y;
}
void RB_tree::right_roll (RB_tree::Node *y)
{
if (y == NULL || y->left == NULL)
return;
RB_tree::Node *x = y->left;
y->left = x->right;
if (x->right != NULL)
x->right->father = y;
x->right = y;
x->father = y->father;
if (root == y)
root = x;
else
{
if (y == y->father->left)
y->father->left = x;
else
y->father->right = x;
}
y->father = x;
}
void RB_tree::insert (int v)
{
RB_tree::Node *x = root;
RB_tree::Node *y = NULL;
RB_tree::Node *n = new RB_tree::Node(v);
if (root == NULL)
{
root = n;
n->isblack = true;
return;
}
while (x!=NULL)
{
y = x;
if (v <= x->value)
x = x->left;
else
x = x->right;
}
if (y == NULL)
root = n;
else
{
n->father = y;
if (v <= y->value)
y->left = n;
else
y->right = n;
}
in_fixup (n);
}
void RB_tree::in_fixup (RB_tree::Node *n)
{
if (n == root)
{
n->isblack = true;
return;
}
if (n->father->isblack)
return;
if (n->father == n->father->father->left)
{
RB_tree::Node *y = n->father->father->right;
if (y == NULL)
{
if (n == n->father->right)
left_roll(n->father);
else
n = n->father;
right_roll (n->father);
n->isblack = true;
n->right->isblack = false;
}
else
{
y->isblack = true;
n->father->isblack = true;
y->father->isblack = false;
in_fixup (y->father);
}
}
else
{
RB_tree::Node *y = n->father->father->left;
if (y == NULL)
{
if (n == n->father->left)
right_roll(n->father);
else
n = n->father;
left_roll (n->father);
n->isblack = true;
n->left->isblack = false;
}
else
{
y->isblack = true;
n->father->isblack = true;
y->father->isblack = false;
in_fixup (y->father);
}
}
}
void RB_tree::remove (RB_tree::Node *n)
{
if (n == NULL)
return;
RB_tree::Node *y = n->right;
RB_tree::Node *w, *x = y->left;
if (y == NULL)
{
y = n;
if (x!=NULL)
x -> father = y->father;
if (y == y->father->left)
{
y -> father -> left = x;
w = y->father->right;
}
else
{
y -> father -> right = x;
w = y->father->left;
}
}
else
{
while (x!=NULL)
{
y = x;
x = x->left;
}
n->value = y->value;
x = y->right;
if (y == n->right)
{
n->right = x;
w = n->left;
}
else
{
y->father->left = x;
w = y->father->right;
}
if (x != NULL)
x->father = n;
}
if (y->isblack && y->father!=NULL)
re_fixup (x, w);
delete y;
if (root != NULL)
root -> isblack = true;
}
void RB_tree::re_fixup (RB_tree::Node *x, RB_tree::Node *w)
{
if (x!=NULL && x->isblack==false)
x->isblack = true;
else if (w == w->father->right)
{
RB_tree::Node *a = w->left;
RB_tree::Node *b = w->right;
if (!w->isblack)
{
left_roll (w->father);
w->isblack = true;
w->left->isblack = false;
re_fixup(x, a);
}
else
{
if (a->isblack && b->isblack)
{
w->isblack = false;
a = w->father;
if (a != root)
{
if (a == a->father->left)
w = a->father->right;
else
w = a->father->left;
re_fixup(a, w);
}
}
else if (a->isblack == false && b->isblack == true)
{
right_roll (w);
w->isblack = false;
a->isblack = true;
re_fixup(x, a);
}
else
{
left_roll (w->father);
w->isblack = w->left->isblack;
w->left->isblack = true;
b->isblack = true;
}
}
}
else
{
RB_tree::Node *a = w->left;
RB_tree::Node *b = w->right;
if (!w->isblack)
{
right_roll(w->father);
w->right->isblack = false;
w->isblack = true;
re_fixup (x, b);
}
else
{
if (a->isblack && b->isblack)
{
w->isblack = false;
a = w->father;
if (a!=root)
{
if (a == a->father->left)
w = a->father->right;
else
w = a->father->left;
re_fixup (a, w);
}
}
else if (a->isblack && b->isblack == false)
{
left_roll(w);
w->isblack = false;
b->isblack = true;
re_fixup (x, b);
}
else
{
right_roll (w->father);
w->isblack = w->right->isblack;
a->isblack = true;
}
}
}
}
void RB_tree::remove(int v)
{
remove (find(v));
}
RB_tree::Node* RB_tree::find (int v)
{
RB_tree::Node *tmp = root;
while (tmp != NULL)
{
if (v == tmp->value)
return tmp;
else if (v < tmp->value)
tmp = tmp->left;
else
tmp = tmp->right;
}
return NULL;
}
void RB_tree::pre_print ()
{
RB_tree::Node *n = root;
stack<RB_tree::Node *> s;
while (1)
{
while (n!=NULL)
{
cout << n->value << '-' << flush;
if (n->isblack)
cout << "black " << flush;
else
cout << "red " << flush;
s.push(n);
n = n->left;
}
n = s.top()->right;
s.pop();
if (s.empty() && n==NULL)
break;
}
cout << endl;
}
void RB_tree::mid_print ()
{
RB_tree::Node *n = root;
stack<RB_tree::Node *> s;
while (1)
{
while (n!=NULL)
{
s.push (n);
n = n->left;
}
n = s.top();
cout << n->value << '-' << flush;
if (n->isblack)
cout << "black " << flush;
else
cout << "red " << flush;
n = n->right;
s.pop();
if (s.empty() && n==NULL)
break;
}
cout << endl;
}
void RB_tree::clear ()
{
RB_tree::Node *n = root;
stack<RB_tree::Node *> s;
while (1)
{
while (n != NULL)
{
s.push (n);
n = n->left;
}
n = s.top() -> right;
delete s.top();
s.pop();
if (s.empty() && n==NULL)
break;
}
root = NULL;
}
RB_tree::~RB_tree ()
{
clear();
}
微信公众号
欢迎关注微信公众号，以技术为主，涉及历史、人文等多领域的学习与感悟，每周三到七篇推文，只有全部原创，只有干货没有鸡汤
