红黑树的分析与C语言实现
前言
红黑树是比较复杂的一种平衡树结构。容易看得云里雾里，让人望而却步。或是强记下来，终究不能理解而很快忘记了。
感觉开始最让人困惑的就是平白无故就得出了一堆性质，然后根据性质很不明所以地推导各种奇怪的操作步骤。这样几乎不可能理解其中的含义。
这是一个充斥着迷茫和痛苦的过程，我花了20多天的所有空余时间，画了二十几页的草稿。
红黑树来源于2-3-4树，是2-3-4树的一种表现形式。当节点为红色时，即表示此节点和父节点连结为2-3-4树中的一个节点，如下图。
在我的学习中，分析过程大约是：先理解2-3-4树的增加删除，再根据2-3-4树分析红黑树的增加删除，然后再研究学习算法导论中的增加删除流程。笔记也按这个过程来写。
相信前人就是这样推出来的，但我一时没有找到相关的资料，今天我们再推一遍。但是这个挑战也是很大的，不但要明白算法导论中的那种按红黑树5条性质推导了的流程，更要进一步搞清楚2-3-4树的流程与这些步骤的关系。
不过，虽然从5个性质来分析插入删除过程比较难明白其含义，但却是比较简单清晰的。
另外，还有2-3树扩展成的红黑树，比较少见。
现在，还有一种左偏红黑树，也是2-3-4树的扩展，不过3度节点转成红黑树的时候只允许红色节点左倾。这种新的树结构由Robert Sedgewick在2008年发表。实现难度比常见的红黑树要简单得多。这也是个算法大神，超级大神高德纳的学生，写有大量著名的算法教材。我就在看他的"算法-C语言实现(第三版)"。
2-3-4树的递归插入过程
2-3-4树的详细说明请看上一篇文章。
插入主要原则是，如果插入后节点不大于3个元素，则直接插入，如果节点大于3个元素，则分裂节点。
假设在如下2-3-4树中插入元素25，第一步查找到(22,24,29)节点
把元素25插入节点
由于节点现在有4个元素，大于最大元素数量3，所以当前节点分裂，把中间节点插入父节点
父节点的元素数量也大于3，跟上一个节点一样进行分裂
2-3-4树的递归删除过程
删除原理：
-
如果查找到的节点不是叶子节点，找到它的前继或后继的叶子节点，交换这两个节点。
-
如果叶子节点不少于2个元素，则直接删除
-
否则，叶子节点只有1个元素，尝试从兄弟取一个元素过来。
-
如果兄弟节点也只有1个元素，则从父节点取一个元素下来。
-
以父节点作为当前节点从第2步循环。尝试从父节点删除当才取出的元素。
假设在如下2-3-4树中删除元素12，查找到元素12
删除元素12形成一个空节点
由于兄弟也是一个元素，所以从父节点取一个节点，空节点上移。即父节点删除一个元素。当前节点指向空节点。
当前节点的兄弟节点(20,24)有两个元素，所以从兄弟节点取一个元素过来。此时删除完成。
再从2-3-4树中删除元素29， 查找到元素29
删除元素形成一个空节点
由于兄弟(22)也是一个元素，所以从父节点取一个节点形成一个新节点(22,24)，空节点上移。即父节点删除一个元素。当前节点指向空节点。
由于兄弟节点(14)也只有一个元素，所以从节点取一个节点形成新节点(14,20)，空节点上移。即父节点删除一个元素。当前节点指空节点
节点是根节点，高度减1。
2-3-4树的插入与红黑树的对应关系
当2-3-4树中的节点有1个元素时插入
当2-3-4树中的节点有2个元素时插入
当2-3-4树中的节点有3个元素时插入
红黑树的插入步骤的推导
由上一节的分析很容易可以发现
-
插入节点为红色。
-
如果插入节点的父节点是黑色时，直接插入不用做其它操作。
-
如果插入节点的父节点是红色时，其叔叔也是红色，则把父节点及叔叔节点设为黑色。
-
(这个忘了做图)如果插入节点的父节点是红色，其叔叔是黑色，则以父节点旋转。
2-3-4树的删除与红黑树的对应关系
1、当前节点有3个元素时
2、当前节点有2个元素时
3、当前节点有1个元素,兄弟节点有3个元素时
4、当前节点有1个元素,兄弟节点有2个元素时，此时节点可能左偏也可能右偏，且两种情况处理方法不同，下图取其中一种。另外一种与情况3的处理方法相同
5、当前节点有1个元素,兄弟节点有1个元素，而父节点有多个元素时。
6、当前节点有1个元素,兄弟节点有1个元素，而父节点有1个元素时。
7、当前节点有1个元素且是左子树,兄弟节点有1个元素，而父节点有2个元素，如果2-3-4树父节点对应红黑树中的红节点右偏，则需要如下图分析。红黑树需要先旋转成左偏的树，然后在左偏的树中删除A节点。
红黑树的删除步骤的推导
删除是是红黑树中比较复杂的。事实上想马上从上面的分析得出算法导论中的红黑树删除步骤是比较困难的，还有很多工作要做。情况比上面的所描述的要复杂。
但是对照算法导论中的步骤和上面的分析来研究，却要容易得多。通过上面分析总结和从算导中我们可以发现，在每个循环分析中，可以只研究删除节点的兄弟即可，而不用去管其父节点。以下都从删除节点是左子树讨论。
-
先使用二叉树的方法查找节点。如果不是叶子节点，查找后继的叶子节点并交换，删除交换后的叶子节点，并从删除后的节点开始修复红黑树。
-
当删除节点是红色时，直接删除。从上节情况1,2可以得出。
-
删除节点是黑色，且其兄弟也是黑色，兄弟的两个儿子也是黑色，则把兄弟设为红色，父节点设为黑色。以父节点为当前节点再进行修正。
-
删除节点是黑色，且其兄弟也是黑色。如果其兄弟的右孩子是红色，则以父节点旋转，并把父节点设置为红色。
-
删除节点是黑色，且其兄弟也是黑色。如果其兄弟的右孩子不是红色而左孩子是红色，则先以兄弟节点右旋转。把当前兄弟节点转换为步骤4的状态。从情况4可以得出。
-
删除节点是黑色，且其兄弟是红色。以父节点左旋转，变成红色节点左偏的树，转换到步骤3的状态。从情况7可以得出。
这个可以对应算法导论中删除步骤分析中的几种情况。
红黑树的性质
（1）每个节点或者是黑色，或者是红色。
（2）根节点是黑色。
（3）每个叶子节点（NIL）是黑色。 注意：这里叶子节点，是指为空的叶子节点。
（4）如果一个节点是红色的，则它的子节点必须是黑色的。
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
从2-3-4树与红黑树的对应关系，我们很容易理解这5条性质。
-
性质4，由于红色节点指向黑色节点来构成2-3-4树中的多度节点，所以连续的两个红色节点违反了定义，是不应该存在的。
-
性质5，由于2-3-4树是个平衡树，所以叶子的高度都相同，而2-3-4树中叶子的到根的路径与红黑树黑节点的路径是一致的。
红黑树性质分析的关键问题
插入的每次情况分析主要看叔叔，删除的每次情况只看兄弟
插入的核心思路是：将红色的节点移到根节点，然后，将根节点设为黑色
删除的核心思路是：将额外的黑色节点向上移动，直到遇到一个红色节点，就把这个红色节点设置为黑色的。但是过程中注意要把兄弟的黑色节点减少1。可以看作每次移动都是将额外的黑色节点移动到父节点所做的操作。
删除操作有几种情况相互转换。操作的一个重要目的是转换成一个更简单的可以处理的情况。
删除操作的情况有如下的转变。
case3->case4->case2->是红节点或是根
case1->case2->是红节点或是根
红黑树的旋转
我能说。。这个树的旋转都是一样的么。所以我下面就用了上次avl树那篇文章画的图。很简单。
左旋转
实现如下：
static void
rb_left_rotate(rb_tree_pt tree, rb_node_pt x)
{
rb_node_pt y = x->right;
x->right = y->left;
if (x->right != NULL) {
x->right->parent = x;
}
y->parent = x->parent;
if (x->parent == NULL) {
tree->root = y;
}
else {
if (x->parent->left == x) {
x->parent->left = y;
}
else {
x->parent->right = y;
}
}
y->left = x;
x->parent = y;
}
右旋转
实现如下：
static void
rb_right_rotate(rb_tree_pt tree, rb_node_pt y)
{
rb_node_pt x = y->left;
y->left = x->right;
if (y->left != NULL) {
y->left->parent = y;
}
x->parent = y->parent;
if (y->parent == NULL) {
tree->root = x;
}
else {
if (y->parent->left == y) {
y->parent->left = x;
}
else {
y->parent->right = x;
}
}
x->right = y;
y->parent = x;
}
通过红黑树性质分析插入步骤
-
将红黑树当作一颗二叉树，将节点插入。并将节点着色为"红色"。
-
对红黑树进行修正操作。
- 被插入的节点是根节点。直接把此节点涂为黑色
- 被插入的节点的父节点是黑色。什么也不需要做
-
被插入的节点的父节点是红色，此时，划分为以下3种情况
-
case1. 当前节点的父节点是红色，且当前节点的祖父节点的另一个子节点（叔叔节点）也是红色。
处理：将“父节点”设为黑色，“叔叔节点”设为黑色，“祖父节点”设为“红色”，将“祖父节点”设为“当前节点”(红色节点)，继续循环对当前节点操作。
-
case2. 当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的右孩子
处理：将“父节点”作为“新的当前节点”，以“新的当前节点”为支点进行左旋。
-
case3. 当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的左孩子
处理：将“父节点”设为“黑色”，“祖父节点”设为“红色”，以“祖父节点”为支点进行右旋。
-
从红黑树的5个性质来分析，以上过程并不难理解。
红黑树插入实现
/*
* Name: rb_tree_insert_fixup
* Description: 红黑树插入修正函数
*
*/
static void
rb_tree_insert_fixup(rb_tree_pt tree, rb_node_pt node)
{
rb_node_pt parent, gparent, uncle;
while ((parent = node->parent) && parent->color == RB_RED) {
gparent = parent->parent;
if (parent == gparent->left) {
uncle = gparent->right;
if (uncle && uncle->color == RB_RED) {
/* case 1 父节点和叔叔节点都是红色*/
parent->color = RB_BLACK;
uncle->color = RB_BLACK;
gparent->color = RB_RED;
node = gparent;
}
else {
if (parent->right == node) {
/* case 2 父节点是红色 ，叔叔节点是黑色，且当前节点是右孩子 */
rb_left_rotate(tree, parent);
node = parent;
parent = node->parent;
}
/* case 3 父节点是红色， 叔叔节点是黑色，且当前节点是左孩子 */
parent->color = RB_BLACK;
gparent->color = RB_RED;
rb_right_rotate(tree, gparent);
}
}
else {
uncle = gparent->left;
if (uncle && uncle->color == RB_RED) {
/* case 1 父节点和叔叔节点都是红色*/
parent->color = RB_BLACK;
uncle->color = RB_BLACK;
gparent->color = RB_RED;
node = gparent;
}
else {
if (parent->left == node) {
/* case 2 父节点是红色 ，叔叔节点是黑色，且当前节点是左孩子 */
rb_right_rotate(tree, parent);
node = parent;
parent = node->parent;
}
/* case 3 父节点是红色， 叔叔节点是黑色，且当前节点是右孩子 */
parent->color = RB_BLACK;
gparent->color = RB_RED;
rb_left_rotate(tree, gparent);
}
}
}
tree->root->color = RB_BLACK;
}
int
rb_tree_insert(rb_tree_pt tree, Item element)
{
rb_node_pt node = NULL, parent = NULL, tmp;
if ((node = rb_node_create(element, NULL, NULL, NULL)) == NULL) {
return -1;
}
tmp = tree->root;
while (tmp != NULL) {
parent = tmp;
if (item_cmp(element, tmp->data)) {
tmp = tmp->left;
}
else if (item_cmp(tmp->data, element)) {
tmp = tmp->right;
}
else {
return -1;
}
}
node->parent = parent;
if (parent == NULL) {
tree->root = node;
}
else {
if (item_cmp(element, parent->data)) {
parent->left = node;
}
else {
parent->right = node;
}
}
node->color = RB_RED;
rb_tree_insert_fixup(tree, node);
return 0;
}
通过红黑树性质分析删除步骤
-
将红黑树当作一颗二叉树，将节点删除。如果是叶子节点，就直接删除，如果是内部节点，就与其后继的叶子节点交换。删除交换后的节点。
-
从删除的节点开始向上修复红黑树。
- 如果当前节点是红节点。直接把当前节点设置为黑色。
- 如果当前节点是黑节点且是根，什么都不做。
- 如果当前节点是黑节点且不是根。有以下4种情况。
- Case 1. 如果兄弟节点是红色。将兄弟节点设为“黑色”，父节点设为“红色”，对父节点进行左旋，然后重新设置兄弟节点。
- Case 2. 兄弟节点是黑色，且兄弟节点的两个孩子都是黑色。将兄弟节点设为“红色”，设置父节点为当前节点。
- Case 3. 兄弟节点是黑色，且兄弟节点的左孩子是红色，右孩子是黑色的。将兄弟节点的左孩子设为“黑色”，兄弟节点设为“红色”，对兄弟节点进行右旋，然后重新设置兄弟节点。
- Case 4. 兄弟节点是黑色，且兄弟节点的右孩子是红色，兄弟节点的左孩子任意颜色。将父节点颜色赋值给兄弟节点，父节点设为“黑色”，兄弟节点的右子节设为“黑色”。对父节点进行左旋，设置当前节点为根节点。
这个比较难复杂一些。
第1步内部节点与后继叶子节点交换时，需要注意交换节点是否连续的问题，如下图
红黑树删除实现
static void
rb_tree_delete_fixup(rb_tree_pt tree, rb_node_pt node, rb_node_pt parent)
{
rb_node_pt sibling;
while ((!node || node->color == RB_BLACK) && node != tree->root) {
if (node == parent->left) {
sibling = parent->right;
if (sibling->color == RB_RED) {
/* case 1 兄弟是红色 */
sibling->color = RB_BLACK;
parent->color = RB_RED;
rb_left_rotate(tree, parent);
sibling = parent->right;
}
/* 上面已保证sibling一定为黑色 */
if ((!sibling->left || sibling->left->color == RB_BLACK) && (!sibling->right || sibling->right->color == RB_BLACK)) {
/* case 2 兄弟是黑色，且左孩子和右孩子是黑色 */
sibling->color = RB_RED;
node = parent;
parent = node->parent;
}
else {
if (!sibling->right || sibling->right->color == RB_BLACK) {
/* case 3 兄弟是黑色，且左孩子是红色，右孩子是黑色 */
sibling->color = RB_RED;
sibling->left->color = RB_BLACK;
rb_right_rotate(tree, sibling);
sibling = parent->right;
}
/* 经过case 3 的处理后，确保sibling的右孩子是红色 */
/* case 4 兄弟是黑色，且左孩子是黑色，右孩子是红色 */
sibling->color = parent->color;
sibling->right->color = RB_BLACK;
rb_left_rotate(tree, parent);
node = tree->root;
break;
}
}
else {
sibling = parent->left;
if (sibling->color == RB_RED) {
/* case 1 兄弟是红色 */
sibling->color = RB_BLACK;
parent->color = RB_RED;
rb_right_rotate(tree, parent);
sibling = parent->left;
}
/* 上面已保证sibling一定为黑色 */
if ((!sibling->left || sibling->left->color == RB_BLACK) && (!sibling->right || sibling->right->color == RB_BLACK)) {
/* case 2 兄弟是黑色，且左孩子和右孩子是黑色 */
sibling->color = RB_RED;
node = parent;
parent = node->parent;
}
else {
if (!sibling->left || sibling->left->color == RB_BLACK) {
/* case 3 兄弟是黑色，且右孩子是红色，左孩子是黑色 */
sibling->color = RB_RED;
sibling->right->color = RB_BLACK;
rb_left_rotate(tree, sibling);
sibling = parent->left;
}
/* 经过case 3 的处理后，确保sibling的左孩子是红色 */
/* case 4 兄弟是黑色，且右孩子是黑色，左孩子是红色 */
sibling->color = parent->color;
sibling->left->color = RB_BLACK;
rb_right_rotate(tree, parent);
node = tree->root;
break;
}
}
}
if (node) {
node->color = RB_BLACK;
}
}
static void
rb_transplant(rb_tree_pt tree, rb_node_pt node1, rb_node_pt node2)
{
if (node1->parent == NULL) {
tree->root = node2;
}
else if (node1->parent->left == node1) {
node1->parent->left = node2;
}
else {
node1->parent->right = node2;
}
if (node2) {
node2->parent = node1->parent;
}
}
void
rb_tree_delete(rb_tree_pt tree, Item element)
{
rb_node_pt node = NULL, temp = tree->root, replace, parent, child;
int color;
/* 找到删除节点 */
while (temp) {
if (item_cmp(element, temp->data)) {
temp = temp->left;
}
else if (item_cmp(temp->data, element)) {
temp = temp->right;
}
else {
node = temp;
break;
}
}
if (node == NULL) {
return;
}
parent = node->parent;
color = node->color;
if (node->left == NULL) {
child = node->right;
rb_transplant(tree, node, child);
}
else if (node->right == NULL) {
child = node->left;
rb_transplant(tree, node, child);
}
else {
/* 待删除节点的左右子节点都不为空的情况 */
replace = rb_tree_successor(node);
color = replace->color;
child = replace->right;
if (replace->parent == node) {
parent = replace;
}
else {
parent = replace->parent;
/* 用child节点替换replace节点 */
rb_transplant(tree, replace, child);
/* 设置replace替换node后的子节点 */
replace->right = node->right;
replace->right->parent = replace;
}
/* 用replace节点替换node节点 */
rb_transplant(tree, node, replace);
replace->left = node->left;
replace->left->parent = replace;
replace->color = node->color;
}
if (color == RB_BLACK) {
rb_tree_delete_fixup(tree, child, parent);
}
}
完整源码
/* rb_tree.h */
#ifndef RB_TREE_H
#define RB_TREE_H
#define RB_RED 0 /* 红色节点 */
#define RB_BLACK 1 /* 黑色节点 */
typedef int Item;
typedef struct rb_node_s* rb_node_pt;
typedef struct rb_node_s {
Item data;
unsigned char color;
rb_node_pt parent;
rb_node_pt left;
rb_node_pt right;
} rb_node_t;
typedef struct rb_tree_s* rb_tree_pt;
typedef struct rb_tree_s {
rb_node_pt root;
} rb_tree_t;
rb_tree_pt rb_tree_create();
int rb_tree_insert(rb_tree_pt tree, Item element);
void rb_tree_delete(rb_tree_pt tree, Item element);
rb_node_pt rb_tree_find(rb_tree_pt tree, Item element);
void rb_tree_destroy(rb_tree_pt tree);
void rb_tree_print(rb_tree_pt tree);
void rb_tree_export_dot(rb_tree_pt tree, char *filename, char *label);
#endif
rb_tree.h
/* rb_tree.c */
/*
* =====================================================================================
*
* Filename: rb_tree.c
*
* Description: 红黑树实现
*
* Version: 1.0
* Created: 2016-11-06 16:08
* Revision: none
* Compiler: gcc
*
* Author: simon
*
* =====================================================================================
*/
#include <stdio.h>
#include <stdlib.h>
#include "rb_tree.h"
/*
* 从小到大 ((a) < (b))
* 从大到小 ({a} > (b))
*
*/
#define item_cmp(a, b) ((a) < (b)) /* 从小到大 */
#define item_equal(a, b) ((a) == (b)) /* 检查是否相等 */
static rb_node_pt rb_node_create(Item element, rb_node_pt parent, rb_node_pt left, rb_node_pt right);
static rb_node_pt rb_tree_successor(rb_node_pt root);
static rb_node_pt rb_tree_predecessor(rb_node_pt root);
static rb_node_pt rb_tree_search(rb_node_pt root, Item element);
static void rb_left_rotate(rb_tree_pt tree, rb_node_pt x);
static void rb_right_rotate(rb_tree_pt tree, rb_node_pt y);
static void rb_tree_insert_fixup(rb_tree_pt tree, rb_node_pt node);
static void rb_tree_delete_fixup(rb_tree_pt tree, rb_node_pt node, rb_node_pt parent);
static void rb_transplant(rb_tree_pt tree, rb_node_pt node1, rb_node_pt node2);
rb_tree_pt rb_tree_create()
{
rb_tree_pt tree = (rb_tree_pt)malloc(sizeof(rb_tree_t));
if (tree == NULL) {
return NULL;
}
tree->root = NULL;
return tree;
}
/*
* Name: rb_node_create
* Description: 创建新的节点
*
*/
static rb_node_pt
rb_node_create(Item element, rb_node_pt parent, rb_node_pt left, rb_node_pt right)
{
rb_node_pt node = (rb_node_pt)malloc(sizeof(rb_node_t));
if (node == NULL) {
return NULL;
}
node->data = element;
node->parent = parent;
node->left = left;
node->right = right;
node->color = RB_BLACK;
return node;
}
/*
* Name: rb_tree_successor
* Description: 找结点的后继结点
*
*/
static rb_node_pt
rb_tree_successor(rb_node_pt root)
{
rb_node_pt node;
if (root == NULL) {
return NULL;
}
node = root->right;
while (node->left) {
node = node->left;
}
return node;
}
/*
* Name: rb_tree_predecessor
* Description: 找结点的前 继结点
*
*/
static rb_node_pt
rb_tree_predecessor(rb_node_pt root)
{
rb_node_pt node;
if (root == NULL) {
return NULL;
}
node = root->left;
while (node->right) {
node = node->right;
}
return node;
}
/*
* Name: rb_tree_search
* Description: 查找树中指定值的节点
*
*/
static rb_node_pt
rb_tree_search(rb_node_pt root, Item element)
{
rb_node_pt node = root;
while (node != NULL) {
if (item_equal(node->data, element)) {
break;
}
else if (item_cmp(element, node->data)) {
node = node->left;
}
else {
node = node->right;
}
}
return node;
}
/*
* Name: rb_left_rotate
* Description: 对红黑树进行左旋转
*
* px px
* / /
* x y
* / \ --(左旋)--> / \ #
* lx y x ry
* / \ / \
* ly ry lx ly
*
*/
static void
rb_left_rotate(rb_tree_pt tree, rb_node_pt x)
{
rb_node_pt y = x->right;
x->right = y->left;
if (x->right != NULL) {
x->right->parent = x;
}
y->parent = x->parent;
if (x->parent == NULL) {
tree->root = y;
}
else {
if (x->parent->left == x) {
x->parent->left = y;
}
else {
x->parent->right = y;
}
}
y->left = x;
x->parent = y;
}
/*
* Name: rb_right_rotate
* Description: 对红黑树进行右旋转
*
* py py
* / /
* y x
* / \ --(右旋)--> / \ #
* x ry lx y
* / \ / \ #
* lx rx rx ry
*/
static void
rb_right_rotate(rb_tree_pt tree, rb_node_pt y)
{
rb_node_pt x = y->left;
y->left = x->right;
if (y->left != NULL) {
y->left->parent = y;
}
x->parent = y->parent;
if (y->parent == NULL) {
tree->root = x;
}
else {
if (y->parent->left == y) {
y->parent->left = x;
}
else {
y->parent->right = x;
}
}
x->right = y;
y->parent = x;
}
/*
* Name: rb_tree_insert_fixup
* Description: 红黑树插入修正函数
*
*/
static void
rb_tree_insert_fixup(rb_tree_pt tree, rb_node_pt node)
{
rb_node_pt parent, gparent, uncle;
while ((parent = node->parent) && parent->color == RB_RED) {
gparent = parent->parent;
if (parent == gparent->left) {
uncle = gparent->right;
if (uncle && uncle->color == RB_RED) {
/* case 1 父节点和叔叔节点都是红色*/
parent->color = RB_BLACK;
uncle->color = RB_BLACK;
gparent->color = RB_RED;
node = gparent;
}
else {
if (parent->right == node) {
/* case 2 父节点是红色 ，叔叔节点是黑色，且当前节点是右孩子 */
rb_left_rotate(tree, parent);
node = parent;
parent = node->parent;
}
/* case 3 父节点是红色， 叔叔节点是黑色，且当前节点是左孩子 */
parent->color = RB_BLACK;
gparent->color = RB_RED;
rb_right_rotate(tree, gparent);
}
}
else {
uncle = gparent->left;
if (uncle && uncle->color == RB_RED) {
/* case 1 父节点和叔叔节点都是红色*/
parent->color = RB_BLACK;
uncle->color = RB_BLACK;
gparent->color = RB_RED;
node = gparent;
}
else {
if (parent->left == node) {
/* case 2 父节点是红色 ，叔叔节点是黑色，且当前节点是左孩子 */
rb_right_rotate(tree, parent);
node = parent;
parent = node->parent;
}
/* case 3 父节点是红色， 叔叔节点是黑色，且当前节点是右孩子 */
parent->color = RB_BLACK;
gparent->color = RB_RED;
rb_left_rotate(tree, gparent);
}
}
}
tree->root->color = RB_BLACK;
}
int
rb_tree_insert(rb_tree_pt tree, Item element)
{
rb_node_pt node = NULL, parent = NULL, tmp;
if ((node = rb_node_create(element, NULL, NULL, NULL)) == NULL) {
return -1;
}
tmp = tree->root;
while (tmp != NULL) {
parent = tmp;
if (item_cmp(element, tmp->data)) {
tmp = tmp->left;
}
else if (item_cmp(tmp->data, element)) {
tmp = tmp->right;
}
else {
return -1;
}
}
node->parent = parent;
if (parent == NULL) {
tree->root = node;
}
else {
if (item_cmp(element, parent->data)) {
parent->left = node;
}
else {
parent->right = node;
}
}
node->color = RB_RED;
rb_tree_insert_fixup(tree, node);
return 0;
}
static void
rb_tree_delete_fixup(rb_tree_pt tree, rb_node_pt node, rb_node_pt parent)
{
rb_node_pt sibling;
while ((!node || node->color == RB_BLACK) && node != tree->root) {
if (node == parent->left) {
sibling = parent->right;
if (sibling->color == RB_RED) {
/* case 1 兄弟是红色 */
sibling->color = RB_BLACK;
parent->color = RB_RED;
rb_left_rotate(tree, parent);
sibling = parent->right;
}
/* 上面已保证sibling一定为黑色 */
if ((!sibling->left || sibling->left->color == RB_BLACK) && (!sibling->right || sibling->right->color == RB_BLACK)) {
/* case 2 兄弟是黑色，且左孩子和右孩子是黑色 */
sibling->color = RB_RED;
node = parent;
parent = node->parent;
}
else {
if (!sibling->right || sibling->right->color == RB_BLACK) {
/* case 3 兄弟是黑色，且左孩子是红色，右孩子是黑色 */
sibling->color = RB_RED;
sibling->left->color = RB_BLACK;
rb_right_rotate(tree, sibling);
sibling = parent->right;
}
/* 经过case 3 的处理后，确保sibling的右孩子是红色 */
/* case 4 兄弟是黑色，且左孩子是黑色，右孩子是红色 */
sibling->color = parent->color;
sibling->right->color = RB_BLACK;
rb_left_rotate(tree, parent);
node = tree->root;
break;
}
}
else {
sibling = parent->left;
if (sibling->color == RB_RED) {
/* case 1 兄弟是红色 */
sibling->color = RB_BLACK;
parent->color = RB_RED;
rb_right_rotate(tree, parent);
sibling = parent->left;
}
/* 上面已保证sibling一定为黑色 */
if ((!sibling->left || sibling->left->color == RB_BLACK) && (!sibling->right || sibling->right->color == RB_BLACK)) {
/* case 2 兄弟是黑色，且左孩子和右孩子是黑色 */
sibling->color = RB_RED;
node = parent;
parent = node->parent;
}
else {
if (!sibling->left || sibling->left->color == RB_BLACK) {
/* case 3 兄弟是黑色，且右孩子是红色，左孩子是黑色 */
sibling->color = RB_RED;
sibling->right->color = RB_BLACK;
rb_left_rotate(tree, sibling);
sibling = parent->left;
}
/* 经过case 3 的处理后，确保sibling的左孩子是红色 */
/* case 4 兄弟是黑色，且右孩子是黑色，左孩子是红色 */
sibling->color = parent->color;
sibling->left->color = RB_BLACK;
rb_right_rotate(tree, parent);
node = tree->root;
break;
}
}
}
if (node) {
node->color = RB_BLACK;
}
}
static void
rb_transplant(rb_tree_pt tree, rb_node_pt node1, rb_node_pt node2)
{
if (node1->parent == NULL) {
tree->root = node2;
}
else if (node1->parent->left == node1) {
node1->parent->left = node2;
}
else {
node1->parent->right = node2;
}
if (node2) {
node2->parent = node1->parent;
}
}
void
rb_tree_delete(rb_tree_pt tree, Item element)
{
rb_node_pt node = NULL, temp = tree->root, replace, parent, child;
int color;
/* 找到删除节点 */
while (temp) {
if (item_cmp(element, temp->data)) {
temp = temp->left;
}
else if (item_cmp(temp->data, element)) {
temp = temp->right;
}
else {
node = temp;
break;
}
}
if (node == NULL) {
return;
}
parent = node->parent;
color = node->color;
if (node->left == NULL) {
child = node->right;
rb_transplant(tree, node, child);
}
else if (node->right == NULL) {
child = node->left;
rb_transplant(tree, node, child);
}
else {
/* 待删除节点的左右子节点都不为空的情况 */
replace = rb_tree_successor(node);
color = replace->color;
child = replace->right;
if (replace->parent == node) {
parent = replace;
}
else {
parent = replace->parent;
/* 用child节点替换replace节点 */
rb_transplant(tree, replace, child);
/* 设置replace替换node后的子节点 */
replace->right = node->right;
replace->right->parent = replace;
}
/* 用replace节点替换node节点 */
rb_transplant(tree, node, replace);
replace->left = node->left;
replace->left->parent = replace;
replace->color = node->color;
}
if (color == RB_BLACK) {
rb_tree_delete_fixup(tree, child, parent);
}
}
rb_node_pt
rb_tree_find(rb_tree_pt tree, Item element)
{
return rb_tree_search(tree->root, element);
}
void
rb_node_destroy(rb_node_pt node)
{
if (node == NULL) {
return;
}
rb_node_destroy(node->left);
rb_node_destroy(node->right);
free(node);
}
void
rb_tree_destroy(rb_tree_pt tree)
{
rb_node_destroy(tree->root);
}
static void
rb_tree_printnode(rb_node_pt node, int h)
{
int i;
for (i=0; i < h; i++) {
printf(" ");
}
if (node == NULL) {
printf("*\n");
}
else {
printf("%d\n", node->data);
}
}
static void
rb_tree_show(rb_node_pt root, int h)
{
if (root == NULL) {
rb_tree_printnode(root, h);
return;
}
rb_tree_show(root->left, h+1);
rb_tree_printnode(root, h);
rb_tree_show(root->right, h+1);
}
void
rb_tree_print(rb_tree_pt tree)
{
rb_tree_show(tree->root, 0);
}
/* 打印节点计数变量 */
static int node_num = 0;
static void
export_dot(FILE *fp, rb_node_pt root, char *last_label)
{
/* 打印节点 */
char node_name[10] = {0};
sprintf(node_name, "n%d", node_num);
if (root == NULL) {
fprintf(fp, "%s[style=invis];\n", node_name);
}
else if (root->color == RB_RED) {
fprintf(fp, "%s[label=%d, style = filled,color=\"tomato\"];\n", node_name, root->data);
}
else {
fprintf(fp, "%s[label=%d, fontcolor=\"white\", style=filled, color=\"black\"];\n", node_name, root->data);
}
node_num++;
/* 打印边 */
if (last_label != NULL) {
if (root == NULL) {
fprintf(fp, "%s->%s[style=invis];\n", last_label, node_name);
}
else {
fprintf(fp, "%s->%s;\n", last_label, node_name);
}
}
if (root == NULL) {
return;
}
/* 打印子节点 */
if (root->left == NULL && root->right == NULL) {
return;
}
export_dot(fp, root->left, node_name);
export_dot(fp, NULL, node_name);
export_dot(fp, root->right, node_name);
}
void
rb_tree_export_dot(rb_tree_pt tree, char *filename, char *label)
{
FILE *fp;
fp = fopen(filename, "w");
fprintf(fp, "digraph g{\nnode[shape=circle];\nlabel=\"%s\";\nlabeljust=l;\nlabelloc=t;\n", label);
export_dot(fp, tree->root, NULL);
fprintf(fp, "}\n");
fclose(fp);
}
rb_tree.c
/* rb_tree_test.c */
#include <stdlib.h>
#include <stdio.h>
#include "rb_tree.h"
#define LENGTH(a) ( (sizeof(a)) / (sizeof(a[0])) )
int
main(int argc, char *argv[])
{
int a[] = {3,2,1,4,5,6,7,16,15,14,13,12,11,10,8,9};
int i, len=LENGTH(a);
rb_tree_pt tree = rb_tree_create();
printf("== 红黑树中依次添加: \n");
for(i=0; i<len; i++)
{
printf("%d ", a[i]);
rb_tree_insert(tree, a[i]);
}
printf("\n");
printf("== 红黑树生成: \n");
rb_tree_print(tree);
rb_tree_export_dot(tree, "rbtree.dot", "红黑树生成");
rb_tree_delete(tree, 8);
printf("== 红黑树删除元素8后: \n");
rb_tree_print(tree);
rb_tree_export_dot(tree, "rbtree2.dot", "红黑树删除后");
rb_tree_destroy(tree);
return 0;
}
rb_tree_test.c
测试程序的运行结果
== 红黑树中依次添加:
3 2 1 4 5 6 7 16 15 14 13 12 11 10 8 9
== 红黑树生成:
*
1
*
2
*
3
*
4
*
5
*
6
*
7
*
8
*
9
*
10
*
11
*
12
*
13
*
14
*
15
*
16
*
== 红黑树删除元素8后:
*
1
*
2
*
3
*
4
*
5
*
6
*
7
*
9
*
10
*
11
*
12
*
13
*
14
*
15
*
16
*
最后生成dot标记文件，然后使用工具可以生成下图
转载文章请注明出处： http://mingnote.com