红黑树是一种二叉搜索树，能够保持整棵树较为平衡，提高最坏查询效率，但是比AVL树更简单。
在红黑树中，每一个节点可能具有两种不同的颜色：红色或黑色。红黑树总是满足如下的5个条件：
- 根节点永远是黑色。
- 叶子节点永远是黑色。
- 如果一个节点是红色的，那么它的两个子节点都是黑色的。
- 每个节点是要么是红色的，要么是黑色的。
- 对每个结点，从该节点到任意一个后代叶子节点的简单路径上，经过的黑色节点的数量相同。
红黑树可以进行旋转、增加节点、删除节点的功能。旋转操作分为左旋和右旋。左旋指原父结点的右叶子节点成为新的父结点，而原父结点成为新父结点的左叶子节点。左旋时，因为节点之间指针发生了变动，原右叶子节点的左子树的位置被原父结点占据，必须为它寻找一个新的父结点。显然，由于这棵子树中所有节点的值小于原右叶子节点，又全部大于原父结点，它可以作为原父结点的右子树。右旋的情况基本相同。
红黑树的插入操作比普通的二叉搜索树要复杂，因为需要维护红黑树的5条性质，这些性质在插入时会被改变。插入操作的前半部分与普通的二叉搜索树基本相同。在树中不断搜索，直到找到一个合适的位置，将新节点作为叶子节点插入到树中。然后，节点被标记为红色。剩下的工作是为了调整红黑树的各个节点的颜色来维持红黑树的性质。
在一个节点下面插入一个红色的结点，有可能造成如下的几种情况：
- 如果它的父结点是红色，那么违反了性质3.
- 如果它是根节点，那么违反了性质1.
对于第二种情况，很好处理，只需要更改节点颜色为黑色就可以了。第一种情况比较复杂。
根据处理的方法不同，可以根据父结点的兄弟结点的颜色来分为三种情况:
- 父结点的兄弟节点也是红色的。这种情况很好处理。
在满足性质3时，父结点需要被标记为黑色，但是此时父结点的兄弟结点仍然为红色，破坏了性质5.这时可以将祖父结点变为红色，让父结点及其兄弟节点变为黑色。这样性质5仍然得到了满足，保证了以祖父结点作为根节点的子树仍然满足红黑树性质。接下来只需要递归地对祖父结点继续调整颜色，就可以保证整棵红黑树满足性质。 - 父结点的兄弟结点是黑色的。
在这种情况，如果将父结点简单的标记为黑色，那么也会破坏性质5，这时改变祖父结点的颜色无法帮助维护性质5.唯一的办法就是将以祖父结点为根节点的子树进行旋转。如果插入的结点位于祖父结点的左子树，那么进行左旋，让父结点变为新的祖父结点（如果被插入的结点是其父结点的右子节点，那么需要对以父结点为根的子树进行左旋，空出右子树的位置。如果符合此情况，那么原父结点成为插入节点的子节点，下文的子节点和父结点全部颠倒）。这时被插入的结点是红色，而父结点的右子节点，即原来的祖父结点仍然是黑色。父结点的左右子树的黑高相差1.只需要把父结点标记为黑色，然后把祖父结点标记为红色就可以消除这个差异。
红黑树的删除操作也较二叉树复杂。如果删除/移动的是红色节点，由于不破坏任何的红黑树性质，与二叉搜索树基本一致。如果删除的是黑色节点，将会导致其父结点的黑高不一致。
在进行删除操作时，除了二叉搜索树的删除操作外，还需要记录被删除/移动的节点的初始颜色，被移动的节点的颜色将会变为被删除的节点的颜色。
以下将被移动的节点记为y.占据y节点原来位置的节点记为x。
删除时会出现以下的几种情况：
- 如果被删除的是根节点，而替代它的是一个红色结点，那么会违反性质1.
- 如果y是黑色结点，y之前的父结点是红色节点，那x和y之前的父结点会违反性质3.
- 如果移动了y,那么原来经过y的简单路径经过的黑色结点数量会少1,违反了性质5.
为了解决情况3的问题，在y结点被移动之后，给x结点再指派一重黑色（这一重黑色是继承了原来y结点的黑色），使其同时具有两重颜色。这样可以使经过x的简单路径的黑色节点数量暂时视为不变，保持性质5.这时，x结点的颜色可能有两种情况：双重黑色或红黑色。如果x是红黑色，就将x设定为黑色。因为这个不影响x及其任意子节点的性质。如果x是双黑色，就需要将多余的黑色指派给别的结点。接下来可以分成以下的几种情况：
- x的兄弟结点w是黑色结点，w的右孩子是红色节点。注意x对应两个黑结点。这时候以x的父结点为根节点的子树要求其左孩子对应的子树的根（加上它的孩子）有两个黑结点，右孩子有一个黑结点。只要对这个子树进行左旋，然后将x的父结点变为黑结点，然后原来的w的颜色和原来的x的父结点的颜色相同即可。
- x的兄弟结点w是黑色结点，w的右孩子是黑色节点，w的左孩子是红色节点。注意到，只要将以w为根的子树进行右旋，将w左孩子的颜色变为黑色，w的颜色变为红色，即可转化为情况1.注意，因为不知道x父结点的颜色，所以将原来的w的颜色变为黑色以避免违反性质3.同时为了避免原w为根的子树的叶子节点的黑高发生变化，w必须被设置为红色。
- x的兄弟结点w是黑色结点，w的所有孩子都是黑色结点。这时候将x和w的黑色去除，即将x变为单黑结点，w变为红结点。然后将x父亲的颜色上再加一重黑色。这样就可以递归地将问题推向父结点。假如父结点是红黑色，那么直接设置为黑色即可。假如是双黑色，那么重复本算法。
- x的兄弟结点w是红色结点。这时候可以判断x的父结点必是黑结点。所以只要将树左旋，将x的父结点设置为红结点，将原来的w设置为黑结点，就将问题转换为情况3.
