红黑树真的没你想的那么难

来自：我就是马云飞（微信号：coding_ma）虽然标题是关于红黑树的，不过此文是通过分析treemap的源码加上图形结合来分析的，让你理解起来不是那么枯燥。（前方高能，此文图片众多，慎入。）概述 TreeMap是红黑树的java实现，红黑树能保证增、删、查等基本操作的时间复杂度为O(lgN)。    首先我们来看一张TreeMap的继承体系图：image还是比较直观的，这里来简单说一下继承体系中不常见的接口NavigableMap和SortedMap，这两个接口见名知意。先说NavigableMap接口，NavigableMap接口声明了一些列具有导航功能的方法，比如：/** * 返回红黑树中最小键所对应的 Entry */Map.Entry firstEntry();/** * 返回最大的键 maxKey，且 maxKey 仅小于参数 key */K lowerKey(K key);/** * 返回最小的键 minKey， ………………………………