本文共 5777 字，大约阅读时间需要 19 分钟。
红黑树可以实现自平衡，主要依靠于它的旋转和变色的特性
//红黑树节点typedef struct RBTreeNode{ unsigned char color; Type key; struct RBTreeNode* left; struct RBTreeNode* right; struct RBTreeNode* parent;}Node, *RBTree;//红黑树的根typedef struct rb_root{ Node* node;}RBRoot; 左旋：以某个节点作为旋转节点，其右子节点变为旋转节点的父节点，右子节点的左子节点变为旋转节点的右子节点，旋转节点的左子节点保持不变。
static void rbtree_left_rotate(RBRoot* root, Node* x){ //设置x的右孩子为y Node* y = x->right; //将y的左孩子设置为x的右孩子 //如果y的左孩子非空，将x设为y的左孩子的父亲 x->right = y->left; if (y->left != NULL) { y->left->parent = x; } //将x的父亲设为y的父亲 y->parent = x->parent; //if语句成立说明x为根节点 if (x->parent == NULL) //修改红黑树的根节点 { root->node = y; //如果“x的父亲”是空节点，则将y设为根节点 } else { //如果x是它父节点的左孩子，则将y设为“x的父节点” if (x->parent->left == x) { x->parent->left = y; } //如果x是它父节点的右孩子，则将y设为“x的父节点” else { x->parent->right = y; } } //将x设为y的左孩子 y->left = x; //将x的父节点设为y x->parent = y;} 右旋：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。
static void rbtree_right_rotate(RBRoot* root, Node* y){ //设置x是当前节点的左孩子 Node* x = y->left; //将x的右孩子设为y的左孩子 //如果x的右孩子不为空，将y设为x的右孩子的父亲 y->left = x->right; if (x->right != NULL) { x->right->parent = y; } //将y的父亲设置为x的父亲 x->parent = y->parent; //if语句成立说明y为根节点 if (y->parent == NULL) { root->node = x; //如果“y的父亲”是空节点，则将x设为根节点 } else { //如果y是它父节点的右孩子，则将x设为“y的父节点” if (y->parent->right == y) { y->parent->right = x; } //如果y是它父节点的左孩子，则将x设为“y的父节点” else { y->parent->left = x; } } //将y设为x的右孩子 x->right = y; //将y的父节点设为x y->parent = x;} 红黑树的插入操作
情况1：红黑树为空树 直接把插入节点作为根节点，把颜色涂成黑色即可。void insert_case1(node *n){ if(n->parent == NULL) n->color = BLACK; else insert_case2 (n); } 情况2：插入节点的父节点为黑色节点
因为插入节点是红色的，当插入节点的父节点为黑色节点时，不会对红黑树的平衡造成影响，直接插入即可。void insert_case2(node *n){ if(n->parent->color == BLACK) return; else insert_case3 (n);} 情况3：插入节点的父节点为红色节点。如果插入的父结点为红结点，那么该父结点不可能为根结点，所以插入结点总是存在祖父结点。
情况3_1：叔叔节点存在且为红色
此时的处理方法是将父亲节点和叔叔节点都涂成黑色，将祖父节点涂成红色，再将祖父节点设置成当前插入的节点，继续从底部向上进行递归或循环判断。
void insert_case3_1(node *n){ if(uncle(n) != NULL && uncle (n)->color == RED) { n->parent->color = BLACK; uncle (n)->color = BLACK; grandparent (n)->color = RED; insert_case1(grandparent(n));}else insert_case3_2and3_3(n);} 情况3_2：叔叔节点不存在或为黑色节点，并且插入节点的父亲节点是祖父节点的左子节点
情况3_2_1：插入节点是父节点的左子节点
处理方法是将父亲节点设为黑色，祖父节点设为红色，并对祖父节点进行右旋情况3_3：叔叔节点不存在或为黑色节点，并且插入节点的父亲节点是祖父节点的右子节点
情况3_3_1：插入节点是父节点的右子节点 处理方法是将父亲节点设为黑色，祖父节点设为红色，并对祖父节点进行左旋
void insert_case3_2_1and3_3_1(node *n){ n->parent->color = BLACK; grandparent (n)->color = RED; if(n->parent == grandparent(n)->left && n == n->parent->left) { rotate_right(grandparent(n)); //情况3_2_1 } else if(n->parent == grandparent (n)->right && n == n->parent->right) { rotate_left(grandparent(n)); //情况3_3_1 }} 情况3_2：叔叔节点不存在或为黑色节点，并且插入节点的父亲节点是祖父节点的左子节点
情况3_2_2：插入节点是父节点的右子节点
处理方法是对父节点进行左旋，然后情况就变成了3-2-1的情况情况3_3：叔叔节点不存在或为黑色节点，并且插入节点的父亲节点是祖父节点的右子节点
情况3_3_2：插入节点是父节点的左子节点 处理方法是对父节点进行右旋，然后情况就变成了3_3_1的情况
void insert_case3_2_2and3_3_2(node *n){ if(n->parent == grandparent(n)->left && n == n->parent->right) { rotate_left(n->parent); //情况3_2_2 n = n->left; } else if(n->parent == grandparent(n)->right && n == n->parent->left) { rotate_right(n->parent); //情况3_3_2 n = n->right; }} 完整代码如下：
#define rb_parent(r) ((r)->parent)#define rb_color(r) ((r)->color)#define rb_is_red(r) ((r)->color == RED)#define rb_is_black(r) ((r)->color == BLACK)#define rb_set_black(r) do {(r)->color = BLACK;} while(0)#define rb_set_red(r) do {(r)->color = RED;} while(0)#define rb_set_parent(r, p) do {(r)->parent = (p);}while(0)#define rb_set_color(r, c) do {(r)->color = (c);}while(0) static void rbtree_insert(RBRoot* root, Node* node){ //添加节点：将节点node插入红黑树中，root为红黑树的根，node为插入的节点 Node* y = NULL; Node* x = root->node; //先将根节点给x //1、将红黑树当做一颗二叉查找树，将节点添加到二叉查找树中 while (x != NULL) { y = x; //y为所需插入节点的父节点 if (node->key < x->key) { x = x->left; } else { x = x->right; } } rb_parent(node) = y; //找到父节点并把要插入节点的父节点的指针修改 //修改父节点的子节点指针 if (y != NULL) { if (node->key < y->key) { y->left = node; //情况2：node包含的值 < y所包含的值 } else { y->right = node; //情况3：node包含的值 >= y所包含的值 } } else { root->node = node; //情况1：若y是空节点，则将node设为根 } //2、设置节点的颜色为红色 node->color = RED; //3、将它重新修正为一颗rb树 rbtree_insert_fixup(root, node);} static void rbtree_insert_fixup(RBRoot* root, Node* node){ Node* parent, * gparent; //若父节点存在，且父节点的颜色是红色 while ((parent = rb_parent(node)) && rb_is_red(parent)) { gparent = rb_parent(parent); //若父节点是祖父节点的左孩子 if (parent == gparent->left) { //Case1条件：叔叔节点是红色 { Node* uncle = gparent->right; if (uncle && rb_is_red(uncle)) //若没有节点进入该分支，如何构造 { rb_set_black(uncle); rb_set_black(parent); rb_set_red(gparent); node = gparent; continue; } } //Case2条件：叔叔是黑色，且当前节点是右孩子，叔叔不存在，也认为是黑色 if (parent->right == node) //插入80节点时，先左旋，后右旋 { Node* tmp; rbtree_left_rotate(root, parent); tmp = parent; parent = node; node = tmp; } //Case3条件：叔叔是黑色，且当前节点是左孩子 rb_set_black(parent); rb_set_red(gparent); rbtree_right_rotate(root, gparent); } else { //若父亲节点是祖父节点的右孩子 { //Case1条件：叔叔节点是红色 Node* uncle = gparent->left; if (uncle && rb_is_red(uncle)) { rb_set_black(uncle); rb_set_black(parent); rb_set_red(gparent); node = gparent; continue; //继续进行调整 } } //Case2条件：叔叔是黑色或空缺，且当前节点是左孩子，插入30时，先右旋，后左旋 if(parent->left == node) { Node* tmp; rbtree_right_rotate(root, parent); tmp = parent; parent = node; node = tmp; } //Case3条件：叔叔是黑色或空缺，且当前节点是右孩子 rb_set_black(parent); //旋转前设置好颜色 rb_set_red(gparent); rbtree_left_rotate(root, gparent); } } //将根节点设为黑色 rb_set_black(root->node);} 转载地址：http://sxxmb.baihongyu.com/