红黑树(Red-Block Tree)是一种近似平衡的二叉树,因此拥有较高的查询效率,但正因为是一棵近平衡树,因此在插入或删除节点时,会结构调整(变色,左旋,右旋),使其接近平衡,从而降低效率.
本文以TreeMap为例说明,TreeMap用红黑树构建,所以查询性能较高,时间复杂度为O(lgn),而HashMap和LinkHashMap的时间复杂度都为O(n),显然查询时比TreeMap耗时,关于时间复杂度分析,可移步到:[时间复杂度分析 理解](https://blog.csdn.net/weixin_40533111/article/details/83027707)
**重点:**红黑树拥有3特征,6种行为,行为的存在使得树在结构调整时,让树符合三种特征.这就是红黑树左旋,右旋,变色,原理,至于怎么设定的,就是发明者 Rudolf Bayer 的厉害的地方了.
特征:1.根节点必须是黑色
2.红色节点不能连续(即红节点的父子节点都得是黑色)
3.对于每个节点,从该节点到树末梢(为null的节点),都有相同数量的黑色节点.
推导结论:一个节点到末端的最长路径不大于最小路径的2倍.
行为(就是源码(本文jdk1.8)的实现方式,6种情况):看下文结构调整.
红黑树样子:
正文:
get():
get(key)通过key查找,内部调getEntry(key),TreeMap每一个节点是一个Entry,有如下属性,可以像钩子一样构成一棵树.
static final class Entry<K, V> implements java.util.Map.Entry<K,V{ K key; V value; TreeMap.Entry<K, V> left; TreeMap.Entry<K, V> right; TreeMap.Entry<K, V> parent; boolean color = true; }