红黑树的由来

BST存在问题

BST（二叉查找树）存在的问题是，树在插入的时候会导致倾斜，不同的插入顺序会导致树的高度不一样，而树的高度直接影响了树的查找效率，最坏的情况所有的结点都在一条斜线上，这样树的高度为N。

基于BST存在的问题，平衡查找二叉树（Balanced BST）产生了。平衡树在插入和删除的时候，会通过旋转操作将高度保持在logn。其中两款具有代表性的平衡树分别为AVL树（高度平衡树，具备二叉搜索树的全部特性，而且左右子树高度差不超过1，通过左旋和右旋实现平衡）和红黑树。

AVL树由于实现比较复杂，而且插入和删除性能差，在实际环境下的应用不如红黑树。

二叉树的删除操作：本质上是找前驱或者后继结点来替代。

删除的情况：

红黑树删除操作和二叉树一样，只不过红黑树多了着色和旋转过程。

2-3-4树是四阶的B树（Balance Tree），它属于一种多路查找树，它的结构有以下限制：所有叶子结点都拥有相同的深度。

节点只能是2-结点、3-结点、4-结点之一。

所有结点必须至少包含1个元素。

元素始终保持排序顺序，整体上保持二叉查找树的性质，即父结点大于左子结点，小于右子结点；而且结点有多个元素时，每个元素必须大于它左边的和它的左子树中元素。

2-3-4树的查询操作像普通的二叉搜索树一样，非常简单，但由于其结点元素数不确定，在一些编程语言中实现起来并不方便，实现一般使用它的等同——红黑树。

2-3-4树中结点添加需要遵守以下规则：

插入都是向最下面一层插入；
升元：将插入结点由2-结点升级成3-结点，或由3-结点升级成4-结点；
向4-结点插入元素后，需要将中间元素提到父结点升元，原结点变成两个2-结点，再把元素插入2-结点中，如果父结点也是4-结点，则递归向上层升元，至到根结点后将树高加1；

而将这些规则对应到红黑树里，就是：

新插入的结点颜色为红色，这样才可能不会对红黑树的高度产生影响。
2-结点对应红黑树中的单个黑色结点，插入时直接成功（对应2-结点升元）
3-结点对应红黑树中的黑+红子树，插入后将其修复成红+黑+红子树（对应3-结点升元）
4-结点对应红黑树中的红+黑+红子树，插入后将其修复成红色祖父+黑色父叔+红色孩子子树，然后再把祖父结点当成新插入的红色结点递归向上层修复，直至修复成功或遇到root结点。

红黑树是一种结点带有颜色属性的二叉查找树，但它在二叉查找树之外，还有以下5大性质：

下图就是一个典型的红黑树：

变色：结点的颜色由黑变红或者由红变黑；

左旋：以某个结点作为旋转点，其右子结点变为旋转节点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。

右旋：以某个结点作为旋转点，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。

新增：分情况讨论，主要是要找到插入位置，然后自平衡（左旋或者右旋）且插入结点是红色（如果是黑色的话，那么当前分支上就会多出一个黑色结点出来，从而破坏了黑色平衡），以下分析全部以左子树为例子，右子树的情况则相反。

如果插入的是第一个结点（根结点），红色变黑色。
如果父结点为黑色，则直接插入，不需要变色。
如果父结点为红色，叔叔结点也是红色（此种情况爷爷结点一定是黑色），则父结点和叔叔结点变黑色，爷爷结点变红色。（如果爷爷结点是根结点，则再变成黑色），爷爷结点此时需要递归（把爷爷结点当做新插入的结点再次进行比较）
如果父结点是红色，没有叔叔结点或者叔叔结点是黑色（此时只能是NIL节点），则以爷爷结点为支点右旋，旋转之后原来的爷爷结点变红色，原来的父结点变黑色。

通俗点讲就是三句话：自己能搞定的自己搞定；搞不定的找兄弟和父亲帮忙；父亲和兄弟都帮不了那有福同享，有难同当（父亲和兄弟自损）

自己能搞定的自己搞定：

搞不定的找兄弟和父亲帮忙：

兄弟和父亲结点帮不了忙，于是开始递归自损。

前提是找到“真正”的兄弟结点，兄弟结点没有多余的元素可借（此时兄弟结点一定为黑色2结点），此时兄弟结点所在分支也要自损一个黑色结点以此达到黑色平衡，最快的方式就是兄弟结点直接变红（相当于就是减少一个黑色结点），此时一父结点为root的子树又达到了平衡（两边都比之前少一个黑色）。但是以祖父结点为root的树依然是不平衡的，此时需要递归处理。