一、平衡二叉查找树：
1、定义：
二叉树中任意一个节点的左右子树的高度相差不能大于1。从这个定义来看，完全二叉树、满二叉树其实都是平衡二叉树，但是非完全二叉树也有可能是平衡二叉树。
二、红黑树：
1、需要满足的条件：
①、根节点是黑色的；
②、节点是红色或黑色。
③、每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
④、每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；
⑤、每个叶子节点（NIL）是黑色。 （注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！）
2、红黑树的高度近似log2n，所以它是近似平衡，插入、删除、查找操作的时间复杂度都是O(logn)。
3、红黑树的左旋、右旋：
<1>、左旋（rotate left） ：对x进行左旋，意味着"将x变成一个左节点"。
<2>、右旋（rotate right）：对y进行右旋，意味着"将x变成一个右节点"。
4、红黑树在插入、删除数据后的平衡调整：
<1>、插入操作的平衡调整：
(1)、如果插入节点的父节点是黑色的，那我们什么都不用做，它仍然满足红黑树的定义。
(2)、如果插入的节点是根节点，那我们直接改变它的颜色，把它变成黑色就可以了。
(3)、其他情况都会违背红黑树的定义，就需要进行调整，调整的过程包含两种基础的操作： 左右旋转和改变颜色。
(4)、操作：
假设父节点的兄弟节点叫作叔叔节点，父节点的父节点叫作祖父节点。
CASE 1：如果关注节点是a，它的叔叔节点d是红色，依次执行下面的操作：
①、将关注节点a的父节点b、叔叔节点d的颜色都设置成黑色；
②、将关注节点a的祖父节点c的颜色设置成红色；
③、关注节点变成a的祖父节点c；
④、跳到CASE 2或者CASE 3。
CASE 2：如果关注节点是a，它的叔叔节点d是黑色，关注节点a是其父节点b的右子节点，执行下面操作：
①、关注节点变成节点a的父节点b；
②、围绕新的关注节点b左旋；
③、跳到CASE 3。
CASE 3：如果关注节点是a，它的叔叔节点d是黑色，关注节点a是其父节点b的左子节点，执行下面的操作：
①、围绕关注节点a的祖父节点c右旋；
②、将关注节点a的父节点b、兄弟节点c的颜色互换。
③、调整结束。
<2>、删除操作的平衡调整：
(1)、针对删除节点初步调整：
红黑树的定义中“只包含红色节点和黑色节点”，经过初步调整之后，为了保证满足红黑树定义的最后一条要求（每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点），有些节点会被标记成两种颜色， “红-黑”或者“黑-黑”。如果一个节点被标记为了“黑-黑”，那在计算黑色节点个数的时候，要算成两个黑色节点。如果一个节点既可以是红色，也可以是黑色，在图中用一半红色一半黑色来表示。如果一个节点是“红-黑”或者“黑-黑”，用左上角的一个小黑点来表示额外的黑色。
CASE 1：如果要删除的节点是a，它只有一个子节点b，依次进行下面的操作：
①、删除节点a，并且把节点b替换到节点a的位置，这一部分操作跟普通的二叉查找树的删除操作一样；
②、节点a只能是黑色，节点b也只能是红色，其他情况均不符合红黑树的定义。这种情况下，我们把节点b改为黑色；
③、调整结束，不需要进行二次调整。
CASE 2：如果要删除的节点a有两个非空子节点，并且它的后继节点就是节点a的右子节点c。依次进行下面的操作：
①、如果节点a的后继节点就是右子节点c，那右子节点c肯定没有左子树。我们把节点a删除，并且将节点c替换到节点a的位置。这一部分操作跟普通的二叉查找树的删除操作无异；
②、然后把节点c的颜色设置为跟节点a相同的颜色；
③、如果节点c是黑色，为了不违反红黑树的最后一条定义，我们给节点c的右子节点d多加一个黑色，这个时候节点d就成了“红-黑”或者“黑-黑”；
④、这个时候，关注节点变成了节点d，第二步的调整操作就会针对关注节点来做。
CASE 3：如果要删除的是节点a，它有两个非空子节点，并且节点a的后继节点不是右子节点，依次进行下面的操作：
①、找到后继节点d，并将它删除，删除后继节点d的过程参照CASE 1；
②、将节点a替换成后继节点d；
③、把节点d的颜色设置为跟节点a相同的颜色；
④、如果节点d是黑色，为了不违反红黑树的最后一条定义，我们给节点d的右子节点c多加一个黑色，这个时候节点c就成了“红-黑”或者“黑-黑”；
⑤、这个时候，关注节点变成了节点c，第二步的调整操作就会针对关注节点来做。
(2)、针对关注节点进行二次调整：
经过初步调整之后，关注节点变成了“红-黑”或者“黑-黑”节点。针对这个关注节点，再分四种情况来进行二次调整。二次调整是为了让红黑树中不存在相邻的红色节点。
CASE 1：如果关注节点是a，它的兄弟节点c是红色的，依次进行下面的操作：
①、围绕关注节点a的父节点b左旋；
②、关注节点a的父节点b和祖父节点c交换颜色；
③、关注节点不变；
④、继续从四种情况中选择适合的规则来调整。
CASE 2：如果关注节点是a，它的兄弟节点c是黑色的，并且节点c的左右子节点d、 e都是黑色的，依次进行下面的操作：
①、将关注节点a的兄弟节点c的颜色变成红色；
②、从关注节点a中去掉一个黑色，这个时候节点a就是单纯的红色或者黑色；
③、给关注节点a的父节点b添加一个黑色，这个时候节点b就变成了“红-黑”或者“黑-黑”；
④、关注节点从a变成其父节点b；
⑤、继续从四种情况中选择符合的规则来调整。
CASE 3：如果关注节点是a，它的兄弟节点c是黑色， c的左子节点d是红色， c的右子节点e是黑色，依次进行下面的操作：
①、围绕关注节点a的兄弟节点c右旋；
②、节点c和节点d交换颜色；
③、关注节点不变；
④、跳转到CASE 4，继续调整。
CASE 4：如果关注节点a的兄弟节点c是黑色的，并且c的右子节点是红色的，依次进行下面的操作：
①、围绕关注节点a的父节点b左旋；
②、将关注节点a的兄弟节点c的颜色，跟关注节点a的父节点b设置成相同的颜色；
③、将关注节点a的父节点b的颜色设置为黑色；
④、从关注节点a中去掉一个黑色，节点a就变成了单纯的红色或者黑色；
⑤、将关注节点a的叔叔节点e设置为黑色；
⑥、调整结束。
