平衡属性：任意节点左右子树高度相差不大于1。

不具有严格的平衡属性，到是平均的使用性能非常良好。

红黑树5个性质：

  • 所有节点非红即黑
  • 根节点是黑色
  • 叶节点是黑色且不保存数据(叶子是NIL节点)
  • 每个红色节点必须有两个黑色的子节点
  • 任意节点到叶子节点路径中有相同数量的黑色节点

在红黑树中没有一条路径比其他路径长出2倍
红黑树树的高度稳定趋近于，在树上的任何操作，时间复杂度也就是
一颗具有n个节点的红黑树，树的高度最多是

怎么保持平衡：

左旋：围绕某个节点向左旋转,也就是逆时针旋转某个点。
右旋：围绕某个节点向右旋转,也就是顺时针旋转某个点。
变色：为满足第四条。

为什么假定插入的点是红色点？

不管新节点是什么颜色，特性3都不可能被破坏，特性1、2、4都有可能被破坏。如果插入的节点是黑色，则一定会破坏特性5，需要进行调整，如果插入的节点是红色，则一定不会破坏特性5。所以将新节点设置为红色，可以降低破坏红黑树特性的可能性。