一、什么是红黑树？
1）定义与性质
红黑树，又称为“对称二叉B树”，是一种自平衡的二叉查找树。
红黑树是一种每一个结点都带有颜色属性的二叉查找树，颜色或是红色或是黑色。可以把一颗红黑树视为一颗扩充的二叉树，用外部结点表示空指针。
红黑树除了具有二叉排序树的所有性质之外，还具有以下三点性质：
性质1：根节点和所有外部结点的颜色都是黑色的。
性质2：从根节点到外部结点的所有路径上没有两个连续的红色结点。
性质3：从根节点到外部结点的所有路径上都包含相同数目的黑色结点。
在上图树中，长方形的标有NIL的结点是外部结点(叶子结点)，带阴影的圆形是黑色结点，不带阴影的圆形是红色结点，粗线为黑色指针，细线为红色指针。
2）红黑树的查找
由于每一颗红黑树都是一颗二叉排序树，因此，在对红黑树进行查找时，可以采用运用于普通二叉排序树上的查找算法，在查找过程中不需要颜色信息。
对普通二叉排序树进行查找的时间复杂度为O(h)，其中h为二叉排序树的深度，对于红黑树则为O(log2n)。
由于在查找普通二叉排序树、AVL树和红黑树时，所用代码是相同的，并且在最坏情况下，AVL树的深度最小，因此在那些以查找操作为主的应用程序中，在最坏情况下，AVL树都能获得最好的时间复杂性。
3）红黑树的插入
首先使用二叉排序树的插入算法将一个结点插入到红黑树中，该结点将作为新的叶子结点插入到红黑树中某一外部结点位置。在插入过程中需要为新结点设置颜色。
若插入前红黑树为空树，则新插入的结点将成为根节点，根据性质1，根节点必须设为黑色。
若插入前红黑树不为空树，且新插入的结点被设为黑色，将违反红黑树的性质3，所以从根节点到外部结点的路径上的黑色结点个数不等。因此，==新插入的结点必须设为红色==，但这又可能违反红黑树的性质2，出现连续两个红色结点，故需要重新平衡。
若将新结点标为红色，则与性质2发生了冲突，此时红黑树变为不平衡。
通过检查新结点u、它的父节点pu以及u的祖父结点gu，可对不平衡的种类进行划分。
由于违反了性质2，出现了两个连续的红色结点，其中一个红色结点为u，另一个比为其父节点。
由于pu是红色，所以它不可能是根节点（性质1）
u必有一个祖父结点gu，而且必是黑色（性质2）。
红黑树的不平衡类型共有8种：
LLr型：pu是gu的左孩子，u是pu的左孩子，gu的另一个孩子为红色。
LRr型：pu是gu的左孩子，u是pu的右孩子，gu的另一个孩子为红色。
RRr型：pu是gu的右孩子，u是pu的右孩子，gu的另一个孩子为红色。
RLr型：pu是gu的右孩子，u是pu的左孩子，gu的另一个孩子为红色。
LLb型：pu是gu的左孩子，u是pu的左孩子，gu的另一个孩子为黑色。
LRb型：pu是gu的左孩子，u是pu的右孩子，gu的另一个孩子为黑色。
RRb型：pu是gu的右孩子，u是pu的右孩子，gu的另一个孩子为黑色。
RLb型：pu是gu的右孩子，u是pu的左孩子，gu的另一个孩子为黑色。
以上8种不平衡类型进行平衡处理时，其中第(1)~(4)种可通过改变颜色来进行，而第(5)~(8)种需要进行一次==旋转==处理。
LLr和LRr颜色转变都需要将gu的左和右孩子的颜色从红色变为黑色。
若gu不是根节点，则需将gu的颜色从黑色变为红色
若gu是根节点，颜色不变。
旋转的原则
插入新结点后，修改局部颜色（pu父、gu祖）
根据平衡二叉树进行旋转
修改颜色（根结点、对应一个孩子）
LLr型：gu左右孩子的颜色从红色变为黑色。gu不是根节点，颜色从黑色变为红色。
LRr型
LLb型
LRb型：插入43 或 插入47
