在数据结构中我们常见的平衡二叉树有AVL树和红黑树。

　　红黑树和AVL树的区别在于它使用颜色来标识结点的高度，它所追求的是局部平衡而不是AVL树中的非常严格的平衡。

　　我们来看红黑树的定义：红黑树首先是一棵二叉查找树，它每个结点都被标上了颜色（红色或黑色），红黑树满足以下5个性质：

　　1、 每个结点的颜色只能是红色或黑色。

　　2、 根结点是黑色的。

　　3、 每个叶子结点都带有两个空的黑色结点（被称为黑哨兵），如果一个结点n的只有一个左孩子，那么n的右孩子是一个黑哨兵；如果结点n只有一个右孩子，那么n的左孩子是一个黑哨兵。

　　4、 如果一个结点是红的，则它的两个儿子都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。

　　5、 对于每个结点来说，从该结点到其子孙叶结点的所有路径上包含相同数目的黑结点。

　　如图（图片来源于网络）

　　具体操作下次更新

红黑树