思想
是二叉搜索树（左<根<右）的一种。
要满足以下特性：
- 根和叶子节点都是黑色。
- 红色节点的两个孩子都必须是黑色，即不存在两个连续的红色节点。
- 从任意节点到它的叶子节点路径上的的黑色节点数量相同
可简记为左根右，根叶黑，不红红，黑路同。
比较特别的是红黑树的所有叶子节点都是空节点，这么做是为了保证性质——从任意节点到它的叶子节点路径上的的黑色节点数量相同。
并因为有这个性质的存在，使得红黑树从根节点到叶子节点的最长路径不超过最短路径的两倍。因为每条路的黑色节点数量是相同的，并且红色节点不能连续出现，所以如果一个根到叶子的最短路是三个黑色节点的话，根到叶子的最长路最多为三个黑色节点和两个红色节点，黑色节点和红色节点交替出现，共五个节点（怎么这里也有325）。换句话说就是任意节点左右子树的高度相差不超过两倍。
ps：因为AVL树要求任意节点左右子树的高度相差的绝对值不超过1，所以查询上更高效，但要靠不停旋转来保证性质，所以红黑树的插入和删除更高效，时间复杂度都为，差距不大。应用中红黑树更广泛，c++ STL的map和set用的都是红黑树。
插入
与二叉搜索树的插入一样，插入时颜色默认为红（显然在一个满足黑路同的红黑树中插入一个黑节点必然会破坏性质，所以插入红色节点会更容易维护）。
如果插入后导致红黑树的性质被破坏了我们就要进行分讨。
- 若插入节点为根节点，直接变黑即可。
- 插入导致两个红色节点连续后，若插入节点的叔叔（父亲的兄弟）是红色，则其父亲和叔叔变成黑色，爷爷变红色，然后插入节点变成爷爷，再去判断是否符合性质，构成循环。
- 插入导致两个红色节点连续后，若插入节点的叔叔（父亲的兄弟）是黑色，要判断是中的哪一种，再去旋转。
右旋：将节点的左儿子变成父亲，当前节点去当右边儿子，原左儿子的右儿子变成当前节点的左儿子。然后原左儿子取代当前节点的位置。
左旋：将节点的右儿子变成父亲，当前节点去当左儿子，原右儿子的左儿子变成当前节点的右儿子。然后原右儿子取代当前节点的位置。
- ：右旋爷爷。然后原父亲红变黑，原爷爷黑变红。
- ：左旋爷爷。然后原父亲红变黑，原爷爷黑变红。
- （父亲为爷爷的左儿子，插入节点为父亲的右儿子）：左旋爸爸，再右旋爷爷。插入节点红变黑，原爷爷黑变红。
- （父亲为爷爷的右儿子，插入节点为父亲的左儿子）：右旋爸爸，再左旋爷爷。插入节点红变黑，原爷爷黑变红。
构建过程就是依次插入每个节点。
删除
以下删除操作均指删除有值的节点，不包含空节点。
二叉搜索树的删除都一个样子：
- 没有孩子：直接删除。
- 只有左/右子树：直接代替。
- 左右子树都有：去找前驱/后继代替这个位置的值，然后删除前驱/后继（转化为前两种情况）。
但为了维护红黑树的性质，删除要麻烦一些。
因为第三种情况就是转化为前两种情况，所以这里我们只讨论前两种情况。
然后因为性质的限制，我们发现第二种情况中只可能是一个黑节点带一个红儿子，因为如果此时红节点有儿子的话，红儿子会违反不红红的性质，黑儿子会违反黑路同的性质（第二种情况中左右子树必空一个，此时如果红儿子下面有黑节点的话必定比那个空的子树多一个黑节点）。又不可能是一个红节点带一个黑儿子，因为无论黑儿子在那边都会违反黑路同的性质。所以我们删除掉的一定是一个黑节点，此时让红节点代替原来黑节点的位置再让红节点为黑色就好了。
对于第一种没有孩子的情况，我们要判断删除的是红节点还是黑节点，红节点直接删就可以了，但黑节点会超级麻烦。我们要进行大分讨。
首先，删除的节点我们定义为双黑节点，此时如果双黑节点的兄弟是黑色我们再去看兄弟的儿子，如果至少有一个红儿子，去判断是中的哪种（），两个儿子都是红色按型或型处理。
- ：兄弟的左儿子变成兄弟的颜色，兄弟的颜色变成父亲的颜色，父亲变成黑色。然后对父亲节点右旋，双黑节点再变成单黑节点，即空节点。
- ：兄弟的右儿子变成兄弟的颜色，兄弟的颜色变成父亲的颜色，父亲变成黑色。然后对父亲节点左旋，双黑节点再变成单黑节点，即空节点。
- ：让兄弟节点的右儿子变黑，父亲节点变黑。然后左旋兄弟右旋父亲，双黑节点再变成单黑节点，即空节点。
- ：让兄弟节点的左儿子变黑，父亲节点变黑。然后右旋兄弟左旋父亲，双黑节点再变成单黑节点，即空节点。
然后再来看另一种情况，即黑兄弟的儿子都是黑色的（空节点也算黑色）。首先让兄弟变成红色，此时对于以他们父亲为根的节点而言，相当于路径上都少了个黑节点，此时我们将双黑节点进行上移，就转换成了在更大的树中去循环判断。如果双黑节点上移到了红色节点直接变成单黑节点就好。如果直接上移到了根节点，说明此时所以路径都少了一个黑节点，没有破坏性质，直接变成单黑节点就好了。
双黑节点的兄弟是黑节点的情况就没了，如果兄弟是红节点的话，兄弟变成红色父亲变成黑色，然后让父亲朝着双黑节点的方向旋转。保持双黑节点继续循环判断。
删除操作就解决了。