В чем преимущество структуры данных treemap в Java помимо сортировки и упорядочения? Как работает внутренняя структура данных treemap?
преимущество структуры данных древовидной карты в java, помимо сортировки и упорядочения
comment
вы можете прочитать docs.oracle.com/javase /6/docs/api/java/util/TreeMap.html
- person sanbhat schedule 07.06.2013
comment
Я бы не сказал, что TreeMap выполняет сортировку и упорядочивание. Если он отсортирован, он должен иметь порядок. Но коллекция может быть упорядочена без сортировки: список имеет порядок, даже если элементы не были отсортированы. Набор не упорядочен и не отсортирован.
- person Andrew Spencer schedule 07.06.2013
comment
Основным преимуществом TreeMap является возможность хранить сопоставления, отсортированные по вашему собственному компаратору, и поэтому вы можете получить большее или меньшее сопоставление, наименьшее или наибольшее. Вкратце расскажу о моей внутренней жизни TreeMap учебник, чтобы узнать это лучше
- person Volodymyr Levytskyi schedule 10.08.2013
Ответы (2)
Основное преимущество карты дерева заключается в том, что она позволяет хранить сопоставления ключ-значение в отсортированном порядке. Treemap внутренне использует красное черное дерево.
Из javadocs:
Реализация NavigableMap на основе красно-черного дерева. Карта сортируется в соответствии с естественным порядком ее ключей или компаратором, предоставленным во время создания карты, в зависимости от того, какой конструктор используется.
Эта реализация обеспечивает гарантированную стоимость log(n) времени для операций containsKey, get, put и remove. Алгоритмы являются адаптацией алгоритмов Кормена, Лейзерсона и Ривеста «Введение в алгоритмы».
Красно-черное дерево из Вики:
Красно-черное дерево — это тип самобалансирующегося бинарного дерева поиска, структура данных, используемая в информатике. Самобалансировка обеспечивается закрашиванием каждого узла одним из двух цветов (обычно они называются «красный» и «черный», отсюда и название деревьев) таким образом, что результирующее окрашенное дерево удовлетворяет определенным свойствам, которые не выполняются. т позволить ему стать значительно несбалансированным. Когда дерево изменяется, новое дерево впоследствии перестраивается и перекрашивается, чтобы восстановить свойства окраски. Свойства спроектированы таким образом, чтобы эта перестановка и перекрашивание могли выполняться эффективно. Балансировка дерева не идеальна, но достаточно хороша, чтобы гарантировать поиск за время O(log n), где n — общее количество элементов в дереве. Операции вставки и удаления, а также перестановка дерева и перекрашивание также выполняются за время O(log n).[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
person
Juned Ahsan
schedule
07.06.2013
Если вы имеете в виду преимущество TreeMap над HashMap, то его нет. На самом деле у HashMap есть преимущество перед TreeMap — он быстрее. Что касается внутренней реализации, вы можете загрузить стандартный lib src с сайта Oracle или отсюда http://sourceforge.net/projects/jdk7src/
person
Evgeniy Dorofeev
schedule
07.06.2013
