java - java中treemap数据结构除了排序和排序之外的优点

Question

java中的treemap数据结构除了排序和排序之外还有什么优点？ 树形图数据结构内部如何工作？

Answer 1

Treemap 的主要优点是它允许按排序顺序存储键值映射。 Treemap内部使用红黑树。

来自 javadoc:

A Red-Black tree based NavigableMap implementation. The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.

This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations. Algorithms are adaptations of those in Cormen, Leiserson, and Rivest's Introduction to Algorithms.

来自 Wiki 的红黑树:

A red–black tree is a type of self-balancing binary search tree, a data structure used in computer science. The self-balancing is provided by painting each node with one of two colors (these are typically called 'red' and 'black', hence the name of the trees) in such a way that the resulting painted tree satisfies certain properties that don't allow it to become significantly unbalanced. When the tree is modified, the new tree is subsequently rearranged and repainted to restore the coloring properties. The properties are designed in such a way that this rearranging and recoloring can be performed efficiently. The balancing of the tree is not perfect but it is good enough to allow it to guarantee searching in O(log n) time, where n is the total number of elements in the tree. The insertion, and deletion operations, along with the tree rearrangement and recoloring are also performed in O(log n) time.[1]

要了解有关 Reb Black 树的更多信息，请查看:http://en.wikipedia.org/wiki/Red%E2%80%93black_tree

要了解有关树状图检查的更多信息:http://docs.oracle.com/javase/6/docs/api/java/util/TreeMap.html