从手写个红黑树说起 TreeMap
去做你害怕的事,去见你害怕的人,这就是成长。
——《末那大叔》
前排提醒,本文高能,红黑树主场,若有心理承受能力较差同学,请自觉提高认知~
自打上次面试效果表现较为吸睛,大Q 也开始了对小a的狂追不舍,每天都在问候他的学习进度,这让小a有点怪异的感觉,这不他俩又聚首开始了新一轮模拟面试...
牛客网视频连线中...
Q:你了解TreeMap吗?
话不多说,没有比类注释更科学权威地能用来介绍一个组件了.
如果要正确地实现Map接口，TreeMap所维护的顺序就像任何有序Map一样
- 无论是否显式地提供了一个比较器
都必须与 equals 方法协作。
之所以如此，是因为Map接口是根据 equals 操作来定义的，但有序map使用其compareTo（或compare）方法来执行所有的键比较，因此，从有序map的角度来看，两个被该方法认为相等的键是相等的。即使排序的map的排序与 equals 不一致，有序map的行为也是很好定义的；它只是没有服从Map接口的一般契约。
注意，这种实现是非同步的。如果多个线程并发访问一个map，并且其中至少有一个线程在结构上修改了map，那么必须对其进行外部同步。这通常是通过在一些自然封装了map的对象上进行同步来实现的。如果不存在这样的对象，应该使用Collections.synchronizedSortedMap方法来 "封装 "该map。这最好是在创建时进行，以防止意外的非同步访问map。
SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...))
支持快速失败机制.
这个类中的方法和它的视图返回的所有 Map.Entry 对都代表了产生map时的快照。它们不支持 Entry.setValue 方法。(但是请注意，可以使用put来改变关联的映射中的映射。)
这个类是Java集合框架中的一个成员。
Q:你了解 TreeMap 底层数据结构吗?
可以看到是一个红黑树结构.
Q:讲讲红黑树?(看你小子今天还不栽了)
淡然一笑,好歹我也是花了好几天时间认真研究了红黑树,不然今天就真的凉透了
红黑树的优点
红黑树也叫红-黑二叉树，首先它是一颗排序二叉树。但红黑树是一颗自平衡的排序二叉树。在数据结构课上我们学过在生成排序二叉树的过程是非常容易失衡的，最坏的情况就是一边倒（只有右/左子树,退化成链表），这就导致二叉树的搜索效率降低为O(n),红黑树和AVL树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保,红黑树相对于AVL树来说，牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树,因此 TreeMap 的设计也就基于红黑树实现的.
红黑树的性质
红黑树是每个节点都带有颜色属性的排序二叉树，颜色为红色或黑色。除排序二叉树的一般要求，红黑树增加了如下要求：
- 节点是红色或黑色
- 根是黑色
- 所有叶节点都是黑色（叶子是NIL节点）
- 每个红色节点必须有两个黑色的子节点（从每个叶子到根的所有路径上不能有两个连续的红色节点）
此性质直接导致路径不可能有两个毗连的红色节点 - 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点
最短可能路径:都是黑色节点
最长可能路径:交替的红/黑色节点
根据本条性质,所有最长路径都有相同数目的黑色节点，这就保证了红黑树的关键特性.
- 红黑树的关键特性
从根到叶的最长可能路径长不多于最短可能路径的两倍。表现就是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的排序二叉树. - 红黑树示例
因为每一个红黑树也是一个排序二叉树，因此红黑树上的只读操作与普通排序二叉树上的只读操作相同。然而，在红黑树上进行插入操作和删除操作会导致不再符合红黑树的性质。恢复红黑树的性质需要 O(log n) 的颜色变更（实际非常快）和不超过三次树旋转（对于插入操作是两次）。虽然插入和删除很复杂，但操作时间仍可以保持为 O(log n).
Q:看来对数据结构也比较熟悉,那你说说 TreeMap 添加元素过程吧?
> 看来今天是真想把我问倒(:з」∠),可惜我都会.
这就得看看Map 接口的优良传统方法 put 了
突然看源码估计看不懂.不急,喝口红牛,我们先看图
首先庖丁解牛,类似于如何把大象装入冰箱,分三步走:
- 以排序二叉树的方式新增节点
因为红黑树首先本身就是一个排序二叉树 - 标记它为红***r /> 如果设为黑色，就会导致根到叶的路径上有一条路上，多一个额外的黑节点，打破性质 5,这个很难调整
但设为红色节点后，可能会导致出现两个连续红色节点的冲突，那么可以通过 - 颜色调换（color flips）和树旋转
调整
之后再要进行什么操作就取决于其他临近节点的颜色
注意到:
- 性质1/2/3总是保持
- 性质4只在增加红色节点、重绘黑色节点为红色，或做旋转时受到威胁
- 性质5只在增加黑色节点、重绘红色节点为黑色，或做旋转时受到威胁
在下面的示意图中，
- 要插入的节点标为N
- N的父节点标为P
- N的祖节点标为G
- N的叔节点标为U
图中展示的任何颜色要么是由它所处情形这些所作的假定，要么就是由假定所自然推出的
插入情境分类
1 N 位于树的根,即无父节点
直接将新插入节点设置为根即可.
这种情形下，把它绘为黑色 - 满足性质2
它在每个路径上对黑节点数目加一 - 满足性质5
2 P 是黑色
直接将N插入即可，不会破坏性质4(N 是红色的).
在这种情形下,性质5未受到威胁，尽管N有两个黑色叶子子节点；但由于N是红色，通过它的每个子节点的路径就都有同通过它所取代的黑色的叶子的路径同样数目的黑色节点，所以依然满足这个性质。
> 在下面情境下,假定P为红色，所以它有祖节点G.
> 因为若P是根，则P就应是黑色。所以N总有一个叔节点，尽管在情形4和5下它可能是叶节点
这种情况下会破坏性质 4,所以又分为如下几种情境:
3 P 和 U 都是红色
此时N做为P的左孩子或右孩子都属于本情境.
- 这里仅图解N做为P左孩子的情境
将G设为红色，P和U设为黑色 - 以保持性质5.
现在N有了一个黑色的父节点P。因为通过父节点P或叔节点U的任何路径都必定通过祖节点G，在这些路径上的黑节点数目没有改变.
But!
- 红色的祖节点G可能是根,破坏性质2
- 也可能祖节点G的父节点是红色的，破坏性质4
为了解决这个问题，在祖节点G递归进行情境1.
> 以下情境，假定P是G的左子节点
4 P是红色,U是黑色或缺少,N是P的右孩子
左旋P,调换 N 和 P 的角色
这个改变会导致某些路径通过它们以前不通过的N（比如图中的1号叶节点）或不通过P（比如图中3号叶节点），但由于这两个节点都是红色，性质5仍有效
但P和N还是连续的两个红色节点，破坏性质 4还，怎么办?看情境5
5 P是红色,U是黑色或缺少，N是P的左子节点
操作前G是黑色，否则P不可能是红色(如果P和G都是红色就破坏了性质4)
右旋G，将P设为黑色，G设为红色，达到平衡.此时P是黑色，不用担心P的父节点是红色.
图解完毕,我们来看源码吧!
public V put(K key, V value) {
// 根节点
Entry<K,V> t = root;
// 若根为空
if (t == null) {
compare(key, key); // 类型校验(可能是 null)
// 创建一个根
root = new Entry<>(key, value, null);
// 有一个根元素了
size = 1;
// 修改计数器勿忘加一
modCount++;
// 返回
return null;
}
// 记录比较结果
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
// 当前使用的比较器
Comparator<? super K> cpr = comparator;
// 若比较器字段非空，直接使用指定的比较器
if (cpr != null) {
// 循环查找key要插入的位置(也就是新节点的父节点)
do {
// 记录上次循环的节点t
parent = t;
// 比较当前节点key和新插入节点key的大小
cmp = cpr.compare(key, t.key);
// 新key小，以当前节点的左孩子节点为新的比较节点
if (cmp < 0)
t = t.left;
// 新key大，则以当前节点的右孩子节点为新的比较节点
else if (cmp > 0)
t = t.right;
else
// 当前节点key和新key相等，则覆盖value并返回
return t.setValue(value);
// 当
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
<p> “挨踢”业行情日益严峻，企业招聘门槛愈来愈高，大厂hc更是少之又少,而Java技术面试普遍对基础知识的掌握考察特别深，大多数同学突击所看的 Java 面试基础知识点根本达不到面试官近乎挑剔的要求。 本专刊针对如今的校招及社招痛点，深入解析 JDK 的核心源码，探究 JDK 的设计精髓及最佳实践，同时以模拟面试的场景切入，让同学们在阅读过程中也能轻松掌握面试技巧。 本专刊购买后即可解锁所有章节，故不可以退换哦~ </p>
查看7道真题和解析