红黑树的性质
红黑树是一直自平衡二叉搜索树，在二叉搜索树的基础上具有额外的颜色性质：
- 节点具有颜色属性，不是红色就是黑色；
- 根节点是黑色；
- 所有叶子节点（NULL节点）是黑色；
- 一个红色节点的左右子节点都是黑色，即从根到叶子的路径中不能出现连续2个红节点；
- 从任何节点到叶子的路径，左右两边路径中的黑色节点数量相同。
红黑树的优点
红黑树在插入和删除操作中需要维护上述颜色性质，以维护这些性质的操作代价（多次对相关节点重新着色以及旋转）来达到在搜索、插入、删除数据场景下的最好/平均/最坏时间复杂度保障为O(log n)，相比其他数据结构有稳定的性能表现：
- 比如和Hash Table/Map相比，在最坏情况下，Hash Table搜索/插入/删除相应操作的时间复杂度由O(1)退化为O(n)，不如红黑树。
- 和AVL树相比，红黑树对平衡限制较为宽松，在插入/删除场景下不需要太多次旋转操作即可满足性质，其性能更优，AVL树有更低的树高度因此在搜索场景下AVL树性能更高。
凭借上述优点，红黑树数据结构被广泛使用，如C++ STL中的std::map, std::set，Linux内核中IO多路复用epoll等。
红黑树的插入操作
红黑树中插入节点数据时：
- 首先根据二叉搜索树的规则找到插入位置，并将新插入节点颜色设置为红色。因为如果将其设置为黑色马上就违反了其性质5，而设置为红色还有几率不违反其他性质，从而在这一步就结束插入。
- 如果新节点是根节点，就把其颜色改为黑色，结束插入操作。
- 否则记新节点为x，其父节点为p = x.parent，如果父节点y的颜色为黑色，则新节点不违反任何性质，结束插入操作。
- 否则父节点p颜色为红色，新节点x也为红色，违反了性质4，需要进一步操作：
- 记父节点p的父节点为g = x.parent.parent，此时g一定存在并为黑色，因为p是红色p一定不可能是根节点。
- 如果x的uncle节点（即y的兄弟节点，记为u）是红色，这里只需要重着色：
6.1 将u和p都变为黑色，此时g向下路径上的黑色节点数增加了1；
6.2 将g变为红色，此时抵消了前一步将u,p变为黑色的影响，此时g有可能违反性质4，转到步骤2继续向上检查。
- 如果u是黑色，这里需要旋转和重着色：
7.1 如果x, p, g逻辑上构成三角形，则针对p进行旋转，将x作为新的p，原p作为x，使得x,p,g逻辑上为一直线，变成7.2的情况继续处理。比如：
7.1.1 如果p是g的左子节点，且x是p的右子节点，则对p进行左旋转，此时x变为p的父节点，p为x的左子节点，g为x的父节点，此时将x作为新的p, p作为新的x;
7.1.2 如果p是g的右子节点，且x是p的左子节点，则对p进行右旋转，此时x变为p的父节点，p为x的右子节点，g为x的父节点，此时将x作为新的p, p作为新的x;
7.2 如果x, p, g逻辑上构成一直线，将g变为红色，将p变为黑色，然后进行旋转：
7.2.1 如果p是g的左子节点，则对g进行右旋转，此时p顶替g的位置，g变为p的右子节点；
7.2.2 如果p是g的右子节点，则对g进行左旋转，此时p顶替g的为是，g变为p的左子节点；
此时已经不违反任何性质，可终止操作。
红黑树的删除操作
从红黑树中删除节点数据时：
- 根据二叉搜索树规则找到要删除节点，如果该节点有2个非空子节点，则找到该节点在中序遍历中的直接后继节点，将直接后继节点的值赋值到该节点，变要删除的节点为该直接后继节点，此时要删除节点最多有一个非空子节点。
- 如果要删除的节点是红色，则直接删除该节点，让其子节点顶替其位置，不会破坏任何性质，结束删除操作。
- 如果要删除的节点是黑色，则直接删除该节点后会将该节点所在路径的黑节点数量减1，破坏了性质5，此时需要后续操作。
- 此时记删除节点后顶替其位置的子节点为x，此时x的父节点为p, x的兄弟节点为s。
- 如果此时x为根节点，则保证其颜色为黑色（若是空节点其本身为黑色，否则将其节点颜色置为黑色），并结束删除操作。
- 否则此时x不为根节点，如果x为红色，则将其颜色置为黑色，这已经抵消了其路径上黑色节点数减少1的问题，这里结束删除操作。
- 如果x为黑色，需要看其兄弟节点s及兄弟节点的子节点：
7.1 如果兄弟节点s是红色（此时父节点p一定是黑色，s的子节点也都是黑色），此时需要转换使得x的兄弟节点s是黑色进行后续操作，转换方式为：将兄弟节点s变为黑色，父节点p变为红色，父节点p向x的方向旋转，此时x的新兄弟节点一定是黑色，因为旋转时是把s的一个子节点作为p的新子节点顶替原来s的位置，x的新兄弟节点作为s，待后续操作；
7.2 如果兄弟节点s为黑色，这里又根据s的子节点颜色分情况进行处理：
7.2.1 如果兄弟节点s的两个子节点都是黑色，此时将s的颜色变为红色，s所在路径上和x所在路径上黑色节点数此时相同，而p所在路径上黑色节点数比其他路径上少1，将问题提升到p节点，将p作为新的x节点，回到步骤5继续执行操作；
7.2.2 如果兄弟节点s的子节点中离x较近的一个为红色，并且离x较远的一个为黑色，则需要转换将其变为离x较远的一个为红色的情况，转换方式为：将s置为红色，将s子节点中离x近的一个置为黑色，然后将s按远离x的方向旋转，此时原s子节点中离x近的一个成为新s，原s成为新s的子节点中离x远的一个，待后续操作；
7.2.3 如果兄弟节点s的子节点中离x较远的一个为红色（不管教近的一个是什么颜色），此时将兄弟节点s颜色置为和父节点p一样，然后p节点置为黑色（简单来说是s和p交换颜色），然后将p向x的方向旋转，并且把s子节点中离x较远的那个由红色变为黑色，此时达到了平衡状态，因为现在s的颜色和原来p的颜色一致，不改变原来p所在路径上黑色节点数量，而p现在顶替了原来x的位置并且颜色为黑色，补齐了之前其路径上减少的一个黑色节点，而s子节点中离x较远的那个变为黑色顶替了原来s的位置，也没有影响其路径上黑色节点数量，所以此时可以停止删除调整操作。
总结
这里仅以文字形式对红黑树做上述个人学习总结，以帮助自己增强理解，以后有时间再做图辅助说明（确实懒）。