红黑树

在看HashMap源码的时候，我发现当hash值相同的时候，hashMap将具有相同hash值的key存到了一个树状结构中，继续看发现是一个红黑树。那么问题来了，什么是红黑树？

红黑树的起源

网上很多介绍红黑树的文一上来都是从红黑树的五种定义开始讲的，而并没有讲为什么会有这五种定义。然后我找到了一篇文章，讲的是红黑树的起源。

https://blog.csdn.net/chen_zhang_yu/article/details/52415077

根据这篇文章来讲，红黑树起源于“2-3树”。为了简化代码，使用了将节点标红或者是标黑的技巧。

而如果把红连接放平，那么就有

所以这也就解释了：

• 红黑树的红连接都为左链接
• 没有任何一个结点同时和两条红链接相连。
• 该树是完美黑色平衡的，即任意空链接到根结点的路径上的黑链接数量相同。
• 如果一个节点是红色的，则它的子节点必须是黑色的。

红黑树的基本操作

旋转

红黑树的基本操作是添加、删除。在对红黑树进行添加或删除之后，这时候这棵树就不是红黑树了，所以需要用旋转来让这棵树重新变成一颗红黑树。

对x进行左旋，意味着将x变成一个左节点。右旋同理（将x变成一个右节点）

添加

将一个数据添加到红黑树中，需要经历以下几个步骤：

• 将节点插入
• 将插入的节点着色（红色）
  首先，红黑树有以下五种特点：
  （1）每个节点或者是黑色，或者是红色。
  （2）根节点是黑色。
  （3）每个叶子节点是黑色。（注意：这里叶子节点，是指为空的叶子节点！）
  （4）如果一个节点是红色的，则它的子节点必须是黑色的。
  （5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
  如果将插入的节点设置为红色，就不会违背（5），使得我们处理的情况变少。
• 通过一系列的旋转或着色等操作，使之重新成为一颗红黑树。

删除

将某一个节点删除，其实操作方法和插入类似，都需要查找和修正。

• 将红黑树当做一颗二叉查找树，将节点删除
  在这里分为三种情况
  （1）被删除的节点没有子节点，那么可以直接删除
  （2）被删除的节点只有一个子节点，那么删除这个节点，然后用子节点去顶替他的位置
  （3）被删除的节点有两个子节点，那么，先找出它的后继节点；然后把“它的后继节点的内容”复制给“该节点的内容”；之后，删除“它的后继节点”。在这里，后继节点相当于替身，在将后继节点的内容复制给"被删除节点"之后，再将后继节点删除。这样就巧妙的将问题转换为"删除后继节点"的情况了，然后看后继节点是否满足（1）或者是（2）。
• 通过旋转和重新着色等操作来修正这棵红黑树

参考：
红黑树的演变：
https://blog.csdn.net/chen_zhang_yu/article/details/52415077
红黑树：
https://www.cnblogs.com/skywang12345/p/3245399.html