二叉树与红黑树重制版(二)

本文主要是介绍二叉树与红黑树重制版(二)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

介绍

红黑树是网红，应用非常广泛。对于二叉排序树，有些极端的情况下会转成链表，降低了效率，所以引入了平衡因子，而对于AVL平衡树是强平衡，实现起来较复杂；所以引入了弱平衡的红黑树。

定义性质

1 每个结点都是红的或黑的
2 根结点为黑
3 叶子结点为黑
4 若一个结点为红，则两个儿子都是黑
5 对于每个结点，从该结点到其子孙结点的所有路径上包含相同的黑结点高度。

应用

两种用法：

a) key_value方式用于查找，性能快O(logn)
b) 使用中序遍历（注意层次遍历和中序遍历是一样的）

应用：
1 Linux进度调度CFS
2 Nginx Timer事件管理
3 Epoll事件块处理等

旋转

三个方向，六根指针进行操作
在这里插入图片描述


//左旋 参数：红黑树T,当前结点轴心
void rbtree_left_rotate(rbtree *T, rbstree_node *x){rbtree_node *y = x->right;//x y 都拿到了//1 第一步 x的柚子树指向y的左子树x->right = y->left;//2 第二步 y的左子树不等nilif (y->left != T->nil){y->left->parent = x;}//3 第三部 y的parent指向原来x的parenty->parent = x->parent;//4 第四部 x的parent为nil,则x是根结点if (x->parent == T->nil){T->root = y;}else if(x == x->parent->left){x->parent->left = y;}else{x->parent->right = y;}//5 第五部y->left = x;//6 第六部x->parent = y;}//右旋 的基础上 x-->y   y-->x  left-->right  right-->left
void rbtree_right_rotate(rbtree *T, rbstree_node *x){rbtree_node *x = y->left;//x y 都拿到了y->left = x->right;if (x->right != T->nil){x->left->parent = y;}x->parent = y->parent;if (y->parent == T->nil){T->root = x;}else if(y == y->parent->right){y->parent->right = x;}else{y->parent->left = x;}x->right = y;y->parent = x;}

添加

在这里插入图片描述

三种情况：
父节点是祖父结点的左子树情况
1 叔结点是红色
2 叔结点是黑色，且当前结点是右子树
3 叔结点是黑色，且当前结点是左子树

void rbtree_insert_fixup(rbtree *T, rbtree_node *z) {while (z->parent->color == RED) { //z ---> REDif (z->parent == z->parent->parent->left) {rbtree_node *y = z->parent->parent->right;if (y->color == RED) {z->parent->color = BLACK;y->color = BLACK;z->parent->parent->color = RED;z = z->parent->parent; //z --> RED} else {if (z == z->parent->right) {z = z->parent;rbtree_left_rotate(T, z);}z->parent->color = BLACK;z->parent->parent->color = RED;rbtree_right_rotate(T, z->parent->parent);}}else {rbtree_node *y = z->parent->parent->left;if (y->color == RED) {z->parent->color = BLACK;y->color = BLACK;z->parent->parent->color = RED;z = z->parent->parent; //z --> RED} else {if (z == z->parent->left) {z = z->parent;rbtree_right_rotate(T, z);}z->parent->color = BLACK;z->parent->parent->color = RED;rbtree_left_rotate(T, z->parent->parent);}}}T->root->color = BLACK;
}void rbtree_insert(rbtree *T, rbtree_node *z) {rbtree_node *y = T->nil;rbtree_node *x = T->root;//找到z指定的位置while (x != T->nil) {y = x;if (z->key < x->key) {x = x->left;} else if (z->key > x->key) {x = x->right;} else { //Existreturn ;}}z->parent = y;if (y == T->nil) {T->root = z;} else if (z->key < y->key) {y->left = z;} else {y->right = z;}z->left = T->nil;z->right = T->nil;z->color = RED;rbtree_insert_fixup(T, z);
}

删除

在这里插入图片描述

void rbtree_delete_fixup(rbtree *T, rbtree_node *x) {while ((x != T->root) && (x->color == BLACK)) {if (x == x->parent->left) {rbtree_node *w= x->parent->right;if (w->color == RED) {w->color = BLACK;x->parent->color = RED;rbtree_left_rotate(T, x->parent);w = x->parent->right;}if ((w->left->color == BLACK) && (w->right->color == BLACK)) {w->color = RED;x = x->parent;} else {if (w->right->color == BLACK) {w->left->color = BLACK;w->color = RED;rbtree_right_rotate(T, w);w = x->parent->right;}w->color = x->parent->color;x->parent->color = BLACK;w->right->color = BLACK;rbtree_left_rotate(T, x->parent);x = T->root;}} else {rbtree_node *w = x->parent->left;if (w->color == RED) {w->color = BLACK;x->parent->color = RED;rbtree_right_rotate(T, x->parent);w = x->parent->left;}if ((w->left->color == BLACK) && (w->right->color == BLACK)) {w->color = RED;x = x->parent;} else {if (w->left->color == BLACK) {w->right->color = BLACK;w->color = RED;rbtree_left_rotate(T, w);w = x->parent->left;}w->color = x->parent->color;x->parent->color = BLACK;w->left->color = BLACK;rbtree_right_rotate(T, x->parent);x = T->root;}}}x->color = BLACK;
}rbtree_node *rbtree_delete(rbtree *T, rbtree_node *z) {rbtree_node *y = T->nil;rbtree_node *x = T->nil;//1 当前就只有一个结点if ((z->left == T->nil) || (z->right == T->nil)) {y = z;} else {y = rbtree_successor(T, z);}if (y->left != T->nil) {x = y->left;} else if (y->right != T->nil) {x = y->right;}x->parent = y->parent;if (y->parent == T->nil) {T->root = x;} else if (y == y->parent->left) {y->parent->left = x;} else {y->parent->right = x;}if (y != z) {z->key = y->key;z->value = y->value;}if (y->color == BLACK) {rbtree_delete_fixup(T, x);}return y;
}