一、红黑树与普通的平衡二叉树的区别

1、平衡二叉树通过保持任一节点左、右子树高度差的绝对值不超过1来维持二叉树的平衡；而红黑树是根据查找路径上黑色节点的个数以及红、黑节点之间的联系来维持二叉树的平衡。

2、平衡二叉树在插入或者删除节点时为了保证左右子树的高度差会进行旋转，这一个旋转根据数据的不同旋转的复杂度也会不一样，所以在插入或者删除平衡二叉树的节点时，旋转的次数不可知，这也导致在频繁的插入、修改中造成的效率问题；红黑树在执行插入修改的操作时会发生旋转与变色（红变黑，或者黑变红）以确保没有一条路径会比其它路径长出两倍。

3、总体来说，在插入或者删除节点时，红黑树旋转的次数比平衡二叉树少，因此在插入与删除操作比较频繁的情况下，选用红黑树。

什么样的数据结构称为红黑树

红黑树（Red Black Tree）是一种自平衡的二叉查找树，它与平衡二叉树相同的地方在于都是为了维护查找树的平衡而构建的数据结构，它的主要特征是在二叉查找树的每个节点上添加了一个属性表示颜色，颜色有两种，红与黑。

性质：

每个节点是红色或者黑色；

根节点是黑色；

所有叶子节点都是黑色（叶子是NIL节点，也称为外节点）;

每个红色节点的子节点都是黑色（从每个叶子节点到根节点的所有路径上不能有两个连续的红色节点）；

从红黑树的任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点（包含黑色节点的数目称为该节点的黑高度）。

延伸阅读：

二、什么是平衡二叉树

平衡二叉树（Balanced Binary Tree）的定义是这样的——空树，或者任一节点左、右子树高度差的绝对值不超过1，称为平衡二叉树。

比如，我们将1,2,3,4,5,6,7,8这几个节点以5,3,1,4,2,7,6,8的顺序插入构造查找二叉树，这棵树就是一个平衡二叉树，它的根节点高度为3，平均查找长度为(1*1+ 2*2 + 4*3 + 1*4)/8 = 2.625,，并且它的任一节点左、右子树高度差的绝对值不超过1。而如果按照6,4,3,5,2,1,7,8的顺序插入构造查找二叉树，这棵树也不能称为平衡二叉树，因为它的根节点的左子树高度为4，而右子树的高度为2，相差大于1；而对于4这一个节点，它的左子树高度为3，右子树的高度为1，相差也大于1。而这棵树的平均查找长度为（1*1 + 2*2 + 3*3 + 4*1 + 5*1）/ 8 = 2.875（这里数据量较小，看不出与平衡二叉树的明显差别）。

上一篇

HalfEdge数据结构有什么优点?

下一篇

MySQL索引为什么要选择B+树这种数据结构?