在阅读HashMap和TreeMap的源码时,都涉及到了红黑树的知识,所有有必要先学习红黑树。
红黑树的五个特性:
1.每个节点要么是红色,要么是黑色;
2.根节点是黑色;
3.每个叶节点(叶节点是指树尾端的Null节点)是黑色;
4.如果一个节点是红色,那么它的俩儿子都是黑色;
5.对于任一节点而言,其到叶节点(Null节点)的每一条路径都包含相同数目的黑节点。

当红黑树插入数据时,先把数据插到合适位置,再通过插入后修正(左旋,右旋,重新着色),使得新的树也成为红黑树。
删除数据时同理,先把数据删除,然后通过删除后修正(左旋,右旋,重新着色),使得新的树成为红黑树。

这里只是简单了解红黑树,具体的原理和操作,参考下面的链接
红黑树(一)之 原理和算法详细介绍
教你透彻了解红黑树-github