红黑树

红黑树，Red-black[RBT]是一个自平衡【不是绝对平衡】的二叉查找树

树上的节点必须满足以下规则

1.每个节点要么是红色，要么是黑色

2.根节点必须是黑色

3.每个叶子节点【NIL】是黑色

4.每个红色节点的两个子节点必须是黑色

5.任意节点到每个叶子节点的路径包含相同数量的黑节点

黑平衡二叉树

1.recolor 重新标记节点为红色或黑色

2.rotation 旋转，使树达到平衡

红黑树能自平衡的关键操作，左旋，右旋和变色

左旋：以某个节点作为支点（旋转节点），其右子节点变为旋转节点的父节点，右子节点的左子节点变为旋转节点的右子节点，左子节点保持不变。

右旋 : 以某个节点作为支点（旋转节点），其左子节点变为旋转节点的父节点，左子节点的右子节点变为旋转节点的左子节点，右子节点保持不变。

变色 : 节点的颜色由红变黑，或由黑变红。