https://blog.csdn.net/very_2/article/details/5722682
二叉树可视化--Graphviz
https://blog.csdn.net/hackooo/article/details/10564049
/*==================================
* Copyright (C) 2016 All rights reserved.
*
* 文件名称：rbt.c
* 描 述：红黑树实现
*
================================================================*/
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
#define RB_RED 0
#define RB_BLACK 1
typedef struct rb_node
{
struct rb_node* left;
struct rb_node* right;
struct rb_node* parent;
uint32_t color:1;
uint32_t data:31;
} rb_node;
typedef struct rb_tree
{
rb_node* root;
} rb_tree;
static inline void rb_init(rb_tree* tree)
{
tree->root = NULL;
}
static inline void rb_init_node(rb_node* node)
{
node->color = RB_RED;
node->parent = node->left = node->right = NULL;
}
static inline void rb_draw_begin(FILE* fp)
{
fprintf(fp, "digraph G{\n");
}
static inline void rb_draw_end(FILE* fp)
{
fprintf(fp, "}\n");
}
#define rb_draw_debug(node, tree) __rb_draw_debug(node, tree, __LINE__)
void __rb_draw_debug(rb_node* node, rb_tree* tree, int line);
void rb_draw_tree(FILE* fp, rb_node* node);
void rb_draw(rb_node* node, const char* filename);
void rb_insert(rb_tree* tree, rb_node* node);
void rb_rotate_right(rb_node* node)
{
rb_node* p = node->parent;
rb_node* l = node->left;
rb_node* lr = l->right;
l->right = node;
node->parent = l;
node->left = lr;
if(lr) lr->parent = node;
l->parent = p;
if(p)
{
if(p->left == node) p->left = l;
else p->right = l;
}
}
void rb_rotate_left(rb_node* node)
{
rb_node* p = node->parent;
rb_node* r = node->right;
rb_node* rl = r->left;
r->left = node;
node->parent = r;
node->right = rl;
if(rl) rl->parent = node;
r->parent = p;
if(p)
{
if(p->left == node) p->left = r;
else p->right = r;
}
}
void rb_insert_adjust(rb_tree* tree, rb_node* node)
{
if(node->parent == NULL)
{
node->color = RB_BLACK;
tree->root = node;
return;
}
if(node->color == RB_BLACK || node->parent->color == RB_BLACK)
return;
rb_node* uncle = NULL;
rb_node* parent = node->parent;
rb_node* grand = parent->parent;
if(grand->left == parent)
uncle = grand->right;
else
uncle = grand->left;
if(uncle && uncle->color == RB_RED)
{
uncle->color = RB_BLACK;
parent->color = RB_BLACK;
grand->color = RB_RED;
rb_insert_adjust(tree, grand);
return;
}
if(grand->left == parent && parent->left == node)
{
rb_rotate_right(grand);
grand->color = RB_RED;
parent->color = RB_BLACK;
rb_insert_adjust(tree, parent);
}
else if(grand->right == parent && parent->right == node)
{
rb_rotate_left(grand);
grand->color = RB_RED;
parent->color = RB_BLACK;
rb_insert_adjust(tree, parent);
}
else if(grand->left == parent && parent->right == node)
{
rb_rotate_left(parent);
rb_insert_adjust(tree, parent);
}
else if(grand->right == parent && parent->left == node)
{
rb_rotate_right(parent);
rb_insert_adjust(tree, parent);
}
}
void rb_insert(rb_tree *tree, rb_node *node)
{
rb_init_node(node);
if(tree->root == NULL)
{
tree->root = node;
node->color = RB_BLACK;
return;
}
rb_node* parent = tree->root;
while(1)
{
if(node->data < parent->data)
{
// left
if(parent->left)
{
parent = parent->left;
}
else
{
parent->left = node;
node->parent = parent;
break;
}
}
else
{
if(parent->right)
{
parent = parent->right;
}
else
{
parent->right = node;
node->parent = parent;
break;
}
}
}
rb_insert_adjust(tree, node);
}
void rb_draw_tree(FILE* fp, rb_node* node)
{
if(node == NULL)
return;
if(node->color == RB_BLACK)
fprintf(fp, "node[shape=record,style=filled,color=black,fontcolor=white];\n");
else
fprintf(fp, "node[shape=record,style=filled,color=red,fontcolor=white];\n");
fprintf(fp, "%d[label=\"<f0> | <f1> %d | <f2> \"];\n", node->data, node->data);
rb_node* parent = node->parent;
if(parent)
{
if(parent->left == node)
{
fprintf(fp, "%d:f0:sw->%d:f1;\n", parent->data, node->data);
}
else
{
fprintf(fp, "%d:f2:se->%d:f1;\n", parent->data, node->data);
}
}
rb_draw_tree(fp, node->left);
rb_draw_tree(fp, node->right);
}
void __rb_draw_debug(rb_node* node, rb_tree* tree, int line)
{
static int v = 0;
char buf[256];
sprintf(buf, "%d_%d_%d.dot",v++, node->data, line);
// rb_draw(tree->root, buf);
}
void rb_draw(rb_node* root, const char* filename)
{
FILE* fp = fopen(filename, "w");
rb_draw_begin(fp);
rb_draw_tree(fp, root);
rb_draw_end(fp);
fclose(fp);
char cmd[1024];
sprintf(cmd, "dot %s -Tpng -o %s.png", filename, filename);
//"dot example1.dot –Tpng –o example1.png"
popen(cmd, "r");
}
/* 删除节点：
* 删除节点时，首先需要将被删除的节点替换到底层
* 替换到底层之后，被删除的节点，要么只有一个儿子，要么没有儿子，不可能存在两个儿子的情况
* 1. 没有儿子
* 1.1 该节点是红色节点：直接删除，太开心了
* 1.2 该节点是黑色节点：太闹心了，见下面吧
* 2. 有一个儿子
* 这个简单，这个儿子一定是红色的，交换一下删除就是了
*
* 考虑这个情况：被删除的节点是黑色的，而且没有儿子
* 这种情况下，将该节点直接删除，然后以它原来的父亲节点为“参考节点”
* 这种情况下，删除叶子节点破坏了红黑树的平衡性，做法的目的是，在这个方向上给它补充一个黑色节点
*
* 理论：当以参考节点的父亲节点为根节点的子树，如果可以再次平衡，并且补充了被删除的黑色节点之后，整个树还是平衡的
* 1. 红色的兄弟
* 在这种情况下，父亲一定是黑色的，这种情况很简单，以父亲做一次旋转（左还是右，则看兄弟位置），然后将兄弟变成黑色，父亲变成红色，删除立马变得简单
*
* 2. 黑色的兄弟
* 2.1 红色的父亲，两个黑色的侄子
* 2.2 黑色的父亲，两个黑色的侄子
* 2.3 如果对面是红色侄子（位置是左边，红侄子在右边）
* 2.4 如果红色侄子和参考节点是同向（都是左边或者都是右边）
*
* */
void rb_erase(rb_tree* tree, int value)
{
rb_node* node = tree->root;
while (node)
{
if(node->data == value)
{
rb_erase_node(tree, node);
return;
}
// find left or right
if(value < node->data)
node = node->left;
else
node = node->right;
}
return NULL;
}
rb_node* rb_remove_node(rb_tree* tree, rb_node* del)
{
if(tree->root==del)
{
free(tree->root);
tree->root = NULL;
return NULL;
}
rb_node* parent = del->parent;
parent->data = del->data;
parent->left = parent->right = NULL;
free(del);
return parent;
}
void rb_erase_adjust(rb_tree* tree, rb_node* node)
{
rb_node* parent = node->parent;
if(parent == NULL)
{
node->color = RB_BLACK;
return;
}
// 把兄弟和两个侄子节点找出来，注意，此时兄弟一定不会为空，侄子可能为空
rb_node* brother = parent->left ^ parent->right ^ node;
rb_node* bl = brother->left;
rb_node* br = brother->right;
// 红色的兄弟，此时做旋转，注意旋转之后，根节点可能指错了
if(brother->color == RB_RED)
{
// 根据兄弟节点的方向，来确认旋转方向
if(parent->left == brother)
{
rb_rotate_right(parent);
}
else
{
rb_rotate_left(parent);
}
// 重新寻找根节点，这里代码有点问题，效率低了，应该有更好的方法
while(parent->parent)
{
parent = parent->parent;
}
tree->root = parent;
return;
}
// 如果兄弟是黑的，父亲是红的，两个侄子也是黑的
// 这种情况最简单，直接将父亲节点改成黑的，兄弟改成红的
if(parent->color == RB_RED
&& (bl == NULL || bl->color == RB_BLACK) && (br == NULL || br->color == RB_BLACK))
{
brother->color = RB_RED;
parent->color = RB_BLACK;
return;
}
// 如果兄弟是黑的，父亲也是黑的，两个侄子也是黑的
// 这种情况node本身什么颜色并不清楚，但是知道父亲在node这边少了个黑节点
// 这种情况下做法是删除该子树一个黑节点，然后递归的整理
if(parent->color == RB_BLACK
&& (bl == NULL || bl->color == RB_BLACK) && (br == NULL || br->color == RB_BLACK))
{
brother->color = RB_RED;
rb_erase_adjust(tree, parent);
return;
}
// 有一个是红色的侄子，那么兄弟显然是黑色的，父亲不知道啥颜色，node也不知道啥颜色
// 这个情况下，分四种情况
if((bl && bl->color == RB_RED) || (br && br->color == RB_RED))
{
}
}
void rb_erase_node(rb_tree* tree, rb_node* node)
{
// 寻找删除位置，先替换删除位置，为该子树的右子树的最左边节点，或者左子树的最右边节点
//
// 假设我们使用左子树的最右边节点
rb_node* del = node->left;
if(del)
{
while(del->right)
{
del = del->right;
}
// 本来要删除node，但是其实把node的值，替换成del的data，再删除del
// 其实效果是一样的，保证删除的是叶子节点，对于简化很有作用
node->data = del->data;
}
else
{
del = node;
}
// 有一个儿子，这个儿子肯定是红色的，所以再替换一次
if(del->left || del->right)
{
del = del->left + del->right;
del->parent->data = del->data;
rb_remove_node(tree, del);
return;
}
// 没有儿子，并且被删除的节点是红色的，直接删除就可以了
if(del->color == RB_RED)
{
rb_remove_node(tree, del);
return;
}
// 没有儿子，并且被删除的节点是黑色的
node = rb_remove_node(tree, del);
if(node == NULL)
return;
rb_remove_adjust(tree, node);
}
int main()
{
int i;
#if 1
srand(time(NULL));
int data[10];
for(i=0; i<sizeof(data)/sizeof(*data); ++i)
{
data[i] = rand()%100;
printf("%d, ", data[i]);
}
printf("\n");
#else
int data[] = {87, 88, 48, 36, 81, 83, 82, 53, 16, 99};
#endif
rb_tree tree;
tree.root = NULL;
char filename[256];
for(i=0; i<sizeof(data)/sizeof(*data); ++i)
{
rb_node* node = malloc(sizeof(*node));
node->data = data[i];
rb_insert(&tree, node);
sprintf(filename, "%d.dot", i);
rb_draw(tree.root, filename);
}
return 0;
}
