一、特点：

① 每个红黑树节点都是黑色或者红色

② 根节点都是黑色

③ 每个叶子节点都是黑色（指向空的叶子节点）

④ 如果一个叶子节点是红色，那么其子节点必须都是黑色的

⑤ 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点（就是单独剔除红节点后的情况）

二、红黑树的维持平衡机制

在插入删除时要弄懂红黑树的维持平衡机制，即当插入或删除后，该结构满足不了红黑树的条件时，就会进行一下操作，左旋，右旋，颜色反转

1、左旋

逆时针旋转红黑树，理解为所有节点都左移一次，而 3 不可能有3个节点，故 4 就顺着顺序给了 2 当子节点

2、右旋

顺时针旋转红黑树，同理

3、颜色反转

①以红黑树的要求为基准，进行颜色的变更，但根节点是不会变化的

②当插入的红节点的父节点也为红节点，就得进行颜色反转

三、插入操作

时间复杂度：O（logn）

插入的默认为红节点，因为黑节点不好控制其红黑树的平衡，很难通过左旋右旋或者颜色变更来保持红黑树的特点。变色是不能原来的单个节点变化的。

①没有根节点，或者说没有父节点

②直接在黑节点上插入红节点，不用改变

③父节点是红节点，叔节点是黑节点，而祖父节点是黑节点（LL），插入的是左节点

④ 父节点是红节点，叔节点是黑节点，而祖父节点是黑节点（LR），插入的是右节点

⑤RR同理

⑥RL同理