学了一下算法导论上的红黑树，这个数据结构基于二叉搜索树，二叉搜索树有一个缺点：如果数据以递增的顺序插入，得到的树深度就是n，进行操作就很不方便。红黑树就是在此基础上完善，自己可以自平衡，使两边始终保持接近，这样时间复杂度就降到O（lgn）。这个数据结构的确很难，插入和删除这两种操作非常复杂，自己按照书上给的伪代码实现了一下，思路是基本理清了，这种太复杂的数据结构想完全记住是不太现实的，能够掌握要点，下次看的时候可以马上回忆起来就可以了。
头文件：
#ifndef _RED_BLACK_TREE_#define _RED_BLACK_TREE_#define RED 82#define BLACK 66typedef struct RBTreeNode{ unsigned int color; int key; struct RBTreeNode *left; struct RBTreeNode *right; struct RBTreeNode *pre;}Node,*RBTree;typedef struct RBRoot{ Node *root;}RBRoot;RBRoot *CreateTree();void InsertTree(RBRoot *tree, int key);void DeleteNode(RBRoot *tree, Node *z);void PrintTree(RBRoot *tree);#endif 函数声明文件：
#include#include #include"rbtree.h"static void LeftRotate(RBRoot *tree, Node *x);static void RightRotate(RBRoot *tree, Node *y);static void RBInsertFixUp(RBRoot *tree, Node *z);static void PrintNode(Node *node,int key, int direction);static void InsertNode(RBRoot *tree, Node *z);static void RBTransplant(RBRoot *tree, Node *u, Node *v);static void RBDeleteFixUp(RBRoot *tree, Node *x);RBRoot *CreateTree(){ RBRoot *tree = (RBRoot *)malloc(sizeof(RBRoot)); tree->root = NULL; return tree;}static void LeftRotate(RBRoot *tree, Node *x){ Node *y = x->right; x->right = y->left; if (y->left != NULL) y->left->pre = x; y->pre = x->pre; if (x->pre == NULL) tree->root = y; else if (x == x->pre->left) x->pre->left = y; else x->pre->right = y; y->left = x; x->pre = y;}static void RightRotate(RBRoot *tree, Node *y){ Node *x = y->left; y->left = x->right; if (x->right != NULL) x->right->pre = y; x->pre = y->pre; if (y->pre == NULL) tree->root = x; else if (y == y->pre->left) y->pre->left = x; else y->pre->right = x; y->pre = x; x->right = y;}static void RBInsertFixUp(RBRoot *tree, Node *z){ while (z->pre!=NULL&&z->pre->pre!=NULL&&z->pre->color == RED)//自己和父亲都是红结点 { if (z->pre == z->pre->pre->left) { Node *y = z->pre->pre->right; if (y!=NULL&&y->color == RED)//叔也为红结点就把父亲和叔叔都变成红色，爷爷变成黑色，这样达到一个z变成爷爷上移的作用，且黑高不变 { z->pre->color = BLACK; y->color = BLACK; z->pre->pre->color = RED; z = z->pre->pre; } else if (z == z->pre->right)//叔为黑且自己为右子树就进行一次左旋转换为第三种情况(叔不存在也是黑) { z = z->pre; LeftRotate(tree, z); } else//将父亲和爷爷的颜色交换并对爷爷进行一次右旋，这样转换为第一种情况 { z->pre->color = BLACK; z->pre->pre->color = RED; RightRotate(tree, z->pre->pre); } } else//父亲为右子树的情况只要把上面的情况中所以Right和Left互换就行 { Node *y = z->pre->pre->left; if (y!=NULL&&y->color == RED) { z->pre->color = BLACK; y->color = BLACK; z->pre->pre->color = RED; z = z->pre->pre; } else if (z == z->pre->left) { z = z->pre; RightRotate(tree, z); } else { z->pre->color = BLACK; z->pre->pre->color = RED; LeftRotate(tree, z->pre->pre); } } } tree->root->color = BLACK;//将根结点设为黑色}static void InsertNode(RBRoot *tree, Node *z){ Node *y = NULL; Node *x = tree->root; while (x != NULL)//寻找合适的位置 { y = x; if (z->key < x->key) x = x->left; else x = x->right; } z->pre = y; if (y == NULL) tree->root = z; else if (z->key < y->key) y->left = z; else y->right = z; z->left = NULL; z->right = NULL; z->color = RED; RBInsertFixUp(tree, z);}static void PrintNode(Node *node,int key, int direction){ if (node != NULL) { if(direction==0) printf("%2d(B) is root\n", node->key); else printf("%2d(%c) is %2d's %6s child\n", node->key, node->color, key, direction == 1 ? "right" : "left"); PrintNode(node->left, node->key, -1); PrintNode(node->right, node->key, 1); }}void PrintTree(RBRoot *tree){ if (tree!=NULL&&tree->root != NULL) PrintNode(tree->root, tree->root->key, 0);}void InsertTree(RBRoot *tree, int key){ Node* temp=(Node*)malloc(sizeof(Node)); temp->key = key; temp->left = NULL; temp->right = NULL; temp->color = BLACK; InsertNode(tree, temp);}void RBTransplant(RBRoot *tree, Node *u, Node *v)//用v来取代u{ if (u->pre == NULL) tree->root = v; else if (u == u->pre->left) u->pre->left = v; else u->pre->right = v; v->pre = u->pre;}void RBDeleteFixUp(RBRoot *tree, Node *x){ while (x != tree->root&&x->color == BLACK) { if (x == x->pre->left) { Node *w = x->pre->right;//x为y的右子树，w为x的兄弟 if (w->color == RED)//情况1：兄弟为红色，左旋一次转换为情况2 { w->color == BLACK; x->pre->color = RED; LeftRotate(tree, x->pre); w = x->pre->right; } else { if (w->left->color == BLACK&&w->right->color == BLACK)//情况2：兄弟的两个孩子都是黑色，将兄弟削去一层黑色，将x上移，转换为情况1234 { w->color = RED; x = x->pre; } else if (w->right->color == BLACK)//情况3：兄弟的左孩子红右孩子黑，右旋一次转换为情况4 { w->left->color = BLACK; w->color = RED; RightRotate(tree, w); w = x->pre->right; } else//情况4：兄弟的孩子都是红色，此时坐旋使原x的路径增加一个黑色，这种情况出现说明完成红黑平衡 { w->color = x->pre->color; x->pre->color = BLACK; w->right->color = BLACK; LeftRotate(tree, x->pre); x = tree->root; } } } else { Node *w = x->pre->left; if (w->color == RED) { w->color == BLACK; x->pre->color = RED; RightRotate(tree, x->pre); w = x->pre->left; } else { if (w->left->color == BLACK&&w->right->color == BLACK)//情况2：兄弟的两个孩子都是黑色，将兄弟削去一层黑色，将x上移，转换为情况1234 { w->color = RED; x = x->pre; } else if (w->left->color == BLACK)//情况3：兄弟的左孩子红右孩子黑，右旋一次转换为情况4 { w->right->color = BLACK; w->color = RED; LeftRotate(tree, w); w = x->pre->left; } else//情况4：兄弟的孩子都是红色，此时坐旋使原x的路径增加一个黑色，这种情况出现说明完成红黑平衡 { w->color = x->pre->color; x->pre->color = BLACK; w->left->color = BLACK; RightRotate(tree, x->pre); x = tree->root; } } } } x->color = BLACK;}void DeleteNode(RBRoot *tree,Node *z){ Node *y,*x; y = z; unsigned int origin_color = y->color; if (z->left == NULL) { x = z->right; RBTransplant(tree, z, z->right); } else if (z->right == NULL) { x = z->left; RBTransplant(tree, z, z->left); } else { Node *temp = z->right; while (temp->left!= NULL) temp = temp->left; y = temp; origin_color = y->color; x = y->right; if (y->pre == z) x->pre = y; else { RBTransplant(tree, y, y->right); y->right = z->right; y->right->pre = y; } RBTransplant(tree, z, y); y->left = z->left; y->left->pre = y; y->color = z->color; } if (origin_color == BLACK) RBDeleteFixUp(tree, x);}
实现文件：
#include#include #include"rbtree.h"int main(){ int test[] = { 10, 40,30,60,90,70,20,50,80}; RBRoot* tree = CreateTree(); for (int i = 0; i < sizeof(test)/sizeof(int); i++) InsertTree(tree, test[i]); PrintTree(tree); DeleteNode(tree,tree->root); PrintTree(tree); return 0;}