红黑树

  红黑树（自平衡的二叉查找树）底层数据结构为（特殊的二叉树）二分查找树，避免二叉树退化为链表而诞生

  什么是“二叉树退化”？如下图：

  大家知道二叉搜索树的的深度即为时间复杂度，即同为3元素，左侧时间复杂度为2，右侧时间复杂度为3，可见数据结构对查询效率的影响，这也就是所谓的“二叉树退化”。

  其实没有什么数据结构是一诞生就是完美的，回顾红黑树的演化史：
链表->二叉树->二叉查找树->特殊的二叉查找树(自平衡二叉树)

  数据结构演化史体现在代码中，就像hashmap的底层，最开始为jdk1.7之前为数组+链表，1.8及以后为数组+链表+红黑树

红黑树的性质:

  1.每个节点或者是黑色，或者是红色。

  2.根节点（root）是黑色。

  3.不可能有连在一起的红色节点，即如果一个节点是红色的，则它的子节点必须是黑色的

  4.每个红色节点的两个子节点都是黑色

补充

1.如何判断一个节点是否为根节点：没有父节点的节点

2.红黑树与avl平衡二叉树

  红黑树出现的原因，因为avl树要求太苛刻，要一直旋转来达到平衡，而红黑树仅要求黑色平衡即可，可减少平衡所需的旋转次数

3.黑色平衡：即某一个节点到他的叶子节点之间，黑色节点数一样

4.2-3-4树

  红黑树的本质，诞生于2-3-4树

  一个红黑树对应一个2-3-4树，而一个2-3-4树对应多个红黑树，因为3节点有左倾和右倾。