1 定义

红黑树也是一种平衡二叉树,和Avl树类似,它都可以动态的保持二叉树的平衡,即左右子树高度差不能太大,红黑树定义左右子树高度小于2倍。这是由于红黑树的性质得到了这些条件:

  • 节点不是红色的就是黑色的
  • 根节点是黑色的
  • 每个红色节点的两个子节点都是黑色的
  • 任意节点到其每个叶子节点包含相同的黑色节点

一棵常规的红黑树如下图所示:

2 实现