java Collection-Map 之 TreeMap

TreeMap 内部定义了一个类  static final class Entry<K,V> implements Map.Entry<K,V>,(自平衡红黑二叉树)作为数据存储节点。

put方法先判断根节点是否为空,为空则在跟节点放置数据。

不为空,(调用比较器)将put的key循环比较parent节点的key,并动态修改parent的指向。最终存入数据。

然后fixAfterInsertion 自平衡调整,过程务必会涉及到红黑树的左旋、右旋、着色三个基本操作

红黑树的5点规定

1、每个节点都只能是红色或者黑色

2、根节点是黑色

3、每个叶节点(NIL节点,空节点)是黑色的。

4、如果一个结点是红的,则它两个子节点都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。

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

原文地址:https://www.cnblogs.com/clds/p/5434044.html