本文纯理论，代码见参考博客

参考博客：
《史上最清晰的红黑树讲解（上）》
《史上最清晰的红黑树讲解（下）》

红黑树5条性质：
性质1：节点是红色或者黑色。
性质2：根节点是黑色。
性质3：每个叶节点（空节点）是黑色。
性质4：每个红色节点的两个子节点都是黑色的。（从每个叶子到根的所有路径上不能有两个连续的红色节点）
性质5：从任一节点到其每个叶子到所有路径都包含相同数目的黑色节点。

左旋右旋不多细说，如下图。

红黑树主要方法：get（查），put（增），remove（删）

get

get方法也不多说，如其他二叉查找树。

put

首先按照get方法找到插入节点的位置，会出现以下几种情况：
注：除了第一种，其他情况插入的节点都是红色。因为如果插入黑色节点，就会违反性质5，需要大规模调整。如果插入红色节点，那就只要在插入节点的父节点也是红色时或者插入的节点是根节点时违反性质死或性质二，只需要改变一些节点颜色即可，不需要大规模调整。

1. 当要插入的是根节点的时候，直接插入。
2. 当要插入的节点的父节点是黑色的时候，直接插入即可，无需调整。
3. 当要插入的节点的父节点是红色的时候，插入后需要做下调整。

插入调整又分为6种情况，需要不断执行直到整棵树都满足五条性质为止（即目标节点的父节点不是红色且目标节点不为空不是根节点）：
注：目标节点为需要调整的节点，下同（两个红节点相连时，目标节点通常是孩子节点）

目标节点的父节点是其祖父节点的左孩子时：

• 情况1：目标节点父节点为红色，目标节点的叔父节点也是红色时，改变目标节点的父节点、叔父节点、祖父节点的颜色，目标节点更改为其祖父节点。
• 情况2：目标节点父节点为红色，目标节点的叔父节点为黑色，且目标节点是父节点的右孩子时，目标节点更改为其父节点，并对更改后的节点进行左旋。
• 情况3：目标节点父节点为红色，目标节点的叔父节点为黑色，且目标节点是父节点的左孩子时，改变目标节点父节点及其祖父节点的颜色，右旋目标节点的祖父节点。

目标节点的父节点是其祖父节点的右孩子时：

• 情况4：目标节点父节点为红色，目标节点的叔父节点也是红色时，改变目标节点的父节点、叔父节点、祖父节点的颜色，目标节点更改为其祖父节点。
• 情况5：目标节点父节点为红色，目标节点的叔父节点为黑色，且目标节点是父节点的左孩子时，目标节点更改为其父节点，并对更改后的节点进行右旋。
• 情况6：目标节点父节点为红色，目标节点的叔父节点为黑色，且目标节点是父节点的右孩子时，改变目标节点的父节点及其祖父节点的颜色，左旋目标节点的祖父节点。

remove（难点）

寻找后继节点（树中大于目标节点最小的元素）：

1. 若给定节点的右子树不为空，则后继节点就是其右子树中最小的那个元素；
2. 若给定节点的右子树为空，则后继节点为其第一个向左走的祖先。

首先以get方法找到需要删除的节点，然后考虑以下两种情况：

• 情况1、若删除点的左右子树都为空，或者有一个为空，则直接删除，有非空子树就用非空子树替代，若删除节点为黑色要做删除调整。
• 情况2、若删除点的左右子树都非空，则用后继节点替代删除节点，然后删除后继节点（此时后继节点必然满足情况1）。

删除调整分8种情况（当目标节点不为根节点并且颜色是黑色时循环执行）：

目标节点是其父节点的左孩子时：

• 情况1：若目标节点的兄弟节点为红色时，兄弟节点改为黑色，父节点改为红色，左旋父节点，并重新获取左旋之后的兄弟节点。
• 情况2：上接情况1，若兄弟节点的左右节点都是黑色时，将兄弟节点改为红色，目标节点变成其父节点。
• 情况3：上接情况1，若兄弟节点的左右节点不都是黑色时，如果兄弟节点的右孩子是黑色时，将兄弟节点的左孩子变为黑色，兄弟节点变为红色，右旋兄弟节点，重新获取右旋后的兄弟节点。
• 情况4：上接情况1或3，若兄弟节点的左右节点不都是黑色时，将兄弟节点变为目标节点的父节点的颜色，将父节点和兄弟节点的右孩子变为黑色，左旋父节点，目标节点改为根节点。

目标节点是其父节点的右孩子时：

• 情况5：若目标节点的兄弟节点为红色时，兄弟节点改为黑色，父节点改为红色，右旋父节点，并重新获取右旋之后的兄弟节点。
• 情况6：上接情况5，若兄弟节点的左右节点都是黑色时，将兄弟节点改为红色，目标节点变成其父节点。
• 情况7：上接情况5，若兄弟节点的左右节点不都是黑色时，如果兄弟节点的左孩子是黑色时，将兄弟节点的右孩子变为黑色，兄弟节点变为红色，左旋兄弟节点，重新获取左旋后的兄弟节点。
• 情况8：上接情况5或7，若兄弟节点的左右节点不都是黑色时，将兄弟节点变为目标节点的父节点的颜色，将父节点和兄弟节点的右孩子变为黑色，右旋父节点，目标节点改为根节点。

公共步骤：将目标节点变为黑色，以防止根节点不是黑色的