红黑树:
k v 方式
用在哪里：
1.hash
强查找的过程：
1.rbtree
2.hash
3.b/b+ tree
4.链表
红黑树：
1.每个结点是红的或者是黑的
2.根结点是黑的
3.每个叶子结点是黑的
4.如果一个结点是红的，则它的两个儿子是黑的
5.对每个节点，从该节点到其子孙结点的所有路径上的包含路径上的黑结点相同
红黑树在插入任何一个结点之前，就是一颗红黑树
左旋：
右旋：
插入：
1.先找到合适的位置
2.先插入节点默认为红色，后面再进行调整
插入调整：
// 定义键类型的别名
typedef int KEY_TYPE;// 定义红色和黑色的宏
#define RED 0
#define BLACK 1// 定义红黑树节点结构的宏
#define RBTREE_ENTRY(name, type) \struct name \{ \struct type *left; \struct type *right; \\struct type *parent; \\unsigned char color; \}// 定义红黑树节点结构
typedef struct _rbtree_node
{KEY_TYPE key; // 节点键值void *value; // 节点关联的值#if 1struct rbtree_node *left; // 左子节点指针struct rbtree_node *right; // 右子节点指针struct rbtree_node *parent; // 父节点指针unsigned char color; // 节点颜色
#elseRBTREE_ENTRY(, rbtree_node) // 使用宏定义节点结构node;
#endif} rbtree_node;// 定义红黑树结构
typedef struct _rbtree
{rbtree_node *root; // 根节点指针rbtree_node *nil; // 默认黑色空节点
} rbtree;// 左旋操作
void rbtree_left_rotate(rbtree *tree, rbtree_node *x)
{// x的右子节点rbtree_node *y = x->right;// 1. 把y的左子节点变成x的右子节点x->right = y->left;if (y->left != tree->nil)y->left->parent = x;// 2. 把x变成y的左子节点y->parent = x->parent;if (x->parent == tree->nil)tree->root = y;else if (x == x->parent->left)x->parent->left = y;elsex->parent->right = y;// 3. 把x变成y的左子节点y->left = x;x->parent = y;
}// 右旋操作
void rbtree_right_rotate(rbtree *tree, rbtree_node *x)
{// x的左子节点rbtree_node *y = x->left;// 1. 把x的左子节点变成y的右子节点y->left = x->right;if (x->right != tree->nil)x->right->parent = y;// 2. 把y变成x的右子节点x->parent = y->parent;if (y->parent == tree->nil)tree->root = x;else if (y == y->parent->left)y->parent->left = x;elsey->parent->right = x;// 3. 把y变成x的左子节点x->right = y;y->parent = x;
}// 插入后修复红黑树性质
void rbtree_insert_fixup(rbtree *tree, rbtree_node *z)
{// 当z的父节点为红色时，需要修复红黑树性质while (z->parent->color == RED){// 判断父节点是祖父节点的左子节点还是右子节点if (z->parent == z->parent->parent->left){// 叔父节点rbtree_node *y = z->parent->right;if (y->color == RED){// 情况1：父节点和叔父节点都是红色z->parent->color = BLACK;y->color = BLACK;z->parent->parent->color = RED;// 继续对祖父节点进行修复z = z->parent->parent;}else{// 情况2：父节点是红色，叔父节点是黑色if (z == z->parent->right){z = z->parent;rbtree_right_rotate(tree, z);}// 情况3：父节点是红色，叔父节点是黑色if (z == z->parent->left){z->parent->color = BLACK;z->parent->parent->color = RED;rbtree_right_rotate(tree, z->parent->parent);}}}else{// 对称处理右子树的情况}}
}// 插入节点到红黑树
void rbtree_insert(rbtree *t, rbtree_node *z)
{// 寻找插入位置rbtree_node *x = t->root;rbtree_node *y = t->nil;while (x != t->nil){y = x;if (z->key < x->key){x = x->left;}else if (z->key > x->key){x = x->right;}else{// 如果键值已存在，则不插入return;}}// 将z插入到y的适当位置if (y->key >= z->key){y->left = z;}else{y->right = z;}z->parent = y;z->left = t->nil;z->right = t->nil;z->color = RED;// 插入后修复红黑树性质rbtree_insert_fixup(t, z);
}
