导航菜单
路很长,又很短
博主信息
昵   称:Cocodroid ->关于我
Q     Q:2531075716
博文数:306
阅读量:737494
访问量:68091
至今:
×
云标签 标签球>>
云标签 - Su的技术博客
Tags : 红黑树发表时间: 2019-04-02 23:59:49

本文以Java TreeMap为例,从源代码层面,结合详细的图解,剥茧抽丝地讲解红黑树(Red-Black tree)的插入,删除以及由此产生的调整过程。

总体介绍

Java TreeMap实现了SortedMap接口,也就是说会按照key的大小顺序对Map中的元素进行排序,key大小的评判可以通过其本身的自然顺序(natural ordering),也可以通过构造时传入的比较器(Comparator)。

TreeMap底层通过红黑树(Red-Black tree)实现,也就意味着containsKey()get()put()remove()都有着log(n)的时间复杂度。其具体算法实现参照了《算法导论》。

...阅读原文