红黑树简介
在红黑树中，每个节点可能有两种不同的颜色:红色或黑色。红黑树总是满足以下五个条件:
红黑树可以旋转、添加节点和删除节点。旋转操作分为左手操作和右手操作。左手是指原父节点的右叶节点成为新父节点，原父节点成为新父节点的左叶节点。向左转时，由于节点间的指针发生了变化，原来的右叶节点的左子树的位置被原来的父节点占据，必须为其寻找新的父节点。显然，因为这个子树中所有节点的值都小于原来的右叶节点，并且都大于原来的父节点，所以可以把它作为原来父节点的右子树。右手旋转的情况基本相同。
红黑树的插入操作比普通的二叉查找树更复杂，因为它需要维护红黑树的五个属性，这些属性在插入时会发生变化。前半部分的插入操作与普通二叉查找树基本相同。继续在树中搜索，直到找到合适的位置，将新节点作为叶节点插入树中。然后，该节点被标记为红色。剩下的工作就是调整红黑树每个节点的颜色，以保持红黑树的属性。
在节点下插入红色节点可能会导致以下情况:
对于第二种情况，很容易处理，只需将节点的颜色改为黑色。第一种情况比较复杂。
根据处理方法的不同，根据父节点的兄弟节点的颜色可以分为三种情况:
红黑树的删除也比二叉树复杂。如果红色节点被删除/移动，它基本上与二叉查找树一致，因为它没有破坏红黑树的任何属性。如果删除一个黑色节点，其父节点的黑色高度将会不一致。
删除时，除了删除二叉查找树，还需要记录被删除/移动节点的初始颜色，被移动节点的颜色会变成被删除节点的颜色。
在下文中，要移动的节点被表示为Y。占据Y节点的原始位置的节点被表示为X..
删除时，会出现以下情况:
为了解决情况3的问题，移动Y节点后，给X节点赋一个重黑(这个重黑是从原Y节点继承的黑)，使其同时具有两种颜色。这样，通过X的简单路径的黑节点数可以暂时视为不变，性质保持不变。5.此时，X节点的颜色可能有两种情况:双黑或红黑。如果x是红色和黑色，将x设置为黑色。因为这不会影响x及其任何子节点的属性。如果x是双黑，就需要给其他节点分配额外的黑。接下来，可以分为以下几种情况: