红黑树

红黑树更多定义：
https://baike.baidu.com/item/%E7%BA%A2%E9%BB%91%E6%A0%91/2413209?fr=aladdin
数据结构学习网址：
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

为什么出现红黑树？

AVL树是严格的平衡二叉树，平衡条件必须满足（所有节点的左右子树高度差的绝对值不超过1）。不管我们是执行插入还是删除操作，只要不满足上面的条件，就要通过旋转来保持平衡，而旋转是非常耗时的，由此我们可以知道AVL树适合用于插入与删除次数比较少，但查找多的情况。

鉴于上述的局限性，更多的地方是用追求局部而不是非常严格整体平衡的红黑树。

什么是红黑树？

红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。
红黑树是一种特化的AVL树（平衡二叉树），都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。
它的左右子树高差有可能大于 1，所以红黑树不是严格意义上的平衡二叉树（AVL），但对之进行平衡的代价较低， 其平均统计性能要强于 AVL 。

红黑树的特征

性质1. 节点是红色或黑色。

性质2. 根节点是黑色。

性质3.所有叶子都是黑色。（叶子是NULL节点，如下图中的NULL LEAF）

叶子

性质4. 每个红色节点的两个子节点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色节点）

性质5.. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

红黑树

因为红黑树是一种特化的二叉查找树，所以红黑树上的只读操行与普通二叉查找树相同。

应用场景

java8中的TreeMap和HashMap。