TreeMap

红黑树是一种近似平衡的二叉查找树，它能够确保任何一个节点的左右子树的高度差不会超过二者中较低那个的一陪。具体来说，红黑树是满足如下条件的二叉查找树（binary search tree）：

• 每个节点要么是红色，要么是黑色。
• 根节点必须是黑色
• 红色节点不能连续（也即是，红色节点的孩子和父亲都不能是红色）。
• 对于每个节点，从该点至 null（树尾端）的任何路径，都含有相同个数的黑色节点。
• 在树的结构发生改变时（插入或者删除操作），往往会破坏上述条件 3 或条件 4，需要通过调整使得查找树重新满足红黑树的条件。

TreeMap 的底层使用了红黑树来实现，像 TreeMap 对象中放入一个 key-value 键值对时，就会生成一个 Entry 对象，这个对象就是红黑树的一个节点，其实这个和 HashMap 是一样的，一个 Entry 对象作为一个节点，只是这些节点存放的方式不同。存放每一个 Entry 对象时都会按照 key 键的大小按照二叉树的规范进行存放，所以 TreeMap 中的数据是按照 key 从小到大排序的。

添加数据

程序添加新节点时，总是从树的根节点开始比较，即将根节点当成当前节点。如果新增节点大于当前节点并且当前节点的右节点存在，则以右节点作为当前节点，如果新增节点小于当前节点并且当前节点的左子节点存在，则以左子节点作为当前节点；如果新增节点等于当前节点，则用新增节点覆盖当前节点，并结束循环 直到某个节点的左右子节点不存在，将新节点添加为该节点的子节点。如果新节点比该节点大，则添加其为右子节点。如果新节点比该节点小，则添加其为左子节点