1.平衡与非平衡树
树的平衡树的平衡指的是：树中每个节点的左边后代的数目，应该和其右边后代的数目大致相等。对于随机数构成的二叉树，一般来说是大致平衡的，但是对于有序的数据，二叉树就严重不平衡了，极端情况下，退化成为链表，其时间复杂度下降到 O(N)，而不再是平衡树的O(logN)。
2.红黑树是什么以及特征
红黑树（R-B Tree）是什么红黑树是一种增加了某些特性的二叉搜索树，它可以保持树的大致平衡。
大致思路是：在插入和删除节点的时候，检查是否破坏了树的一定的特
征，如果破坏了，就需要进行纠正，从而保持树的平衡。
红黑树的特征 ：
1）节点都有颜色
2）在插入和删除过程中，要遵循保持这些颜色的不同排列的规则
3.红黑树的规则和修正手段
红黑树的规则（也称红黑规则）：
- 1）每个节点不是红色就是黑色
- 2）根总是黑色
- 3）如果节点是红色的，那么它的子节点必须是黑色的（反之不必为真）
- 4）每个空子节点都是黑的
这里的空子节点指的是：对非叶子节点而言，本可能有，但实际没有的那个子节点。比如一个节点只有右子节点，那么它空缺的左子节点就是空子节点。 - 5）从根到叶节点或“空子节点”的每条路径，必须包含相同数目的黑色节点（这些黑色节点的数目也称黑色高度）
红黑树的修正手段 ：
- 1）改变节点颜色
- 2）执行旋转操作
4.红黑树的旋转
5.红黑树的节点插入算法，并代码示例
红黑树的插入，前面跟二叉树插入一样，就是从根节点向下查找节点要插入的位置，然后插入节点；插入节点过后，后面添加了这样的操作：检查树是否平衡，如果不平衡，就要做修复，使树重新变得平衡。
插入新的节点，通常会设置这个节点为红色，因为这样违反红黑规则的几
率较小，插入节点后，有以下几种情况：
- 1）如果插入的是根节点，那么违反规则2，就直接把节点修改为黑色
- 2）如果插入节点的父节点是黑色的，说明符合规则，什么都不做
- 3）如果插入节点的父节点是红色的，且祖父结点的另一个子节点（叔叔节点）也是红色的
那么：将祖父节点变红，而父和叔节点变黑，然后设置祖父节点为当前节点，然后重新开始判断。 - 4）如果插入节点的父节点是红色，而叔节点是黑色，且插入节点是其父的左子节点，而父节点是祖父节点的左子节点
那么：把父节点变为黑色，祖父节点变为红色，然后对祖父节点进行右旋，然后重新开始判断。 - 5）如果插入节点的父节点是红色，而叔节点是黑色，且插入节点是其父的右子节点，而父节点是祖父节点的右子节点
那么：把父节点变为黑色，祖父节点变为红色，然后对祖父节点进行左旋，然后重新开始判断。 - 6）如果插入节点的父节点是红色，而叔节点是黑色，且插入节点是其父的右子节点，而父节点是祖父节点的左子节点
那么：把当前节点的父节点做为新的当前节点，对新的当前节点进行左旋，然后重新开始判断。 - 7）如果插入节点的父节点是红色，而叔节点是黑色，且插入节点是其父的左子节点，而父节点是祖父节点的右子节点
那么：把当前节点的父节点做为新的当前节点，对新的当前节点进行右旋，然后重新开始判断。
6.红黑树的节点删除算法，并代码示例
红黑树的节点删除在前面学习二叉树的时候，我们知道做节点删除是很复杂的，同样，在红黑树里面做节点删除，也是很复杂的，甚至比二叉树的节点删除更复杂，因为还需要保证删除节点后，进行树的平衡。因此，在实际开发中，多数情况下不用去做红黑树的节点删除，而是采用其它变通方法：比如仅仅标识这个节点被删除，并不真的删除，这样树就不用动，在进行业务处理的时候，判断一下，跳过这些节点就可以了。
红黑树的删除算法
- 1）如果删除节点是叶子节点
（1）如果删除节点是红色的，那就直接删除，不做其它操作
（2）如果删除节点是黑色的，那么就创建一个空节点来顶替删除节点，然后按照后面的调整步骤进行调整 - 2）如果删除节点有一个子节点，把后来顶替被删节点的那个节点成为顶替节点，如果删除节点为黑，而且顶替节点也为黑，那么把顶替节点当作当前节点，然后按照后面的调整步骤进行调整。
- 3）如果删除节点有两个子节点，那么，找到其中序后继节点，把这两个节点的数据交换一下，不要复制颜色，也不改变其原有的父子等关系，然后重新进行删除。由于其中序后继节点只可能是叶子节点或者只有一个子节点，因此回到前面两种情况。
删除步骤后的调整步骤，有以下几种情况：
- 1）当前节点是红
那么：直接把当前节点变成黑色，结束 - 2）当前节点是黑且是根节点
那么：什么都不用做，结束 - 3）当前节点是黑且兄弟节点为红色，当前节点为父节点的左子节点
那么：把兄弟结点变成父节点的颜色，把父节点变成红色，然后在父节点上做左旋，再重新开始判断。 - 4）当前节点是黑且兄弟节点为红色，当前节点为父节点的右子节点
那么：把兄弟结点变成父节点的颜色，把父节点变成红色，然后在父节点上做右旋，再重新开始判断。 - 5）当前节点是黑且父节点和兄弟节点都为黑色，兄弟节点的两个子节点全为黑色
那么：把兄弟节点变红，然后把父节点当成新的当前节点，再重新开始判断 - 6）当前节点是黑且兄弟节点为黑色，兄弟节点的两个子节点都是黑色，但是父节点是红色
那么：就把兄弟节点变红，父节点变黑，结束 - 7）当前节点是黑且兄弟节点为黑色，兄弟节点的左子是红色，右子是黑色，而且当前节点是父节点的左子节点
那么：把兄弟节点变红，兄弟左子节点变黑，然后对兄弟节点进行右旋，再重新开始判断 - 8）当前节点是黑且兄弟节点为黑色，兄弟节点的左子是黑色，右子是红色，而且当前节点是父节点的右子节点
那么：把兄弟节点变红，兄弟右子节点变黑，然后对兄弟节点左旋，再重新开始判断 - 9）当前节点是黑且兄弟节点为黑色，兄弟节点的右子是红色，左子的颜色任意，而且当前节点是父节点的左子节点
那么：把兄弟节点变成当前节点父节点的颜色，把当前节点父节点变黑，兄弟节点右子变黑，然后以当前节点的父节点为支点进行左旋，结束。 - 10）当前节点是黑且兄弟节点为黑色，兄弟节点的左子是红色，右子的颜色任意，而且当前节点是父节点的右子节点
那么：把兄弟节点变成当前节点父节点的颜色，把当前节点父节点变黑，兄弟节点左子变黑，然后以当前节点的父节点为支点进行右旋，结束。
7.红黑树的效率
红黑树的效率红黑树的查找、插入和删除的时间复杂度都是O(logN)，以2为底。跟二叉树是一样的，但实际上，由于红黑树在插入和删除的时候，需要保证树的平衡，所以会比二叉树慢。另外一个，红黑树的节点需要多一点额外的空间，来存储颜色信息。
8.了解其它的平衡树
AVL(发明者为：Adelson-Velskii和Landis)树是最早的一种平衡树，它要求节点左子树和右子树的高度相差不超过1。当插入和删除节点的时候，都需要重新平衡树，也就是每次操作会扫描两趟树，一次向下查找节点，一次向上平衡树。 AVL树的效率不如红黑树，也不如红黑树常用，因此了解一下即可。
