红黑树

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

二叉树

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

二叉查找树

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