红黑树是一种自平衡二叉查找树, 它的特点是拥有良好的最坏情况的时间复杂度: O(log n). 因此 Java 的 HashMap 使用红黑树可以一定程度上避免 hash 碰撞攻击.

二叉树

二叉树是每个节点最多只有两个分支的树, 二叉树的分支具有左右次序，不能随意颠倒。

二叉查找树

  1. 左子树上所有结点的值均小于或等于它的根结点的值
  2. 右子树上所有结点的值均大于或等于它的根结点的值
  3. 左、右子树也分别为二叉排序树

存在向链表退化的问题.

平衡二叉查找树

  1. 每个节点的左右两子树高度差都不超过 1
  2. 其每一个子树均为平衡二叉树

AVL 树

AVL 树是一种自平衡二叉查找树, 它能够保证增删查的的平均和最坏时间复杂度都是 $O(log\ n)$. 增加或者删除时需要进行一次/多次树旋转以达到重新平衡.

AVL树的重新平衡

变换只要记住两点即可(When & How):

  1. 平衡因子是它的左子树的高度减去它的右子树的高度, 平衡因子为 2/-2 时才会进行旋转.
  2. Pivot 会成为新的根节点, 其他的子树根据值域重新找坑即可.

红黑树

  1. 节点是红色或黑色。
  2. 根是黑色。
  3. 所有叶子都是黑色（叶子是 NIL 节点）。
  4. 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。
  5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

红黑树如果把红节点和父节点当成一起的话, 可以看作是 2-3-4 树. 但是红黑树更容易理解, 且自平衡的操作会简单些.

红黑树是一种“不严格”的自平衡树, 它的红节点给它带来的便利就是减少了插入和删除时的操作.

有人把红节点理解为"缓存".