红黑树

最大高度是2*log(n+1),(100万个节点，最大树高是40)

搜索：O(logn),O(1)次的旋转

添加：O(logn),O(1)次的旋转

删除：O(logn),O(1)次的旋转

满足5个条件

1.节点是red或者black

2.根结点是black

3.叶子节点（外部节点，空节点）都是black

4.red节点的子节点都是black,red节点的parent都是black，从根结点到叶子节点不能有2个连续的红色节点

5.从任一节点到叶子节点的所有路径包含相同数量的BLACK节点

添加：（55,38,80,25,46,76,88,17,33,50,72）

假设添加的叶子节点为红色

一共有12中情况

4种parent节点是黑色，则不用处理(40,78,82,90)

4种parenet节点是红色，且uncle节点不是红色，进行染色（LL和RR:把parent染成黑色，把grand染成红色，LR和RL：把node染成黑色，把grand染成红色）+旋转（AVL树的旋转,LL右旋转，RR左旋转，LR parent进行左旋转 grand进行右旋转 RL parent进行右旋转，grand进行左旋转）(48,52,60,74)

4种parent节点是红色，且uncle节点为红色，进行染色（parent和uncle染成黑色）+上溢(10,20,30,36)

删除：

删除的是红色，直接删除

删除的节点有两个红色子节点，只需要找到后继节点（或前驱节点）替代

删除的节点有一个子节点，且这个子节点为红色，直接把子节点替代并染黑（20, 98, 97, 79, 47, 42, 60, 73, 72, 64, 61, 82, 52, 25）

删除的是黑色叶子节点：

如果删除的黑色子节点的兄弟节点也是黑色：

如果兄弟节点至少有一个红色子节点，进行旋转操作，旋转之后中间的节点继承父节点的颜色，旋转之后的左右节点染为black（55,87,56,74,96,22,62,20,70,68,90,50）

如果兄弟节点没有红色节点可以借，如果父节点是红色则不会造成下溢，将兄弟节点染成红色，父节点染成黑色即可，如果父节点是黑色，会导致父节点下溢，只需要把父节点当做被删除的节点处理即可

删除的叶子节点的兄弟节点是红色的，兄弟节点染成黑色，父节点染成红色，进行旋转，旋转后叶子节点的兄弟节点变成了黑色，参考上面的方法进行删除