文明校园建设专题网站,手机网站 手机app,北京建网站需要多少钱,网站科技动效文章目录1. 使用场景2. 性质3. 结点定义4. 结点旋转5. 结点插入1. 使用场景
Linux进程调度CFSNginx Timer事件管理Epoll事件块的管理
2. 性质
每一个节点是红色或者黑色根节点一定是黑色每个叶子节点是黑色如果一个节点是红色#xff0c;那么它的两个儿子节点都是黑色从任意…
文章目录1. 使用场景2. 性质3. 结点定义4. 结点旋转5. 结点插入1. 使用场景
Linux进程调度CFSNginx Timer事件管理Epoll事件块的管理
2. 性质
每一个节点是红色或者黑色根节点一定是黑色每个叶子节点是黑色如果一个节点是红色那么它的两个儿子节点都是黑色从任意一个节点到其每个叶子节点的所有路径都包含相同数目的黑色节点
3. 结点定义
typedef int KEY_TYPE;typedef struct _rbtree_node
{unsigned char color;struct _rbtree_node *left;struct _rbtree_node *right;struct _rbtree_node *parent;KEY_TYPE key;void *value;
}rbtree_node;4. 结点旋转 左旋实现
void _left_rotate(rbtree *T, rbtree_node *x)
{rbtree_node *y x-right;x-right y-left;if (y-left ! T-nil){y-left-parent x;}y-parent x-parent;if (x-parent T-nil){T-root y;}else if (x x-parent-left){x-parent-left y;}else if (x x-parent-right){x-parent-right y;}y-left x;x-parent y;
}右旋实现
void _right_rotate(rbtree *T, rbtree_node *y)
{rbtree_node *x y-left;y-left x-right;if (x-right ! T-nil){x-right-parent y;}x-parent y-parent;if (y-parent T-nil){T-root x;}else if (y y-parent-left){y-parent-left x;}else if (y y-parent-right){y-parent-right x;}x-right y;y-parent x;
}5. 结点插入 将新节点的颜色设为红色然后按照二叉查找树的规则插入到合适的位置 如果设置成黑色的话则必定会违反上述五条性质中的第五条 如果新节点是根节点那么将其颜色改为黑色结束 如果新节点的父节点是黑色那么不需要做任何调整结束 如果新节点的父节点和叔叔节点父节点的兄弟节点都是红色那么将它们的颜色改为黑色将祖父节点父节点的父节点的颜色改为红色然后把祖父节点作为新的当前节点重复步骤2和3 如果新节点的父节点是红色但叔叔节点是黑色或不存在那么分四种情况进行旋转和变色操作 新节点是父节点的左子节点且父节点是祖父节点的左子节点左左情况那么对祖父节点进行右旋并交换祖父和父亲的颜色新节点是父节点的右子节点且父节点是祖父节点的左子节点左右情况那么对父亲节点进行左旋并交换新节点和父亲节点的颜色然后把新节点作为当前节点转化为左左情况处理新节点是父亲节点的右子节点且父亲节点是祖父节点的右子节点右右情况那么对祖父节点进行左旋并交换祖父和父亲的颜色新节点是父亲节点的左子节点且父亲节点是祖父节点的右子节点右左情况那么对父亲节点进行右旋并交换新节点和父亲节点的颜色然后把新节点作为当前节点转化为右右情况处理
int key_compare(KEY_TYPE *a, KEY_TYPE *b)
{//TODO
}void rbtree_insert_fixup(rbtree *T, rbtree_node *z)
{while (z-parent-color RED){if (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;}else{if (z z-parent-right){z z-parent;_left_rotate(T, z);}z-parent-color BLACK;z-parent-parent-color RED;_right_rotate(T, z-parent-parent);}}}T-root-color BLACK;
}void rbtree_insert(rbtree *T, rbtree_node *z)
{rbtree_node *x T-root;rbtree_node *y T-nil;while (x ! T-nil){y x;// 如果是自定义类型可以实现key_compare接口来进行比较if (x-key z-key){x x-right;}else if (x-key z-key){x x-left;}else{return;}}z-parent y;if (y T-nil){T-root z;}else if (z-key y-key){y-right z;}else{y-left z;}z-left T-nil;z-right T-nil;z-color RED;rbtree_insert_fixup(T, z);
}
