1 什么是平衡二叉树
平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
常用的平衡二叉树有：AVL树，红黑树。
2 为什么需要平衡二叉树
假设二叉搜索树树所有节点都是右节点，则二叉树变为链表，此时，二叉搜索树查找时间复杂度变为O(n)。则二叉平衡树的时间复杂度有原先的O(logn)下降为O(n)。
3 如何保证是平衡树
下面以红黑树为例，说明红黑树如何保证其实二叉平衡树。
红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组（键值对）。红黑树它可以在O(log n)时间内做查找，插入和删除，这里的n是树中元素的数目。
红黑树是每个节点都带有颜色属性的二叉查找树，颜色为红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树增加了如下的额外要求:
性质1. 节点是红色或黑色。Every node is either red or black.
性质2. 根是黑色。The root is always black.
性质3. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
If a node is red, its children must be black(although the convert isn't necessarily true).
性质4. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
Every path from the root to a leaf, or to a null child, must contain the same number of black nodes.
为什么上述性质，可以保证红黑树是平衡二叉树？因为这些性质强制了红黑树的关键性质:
1）性质3确保红黑树没有一条路径会比其他路径长出俩倍。
注意到属性3导致了路径不能有两个毗连的红色节点。最短的可能路径都是黑色节点，最长的可能路径有交替的红色和黑色节点。因为根据属性4所有最长的路径都有相同数目的黑色节点，这就表明了没有路径能多于任何其他路径的两倍长。
假如有一棵高度为 3 的红黑树：从根节点到叶节点的最短路径长度是 2，该路径上全是黑色节点（黑节点 - 黑节点 - 黑节点）。最长路径也只可能为 4，在每个黑色节点之间插入一个红色节点（黑节点 - 红节点 - 黑节点 - 红节点 - 黑节点）。
2）性质 4 保证绝不可能插入更多的红色节点。
由此可见，红黑树中最长路径就是一条红黑交替的路径。因而是接近平衡的，保证了最坏情况下的时间复杂度也是O(log n)。这不只是使它们在时间敏感的应用如实时应用(real time application)中有价值，而且使它们有在提供最坏情况担保的其他数据结构中作为建造板块的价值；例如，在计算几何中使用的很多数据结构都可以基于红黑树。
4 如何实现红黑树
在插入元素时进行颜色翻转和旋转；删除元素比较复杂，如果删除操作不是经常发生，可以只是将要删除的元素标记为删除，并不真正删除它。
插入操作：首先以二叉查找树的方法增加节点并标记它为红色。（如果设为黑色，就会导致根到叶子的路径上有一条路上，多一个额外的黑节点，这个是很难调整的。但是设为红色节点后，可能会导致出现两个连续红色节点的冲突，那么可以通过颜色调换（color flips）和树旋转来调整。叔父节点指一个节点的父节点的兄弟节点。
具体实现见维基百科红黑树。