红黑树是指每个节点都带有颜色属性的二叉查找树，其中颜色为红色或黑色。

除了二叉查找树的一般要求外，对于红黑树还有如下的额外的特性：

1.节点是红色或黑色

2.根节点是黑色。

3.所有叶子节点都是黑色。（“哨兵”，返回NULL的节点）

4.每个红色节点的两个子节点都是黑色（每个叶子节点到根节点的所有路径上不能有两个连续的红色节点）。

5.从任一节点到其每个叶子节点的所有简单路径都包含相同数目的黑色节点。

复杂度o(logN)

首先定义几个结构

typedef struct rbtree_node_s rbtree_node_t;

/*struct of node*/

struct rbtree_node_s {

int key;

rbtree_node_t *left;

rbtree_node_t *right;

rbtree_node_t *parent;

char color;

int num;

};

typedef struct rbtree_s rbtree_t;

typedef void (*rbtree_insert_pt) (rbtree_node_t *root,rbtree_node_t *node, rbtree_node_t *sentinel);

struct rbtree_s {

rbtree_node_t *root;

rbtree_node_t *sentinel; /*哨兵*/

rbtree_insert_pt insert; /*提供一个函数指针给插入数据使用*、

};

红黑树的左旋以及右旋（通过旋转来达到平衡）

左旋

右旋：

宏定义几个常用的函数

插入操作

1. 插入数据（插入节点时候，函数指针insert进行调用）

2. 插入节点

接上面的else

分析： node->parent(父） node->parent->parent(爷） 个人理解，需结合代码看

只判断node是不是插入红色节点下面时候且node不为根节点：

1.如果node的父是node的爷的左儿子

一.如果node的爷的右儿子存在且为红色（直接设置node,node爷为红色,node爷2个儿子为黑色）

二.如果node是node父的右儿子，node->parent指向node，并进行左旋操作（操作1）

将node（此时node = node->parent）父设置黑色，node爷设置红色，node爷进行右旋 (操作2)

(操作结果就是）

三. 如果node是node父的左儿子，直接进行操作2

2.如果node的父是node的爷的右儿子

一.如果node的爷的左儿子存在且为红色（直接设置node,node爷为红色,node爷2个儿子为黑色）

二.如果node是node父的左儿子，node->parent指向node，并进行右旋操作（操作1）

将node（此时node = node->parent）父设置黑色，node爷设置红色，node爷进行左旋 (操作2)

(操作结果就是）

三. 如果node的父是node爷的左儿子

直接进行操作2

删除操作

求最小的节点（按key值） delete操作时候会用到

static rbtree_node_t*

rbtree_min(rbtree_node_t *node, rbtree_node_t *sentinel)

{

while (node->left != sentinel) {

node = node->left;

}

return node;

}