目录
前言
首先要注意的是,本文章不涉及到红黑树的具体实现,也就是说不会逐行分析TreeMap
和TreeSet
的源码实现,因为红黑树看了也会忘的…
所以本文只是记录红黑树的一些基础介绍,以及TreeMap
和TreeSet
两个类的公共API.
红黑树
红黑树,一种二叉查找树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。
通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。
红黑树首先是一颗二叉查找树,满足二叉查找树的一下特点:
- 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
- 若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值;
- 任意节点的左、右子树也分别为二叉查找树;
- 没有键值相等的节点。
红黑树在二叉查找树的基础上又有以下性质:
- 每个结点要么是红的要么是黑的。
- 根结点是黑的。
- 每个叶结点(叶结点即指树尾端NIL指针或NULL结点)都是黑的。
- 如果一个结点是红的,那么它的两个儿子都是黑的。
- 对于任意结点而言,其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。
通过这5个性质,可以保证红黑树的高度永远是logn
,所以红黑树的查找、插入、删除的时间复杂度最坏为O(log n).
红黑树有什么作用呢?那就是快,查找,插入,删除的时间复杂度最坏为O(logn).
红黑树的具体实现可以google一下,有很多开源的实现.中心思想就是各种旋转~.
TreeMap
TreeMap是一个有序的key-value集合,基于红黑树(Red-Black tree)实现。该映射根据其键的自然顺序进行排序,或者根据创建映射时提供的 Comparator 进行排序,具体取决于使用的构造方法。
具体的使用方法见下方API极其注释(常用的没有注释).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
| Entry<K, V> ceilingEntry(K key) K ceilingKey(K key) void clear() Object clone()
Comparator<? super K> comparator() boolean containsKey(Object key)
NavigableSet<K> descendingKeySet() NavigableMap<K, V> descendingMap() Set<Entry<K, V>> entrySet()
Entry<K, V> firstEntry() K firstKey()
Entry<K, V> floorEntry(K key) K floorKey(K key) V get(Object key)
NavigableMap<K, V> headMap(K to, boolean inclusive) SortedMap<K, V> headMap(K toExclusive)
Entry<K, V> higherEntry(K key) K higherKey(K key) boolean isEmpty() Set<K> keySet()
Entry<K, V> lastEntry() K lastKey()
Entry<K, V> lowerEntry(K key) K lowerKey(K key)
NavigableSet<K> navigableKeySet()
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)
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如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
| 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()
SortedSet<E> headSet(E end) NavigableSet<E> headSet(E end, boolean endInclusive) SortedSet<E> tailSet(E start) NavigableSet<E> tailSet(E start, boolean startInclusive)
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
更多学习笔记见个人博客——>呼延十