做游戏都需要什么网站/推广网站都有哪些
接下来介绍红黑树的插入操作，介绍插入之前，我们先来了解一下红黑树的性质。
1、每个节点不是红色就是黑色
2、跟节点为黑色。
3、如果节点为红，子节点必须为黑。
4、任意节点至树尾端的任何路径，黑节点必须相同。
规则4主要是保证树的平衡性，不过它的要求不是很严。主要是为了减少调整操作。根据规则4，我们可以判断出新节点都是红节点。（如果新节点是黑节点，那么每次插入都要进行调整）
由于要经常使用某个节点的父亲。所以这里添加了一个指向父亲的指针。所以我们先看一下红黑树的结构组成。
typedef int value_type; typedef bool color_type; const color_type red = true; const color_type black = false;typedef struct node {value_type value;color_type color;struct node * parent;struct node * left;struct node * right; } Node;typedef struct Tree {Node * root; } Tree;
Node节点，value，关键字信息。color，颜色。parent，left，right，父亲，左孩子，右孩子。
Tree只有一个根节点。
插入操作，与二叉树的插入是一样的。
首先是找到插入位置。
//根节点返回NULL,找到返回当前节点,否则返回x的父亲(x是节点所在的位置) static Node * search_node(const int key, Tree * tree) {Node * x, * y;x = tree->root;y = nil;while ( x != nil ){y = x;if ( key < x->value )x = x->left;else if ( key > x->value )x = x->right;elsebreak;}return y; }
nil是一个空节点，所有应该为空的指针都指向它。这个节点是黑色的，parent，left，right都为NULL，没有初始化value。（不是一定要有nil节点）
其次将元素插入
void rb_insert(const value_type value, Tree * tree) {Node * new_node;//新节点Node * x = search_node(value, tree);//插入点if ( x == nil ){tree->root = make_new(value);tree->root->color = black;//根节点为黑色 }else{if ( x->value == value )//关键字不可重复return;new_node = make_new(value);if ( value < x->value )//将新节点插入二叉树中x->left = new_node;elsex->right = new_node;new_node->parent = x;//设置新节点的父亲if ( x->color == red )//如果新节点的父亲为红色,调整 insert_fixup(new_node, tree);} }
新节点一定是红色的，所以不会违反规则4，但有可能违反规则3。也就是说如果插入节点的父亲是红色的，那么违反了规则3。
我们需要进行调整。
调整时会遇到三种情况，根据不同的情况进行不同的调整。
调整是一个循环过程，当x为根节点或者x是黑色时结束。（这个操作次数并不会很多）
三种情况在代码中看注释。
static void insert_fixup(Node * x, Tree * tree) {Node * y;//y是x的伯父节点while ( x != tree->root && x->parent->color == red ){if ( x->parent == x->parent->parent->left )//父亲是祖父左孩子 {y = x->parent->parent->right;//case 1: 伯父是红色//处理办法// 1.将父亲,伯父变成黑色// 2.将祖父变成红色// 3.将祖父设为x，向上检查if ( y->color == red ){x->parent->color = black;y->color = black;x->parent->parent->color = red;x = x->parent->parent;}else{//case 2: x是父亲的右孩子//处理办法:// 1.将x设为x的父亲// 2.以x为旋转点,左旋//经过上述操作,转换成case 3if ( x == x->parent->right ){x = x->parent;left_rotate(x, tree);}//case 3: x是父亲的左孩子//处理办法:// 1.将x的父亲设为黑色// 2.将x的祖父设为红色// 3.以x的祖父为旋转点,右旋x->parent->color = black;x->parent->parent->color = red;right_rotate(x->parent->parent, tree);}}else//与上述处理相同,只是将left与right互换 {y = x->parent->parent->left;if ( y->color == red ){x->parent->color = black;y->color = black;x->parent->parent->color = red;x = x->parent->parent;}else{if ( x == x->parent->left ){x = x->parent;right_rotate(x, tree);}x->parent->color = black;x->parent->parent->color = red;left_rotate(x->parent->parent, tree);}}}//while end tree->root->color = black; }
这样插入操作就完成了。
这是一棵红黑树，圆圈里的代表黑色节点，没有圆圈的代表红色。大家可以利用这棵树来调代码。建议在调整时，用printf把case 1到3标记一下，挨个试验。
这颗树的插入顺序是10，7，8，15，5，6，11，13，12。