参考 链接， jdk 1.8 之后 HashMap 使用了红黑树的数据结构


image.png

红黑树本质上是一棵平衡二叉树

二叉查找树

二叉查找树（Binary Search Tree）是指一棵空树或者具有下列性质的二叉树：

  1. 若任意结点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  2. 若任意结点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  3. 任意结点的左、右子树也分别为二叉查找树。
  4. 没有键值相等的结点（no duplicate nodes）。

因为，一棵由 n 个结点，随机构造的二叉查找树的高度为lgn，所以顺理成章，一般操作的执行时间为O（lgn）.（至于n个结点的二叉树高度为lgn的证明
但二叉树若退化成了一棵具有n个结点的线性链后，则此些操作最坏情况运行时间为O(n)。后面我们会看到一种基于二叉查找树-红黑树，它通过一些性质使得树相对平衡，使得最终查找、插入、删除的时间复杂度最坏情况下依然为O（lgn）。使用红黑树的目的是为了提高查询的速度。无论在任何情况下，我们查找、删除一个数的时间复杂度都是 O(lgn).

红黑树

在平衡二叉树的基础上，红黑树特点：

  1. 节点是红色或者是黑色；
  2. 根节点是黑色；
  3. 每个叶节点（NIL或空节点）是黑色
  4. 每个红色节点的两个子节点都是黑色的（也就是说不存在两个连续的红色节点）；
  5. 从任一节点到其每个叶节点的所有路径都包含相同数目的黑色节点；

通过数学证明来证明，满足这五条性质的二叉树可以将查找删除维持在对数时间内。

对树的操作：
当我们在对红黑树进行插入和删除等操作时，对树做了修改，那么可能会违背红黑树的性质。
为了继续保持红黑树的性质，我们可以通过对结点进行重新着色，以及对树进行相关的旋转操作，即修改树中某些结点的颜色及指针结构，来达到对红黑树进行插入或删除结点等操作后，继续保持它的性质或平衡。

红黑树是每个节点都带颜色的树，节点颜色或是红色或是黑色，红黑树是一种查找树。红黑树有一个重要的性质，从根节点到叶子节点的最长的路径不多于最短的路径的长度的两倍。对于红黑树，插入，删除，查找的复杂度都是O（log N）。