二叉查找树，支持快速插入、删除、查找操作，各个操作的时间复杂度跟树的高度成正比，理想情况下，时间复杂度是O(logn)。
二叉查找树在频繁的动态更新过程中，可能会出现树的高度远大于log2n的情况，从而导致各个操作的效率下降。极端情况下，二叉树会退化为链表，时间复杂度会退化到O(n)。
需要平衡二叉查找树，解决普通二叉查找树在频繁的插入、删除等动态更新的情况下，出现时间复杂度退化的问题。
平衡二叉查找树定义
二叉树中任意一个节点得左右子树的高度相差不能大于1。完全二叉查找树、满二叉树都是平衡二叉树。平衡二叉查找树还需要满足二叉查找树的特点。AVL树。
平衡二叉查找树中“平衡”的意思，其实就是让整棵树左右看起来比较“对称”、比较“平衡”，不要出现左子树很高、右子树很矮的情况。这样就能让整棵树的高度相对来说低一些，相应的插入、删除、查找等操作的效率高一些。
树的高度不比log2n很多。
红黑树定义
红黑树”Red-Black Tree”，简称R-B Tree。是一种不严格的平衡二叉查找树。
红黑树中的节点，一类被标记为黑色，一类被标记为红色。
- 根节点是黑色的；
- 每个叶子节点都是黑色的空节点(NIL)，叶子节点不存储数据；
主要是为了简化红黑树的代码实现。（共用一个黑色的、空的叶子节点。避免浪费存储空间。）
- 任何相邻的节点都不能同时为红色，红色节点是被黑色节点隔开的；
- 每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；
红黑树就是用红链接表示3-节点的2-3树。2-节点(包含一个元素，两条子链接)，3-节点(包含两个元素，三条链接)
红链接将两个2-节点连接起来构成一个3-节点，黑链接则是2-3树中的普通链接。
红色节点标记代表指向其的链接是红链接，黑色标记的节点就是普通的节点。红色节点可以与其父节点合并为一个3-节点。
- 红链接均为左链接（左倾红黑树）；
- 没有任何一个结点同时和两条红链接相连；
- 该树是完美黑色平衡的，任意空链接到根节点的路径上的黑链接数量相同。
将红黑树中所有的红色链接放平，那么它所有的叶子节点到根节点的距离都是相同的。如果将由红链接相连的节点合并，得到的就是一棵2-3树。
父节点指向的节点是红节点，那么就认为这两个节点其实就是2-3树里面的3节点。如果有一个黑节点连接了连个红节点，那么就认为这是一个4-节点，因为2-3树不允许4-节点，所以要将其提取出来。
所谓的旋转，对于2-3树来说节点并没有变化。因为红节点和指向它的节点本来就被认为是一个节点。
实现红黑树
在插入、删除节点的过程中，第三、第四点要求可能会被破坏。
平衡调整实际上就是要把被破坏的第三、第四点回复过来。
左旋(rotate left)围绕某个节点的左旋。逆时针
右旋(rotate right)围绕某个节点的右旋。顺时针
插入操作的平衡调整
红黑树规定，插入的节点必须是红色的。而且，二叉查找树中新插入的节点都是放在叶子节点上。
- 如果插入结点的父节点是黑色的，那什么都不用做，它仍然满足红黑树的定义。
- 如果插入的节点是根节点，那么直接改变它的颜色，把它变成黑色就可以了。
- 其他情况都会违背红黑树的定义，需要进行调整，调整的过程包含两种基础的操作：左右旋转和改变颜色。
红黑树的平衡调整过程是一个迭代的过程。把正在处理的节点叫做关注节点。关注节点会随着不停的迭代处理，而不断发生变化。最开始的关注节点就是新插入的节点。
如果关注节点是a，它的叔叔节点d是红色：
- 将关注节点a的父节点b、叔叔节点d的颜色都设置成黑色；
- 将关注节点a的祖父节点c的颜色设置成红色；
- 关注节点变成a的祖父节点c;
- 跳到情况2或者情况3。
如果关注节点是a，它的叔叔节点d是黑色，关注节点a是其父节点b的右子节点：
- 关注节点变成节点a的父节点b；
- 围绕新的关注节点b左旋；
- 跳到情况3。
如果关注节点是a，它的叔叔节点d是黑色，关注节点a是其父节点b的左子节点：
- 围绕关注节点a的祖父节点c右旋；
- 将关注节点a的父节点b、兄弟节点c的颜色互换。
- 调整结束
删除操作的平衡调整
删除操作的平衡调整分为两步，第一步是针对删除节点初步调整。初步调整只是保证整棵红黑树在一个节点删除之后，仍然满足最后一条定义的要求，每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；第二部是针对关注节点进行二次调整，让它满足红黑树的第三条定义，即不存在相邻的两个红色节点。
第一步，针对删除节点初步调整。
经过初步调整之后，为了保证满足红黑树定义的最后一条要求，有些节点会被标记成两种颜色，“红-黑”或者“黑-黑”。如果一个节点被标记为了“黑-黑”，在计算黑色节点个数的时候，要算成两个黑色节点。
如果要删除的节点是a，它只有一个子节点b：
- 删除节点a，并且把节点b替换到节点a的位置，此操作跟普通的二叉查找树的删除操作一样；
- 节点a只能是黑色，节点b只能是红色，其他情况均不符合红黑树的定义。把节点b改成黑色；
- 调整结束，不需要进行二次调整。
如果要删除的节点a有两个非空子节点，并且它的后继节点就是节点a的右子节点c：
- 如果节点a的后继节点就是右子节点c，那右子节点c肯定没有左子树。把节点a删除，并且将节点c替换到节点a的位置。此操作与二叉查找树的删除操作一样；
- 然后把节点c的颜色设置为跟节点a相同的颜色；
- 如果节点c是黑色，为了不违反红黑树的最后一条定义，给节点c的右子节点d多加一个黑色，此时节点d就成了“红-黑”或者“黑-黑”；
- 关注节点变成节点d，第二步的调整操作就会针对关注节点来做。
如果要删除的是节点a，它有两个非空子节点，并且节点a的后继节点不是右子节点：
- 找到后继节点d，并将它删除，删除后继节点d的过程参照情况1；
- 将节点a替换成后继节点d；
- 把节点d的颜色设置为跟节点a相同的颜色；
- 如果节点d是黑色，为了不违反红黑树的最后一条定义，给节点d的右子节点c多加一个黑色，此时节点c就成了“红-黑”或者“黑-黑”；
- 关注节点变成了节点c，第二步的调整操作就会针对关注节点来做。
第二步，针对关注节点进行二次调整。
经过初步调整之后，关注节点变成了“红-黑”或者“黑-黑”节点。针对关注节点的二次调整是为了让红黑树中不存在相邻的红色节点。
关注节点是a，它的兄弟节点c是红色的：
- 围绕关注节点a的父节点b左旋；
- 关注节点a的父节点b和祖父节点c交换颜色；
- 关注节点不变；
- 继续从四种情况中选择适合的规则来调整。
关注节点是a，它的兄弟节点c是黑色的，并且节点c的左右子节点d、e都是黑色的：
- 将关注节点a的兄弟节点c的颜色变成红色；
- 从关注节点a中去掉一个黑色，此时节点a就是单纯的红色或者黑色；
- 给关注节点a的父节点b添加一个黑色，此时节点b就变成了“红-黑”或者“黑-黑”；
- 关注节点从a变成其父节点b；
- 继续从四种情况中选择符合的规则来调整。
关注节点是a，它的兄弟节点c是黑色，c的左子节点d是红色，c的右子节点e是黑色：
- 围绕关注节点a的兄弟节点c右旋；
- 节点c和节点d交换颜色；
- 关注节点不变；
- 跳转到情况4，继续调整。
关注节点a的兄弟节点c是黑色的，并且c的右子节点是红色的：
- 围绕关注节点a的父节点b左旋；
- 将关注节点a的兄弟节点c的颜色，跟关注节点a的父节点b设置成相同的颜色；
- 将关注节点a的父节点b的颜色设置为黑色；
- 从关注节点a中去掉一个黑色，节点a就变成了单纯的红色或者黑色；
- 将关注节点a的叔叔节点e设置为黑色；
- 调整结束。