红黑树工程中使用：
1.利用红黑树顺序功能（最小节点，最大节点）；2.利用红黑树快速查找的功能，key-value。
红黑树的应用场景：
nginx中用来管理timer，epoll中用红黑树管理fd，linux进程调度 用红黑树管理进程控制块，C++STL中map，set的底层实现全是用的红黑树。
红黑树性质：
1节点不是红色就是黑色
2根节点是黑色的
3所有叶子节点是黑色的
4红节点的两个孩子节点是黑色的
5对于每个节点 到叶子节点所有路径上包含相同数量的黑色节点
4和5是O(lgn)的保证，
红黑树平衡的是黑色节点的高度，红节点方便做旋转。4意味着一条路径上不可能有两个连续的红节点，因此每个红节点后面都有一个黑节点。
对于定义5，结合定义4，即代表红黑树最长路径最多是最短路径的两倍
节点旋转：
节点旋转
总共有三个方向需要改变（标红处），因为每个节点有指向父节点的指针，所有需要6个指针需要改变。
左旋：以x为轴心，获取y
x指向y的指针 改变成 x指向y 的左子树
1
y的左子树父指针指向 改变为 指向x
2
y的父指针 改变为指向 x的父指针所指
3
指向x的指针 改变成 指向 y ：这个需要判断x的父节点是否为root节点 或者 x是父节点的左孩子还是右孩子。
4
y指向左子树的指针 改变成 y指向x
5
x的父指针指向 修改为指向y
6
以上6个步骤就是左旋。
右旋上面思想一致，在左旋的基础上进行修改：将x修改成y，将y修改成x，将left修改成right，将right修改成left即可。
红黑树插入节点：
插入的节点是最底下的叶子节点，插入节点设置为红色，不影响黑色的高度，此时只有插入在红色节点下面的时候才会进行调整（违背性质）。
也就是说插入节点的父节点是红色的，需要进行调整。
已知插入节点z是红色的，父节点是红色的：则z的祖父节点是黑色的，z的叔父节点可能是红色的可能是黑色的。
当前节点永远是红色的。
父节点是红色的，叔父节点也是红色的，两边的高度是一致的。
父节点是红色的，叔父节点是黑色的，父节点的高度要大于叔父节点，往叔父节点这边旋转。
z父节点是其祖父节点的左子树left：
调整情况1.叔父节点红色： 修改父节点color为black，当前节点color=black，祖父节点color=red；把当前节点设置为祖父节点。变色保持黑高，无需旋转。
调整情况2.叔父节点黑色 ：2.1 如果z是父节点的右子树，以z的父节点为轴心进行左旋(z=z->parent)；2.2设置当前节点的父节点color=black；祖父节点color=red，以祖父为轴心进行右旋。
z父节点是其祖父节点的右子树，原理同上。
如何判断左旋还是右旋？哪边腿长，就往对方向旋转。
红黑树删除节点：
删除节点的实质是删除此节点的后继节点。后继的子树作为旋转的点。要删除的节点z被其后继节点y覆盖掉了，z是真正的删除节点，从z的左右子节点中选择一个节点进行调整
记作：覆盖节点（要删除的节点） z；真正删除的节点为y（后继节点），轴心节点为x。
后继节点（y）：此节点没有子树，则后继节点是其父节点；此节点有子树，后继是其右子树中最小的节点。
删除节点z：如果z只有一个子节点，则后继节点y即为z本身，y =z;
真正删除除的节点是黑色的节点，才需要进行调整，红色不影响黑高。
y为黑色，x是y的右子树：
如果x是红色的，把x变成黑色；
如果x是黑色的，需要进行调整。
红黑树源码实现地址：红黑树源码
网友评论