前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Java中 Treemap和 Treeset的使用

Java中 Treemap和 Treeset的使用

作者头像
呼延十
发布2019-07-01 17:17:32
1.3K0
发布2019-07-01 17:17:32
举报
文章被收录于专栏:呼延

前言

首先要注意的是,本文章不涉及到红黑树的具体实现,也就是说不会逐行分析TreeMapTreeSet的源码实现,因为红黑树看了也会忘的…

所以本文只是记录红黑树的一些基础介绍,以及TreeMapTreeSet两个类的公共API.


红黑树

红黑树,一种二叉查找树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。

红黑树首先是一颗二叉查找树,满足二叉查找树的一下特点:

  1. 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
  2. 若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值;
  3. 任意节点的左、右子树也分别为二叉查找树;
  4. 没有键值相等的节点。

红黑树在二叉查找树的基础上又有以下性质:

  1. 每个结点要么是红的要么是黑的。
  2. 根结点是黑的。
  3. 每个叶结点(叶结点即指树尾端NIL指针或NULL结点)都是黑的。
  4. 如果一个结点是红的,那么它的两个儿子都是黑的。
  5. 对于任意结点而言,其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。

通过这5个性质,可以保证红黑树的高度永远是logn,所以红黑树的查找、插入、删除的时间复杂度最坏为O(log n).

红黑树有什么作用呢?那就是快,查找,插入,删除的时间复杂度最坏为O(logn).

红黑树的具体实现可以google一下,有很多开源的实现.中心思想就是各种旋转~.

TreeMap

TreeMap是一个有序的key-value集合,基于红黑树(Red-Black tree)实现。该映射根据其键的自然顺序进行排序,或者根据创建映射时提供的 Comparator 进行排序,具体取决于使用的构造方法。

具体的使用方法见下方API极其注释(常用的没有注释).

代码语言:javascript
复制
// 返回(大于等输入key)的最小的key/entry,不存在返回null
Entry<K, V>                ceilingEntry(K key)
K                          ceilingKey(K key)
void                       clear()
Object                     clone()
// 返回comparator
Comparator<? super K>      comparator()
boolean                    containsKey(Object key)
// 降序返回key/map
NavigableSet<K>            descendingKeySet()
NavigableMap<K, V>         descendingMap()
Set<Entry<K, V>>           entrySet()
// 返回第一个key/entry
Entry<K, V>                firstEntry()
K                          firstKey()
// 返回(小于等于输入key)的最大的key/entry,不存在返回null
Entry<K, V>                floorEntry(K key)
K                          floorKey(K key)
V                          get(Object key)
// 返回优先级高于指定k的部分map,inclusive为是否包含当前key
NavigableMap<K, V>         headMap(K to, boolean inclusive)
SortedMap<K, V>            headMap(K toExclusive)
// 返回大于给定key的第一个节点
Entry<K, V>                higherEntry(K key)
K                          higherKey(K key)
boolean                    isEmpty()
Set<K>                     keySet()
// 最后一个key/entry
Entry<K, V>                lastEntry()
K                          lastKey()
// 返回小于给定key的第一个节点
Entry<K, V>                lowerEntry(K key)
K                          lowerKey(K key)
// 返回NavigableSet,可以导航..有low/high等方法
NavigableSet<K>            navigableKeySet()
// 弹出第一个key/entry
Entry<K, V>                pollFirstEntry()
Entry<K, V>                pollLastEntry()
V                          put(K key, V value)
V                          remove(Object key)
int                        size()
SortedMap<K, V>            subMap(K fromInclusive, K toExclusive)
NavigableMap<K, V>         subMap(K from, boolean fromInclusive, K to, boolean toInclusive)
// 返回尾部map,小于给定k,inclusive为控制是否包含
NavigableMap<K, V>         tailMap(K from, boolean inclusive)
SortedMap<K, V>            tailMap(K fromInclusive)

TreeSet

TreeSet是基于TreeMap实现的。TreeSet中的元素支持2种排序方式:自然排序 或者 根据创建TreeSet 时提供的 Comparator 进行排序。这取决于使用的构造方法。

因为他是基于TreeMap实现的,所以其实也是基于红黑树,其基本操作(add、remove 和 contains等)都是O(logn)的时间复杂度.

API如下:

代码语言:javascript
复制
boolean                   add(E object)
boolean                   addAll(Collection<? extends E> collection)
void                      clear()
Object                    clone()
boolean                   contains(Object object)
// 返回第一个/最后一个元素
E                         first()
E                         last()
boolean                   isEmpty()
// 弹出第一个或者最后一个元素
E                         pollFirst()
E                         pollLast()
// 返回大于/小于给定元素的元素
E                         higher(E e)
E                         lower(E e)
// 返回小于/大于给定元素的最大/最小的一个
E                         floor(E e)
E                         ceiling(E e)
boolean                   remove(Object object)
int                       size()
Comparator<? super E>     comparator()
Iterator<E>               iterator()
// 降序遍历
Iterator<E>               descendingIterator()
// 返回大于/小于给定元素的所有元素集合,endInclusive为是否包含的控制量
SortedSet<E>              headSet(E end)
NavigableSet<E>           headSet(E end, boolean endInclusive)
SortedSet<E>              tailSet(E start)
NavigableSet<E>           tailSet(E start, boolean startInclusive)
// 降序的set
NavigableSet<E>           descendingSet()
// 子集合
SortedSet<E>              subSet(E start, E end)
NavigableSet<E>           subSet(E start, boolean startInclusive, E end, boolean endInclusive)

参考文章

https://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91

完。

ChangeLog

2019-05-25 完成 以上皆为个人所思所得,如有错误欢迎评论区指正。

欢迎转载,烦请署名并保留原文链接。

联系邮箱:huyanshi2580@gmail.com


本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 前言
  • 红黑树
  • TreeMap
  • TreeSet
  • 参考文章
    • ChangeLog
    领券
    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档