一. 规则
1. 根节点必须是黑色；
2. 节点要么是黑色要么是红色；
3. 叶子节点都为黑色；
4. 从任意节点出发到根节点，所经历的黑色节点的数目相同
5. 如果节点为红，其子节点必须为黑
二.插入
1.当前节点是根节点：把根节点改为黑色
2.当前节点的父节点是黑节点，保持不变
3.当前节点的父节点是红节点，并且当前接电费的叔叔节点是红色：把父节点和叔叔节点改为黑色，把祖父节点改为红色，把祖父节点作为当前节点，向上判断
4.当前节点的父节点是红节点，并且当前叔叔节点不是红节点：旋转，可以分为两种情况，即外侧插入和内侧插入
外侧插入进行左旋或者右旋，内侧插入则需要进行双旋转，可以细分为一下四种情况：
a). 祖父节点 -> 父节点 -> 当前节点， 一直向右：做左旋，再把父节点改为黑色，之前的祖父节点改为红色
b). 祖父节点 -> 父节点 -> 当前节点，一直向左：做右旋，再把父节点改为黑色，之前的祖父节点改为红色
c). 祖父节点 -> 父节点 -> 当前节点，先向左再向右：先对当前节点做左旋，再对当前节点做右旋，然后把当前节点改为黑色，之前的祖父节点改为红色
d). 祖父节点 -> 父节点 -> 当前节点，先向右再向左： 先对当前节点做右旋，再对当前节点做左旋，然后把当前节点改为黑色，之前祖父节点改为红色
参考链接：https://algs4.cs.princeton.edu/33balanced/
原文：https://www.cnblogs.com/BaymaxHH/p/14828873.html