TreeMap 工作原理及实现

HashMap不保证数据有序
LinkedHashMap保证数据插入有序，
要保证map的key可以大小排序，使用TreeMap集合

 TreeMap<Integer, String> treeMap = new TreeMap<>();
        treeMap.put(4,"qd");
        treeMap.put(3,"sd");
        treeMap.put(1,"sd");
        treeMap.put(5,"sd");
        treeMap.put(7,"sd");
        treeMap.put(9,"sd");
        treeMap.put(0,"sd");
        for(Map.Entry<Integer,String> entry: treeMap.entrySet()){
            System.out.println(entry.getKey()+" "+entry.getValue());

        }

…

key是按照大小排序，
treeMap 能够按照key大小排序
key不能为null，key不能重复
如何做到数据有序的呢？红黑树
红黑树

红黑树(Red-Black Tree)首先是一颗二叉树,**二叉树的特征是树中的任何节点的值大于他的左孩子节点、**且小于它的右孩子节点，提高检索效率
二叉树在生成过程中容易失衡，导致检索效率降低

平衡二叉树：是一颗空树或左右子树的高度差的绝对值不超过1，并且左右孩子都是一颗平衡二叉树，

红黑树是一种平衡的二叉树，要保证数据的平衡，二叉树是要满足以下特点：
1、每个节点都只能是红色或者黑色
2、根节点必须是黑色
3、每个叶子节点是黑色的
4、如果一个节点是红色的，则它的子节点都是黑色的，一条路径上不能出现相邻的两个红色节点
5、从任意一个节点到其叶子节点包含相同数目的黑色节点

插入后者删除数据，红黑树就发生了变换，调整无非左旋、右旋、或者着色

复杂难点在于旋转和着色的过程

treemap提供的api

求助：不会用treeMap的自然排序？