#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// #define RED     0
// #define BLACK   1
typedef enum color_t{
    RED,
    BLACK
} color_t;

typedef int key_t;
typedef int data_t;

typedef struct rb_node_t
{
    color_t color;
    struct rb_node_t *parent;
    struct rb_node_t *left;
    struct rb_node_t *right;
    key_t key;
    data_t data;
} rb_node_t;

//一、左旋代码分析
/*-----------------------------------------------------------
|   node           right
|   / \    ==>     / \
|   a  right     node  y
|       / \       / \    
|       b  y     a   b    //左旋
-----------------------------------------------------------*/
static rb_node_t* rb_rotate_left(rb_node_t* node, rb_node_t* root);
 
 
//二、右旋
/*-----------------------------------------------------------
|       node            left
|       / \             / \
|    left  y   ==>    a    node
|   / \                    / \
|  a   b                  b   y  //右旋与左旋差不多，分析略过
-----------------------------------------------------------*/
static rb_node_t* rb_rotate_right(rb_node_t* node, rb_node_t* root);
 
 
//三、红黑树查找结点
//----------------------------------------------------
//rb_search_auxiliary：查找
//rb_node_t* rb_search：返回找到的结点
//----------------------------------------------------
static rb_node_t* rb_search_auxiliary(key_t key, rb_node_t* root, rb_node_t** save);
 
//返回上述rb_search_auxiliary查找结果
rb_node_t* rb_search(key_t key, rb_node_t* root);

rb_node_t *rb_new_node(key_t key, data_t data);

static rb_node_t* rb_insert_rebalance(rb_node_t *node, rb_node_t *root);

//四、红黑树的插入
//---------------------------------------------------------
//红黑树的插入结点
rb_node_t* rb_insert(key_t key, data_t data, rb_node_t* root);
 
 
//五、红黑树的3种插入情况
//接下来，咱们重点分析针对红黑树插入的3种情况，而进行的修复工作。
//--------------------------------------------------------------
//红黑树修复插入的3种情况
//为了在下面的注释中表示方便，也为了让下述代码与我的倆篇文章相对应，
//用z表示当前结点，p[z]表示父母、p[p[z]]表示祖父、y表示叔叔。
//--------------------------------------------------------------
static rb_node_t* rb_insert_rebalance(rb_node_t *node, rb_node_t *root);
 
 static rb_node_t* rb_erase_rebalance(rb_node_t *node, rb_node_t *parent, rb_node_t *root);

 
//六、红黑树的删除
//------------------------------------------------------------
//红黑树的删除结点
rb_node_t* rb_erase(key_t key, rb_node_t *root);
 
 
//七、红黑树的4种删除情况
//----------------------------------------------------------------
//红黑树修复删除的4种情况
//为了表示下述注释的方便，也为了让下述代码与我的倆篇文章相对应，
//x表示要删除的结点，*other、w表示兄弟结点，
//----------------------------------------------------------------
static rb_node_t* rb_erase_rebalance(rb_node_t *node, rb_node_t *parent, rb_node_t *root);