Эффективная структура данных для отсортированного списка

Question

Я хочу сохранить объекты в соответствии с ключом в атрибутах моего объекта отсортированным способом. Позже я буду обращаться к этим объектам последовательно с max key на min key. Я также займусь поисковыми задачами.

Я рассматриваю использование либо дерева AVL, либо дерева RB. Насколько я знаю, они почти эквивалентны в теории (оба имеют O (logn)). Но на практике это может быть лучше в моей ситуации. И есть ли лучшая альтернатива, чем те, учитывая, что я в основном делаю вставку и последовательный доступ к ds.

Edit: Я собираюсь использовать Java

Answer 1

Для чего это необходимо, в C# SortedDictionary<K, V> реализовано как красно-черное дерево, а во многих реализациях STL в C++ std::map<K, T> реализовано как красно-черное дерево.

Кроме того, из Wikipedia на AVL против красно-черных деревьев:

Дерево АВЛ является другая структура поддерживает O (журнал п) поиск, вставка и удаление . Это более жестко сбалансированных, чем красно-черных деревьев, ведущих для более медленного ввода и удаления, но более быстрое извлечение. Это делает его привлекательным для структур данных, которые могут быть построены один раз и загружается без реконструкции, таких как язык словари (или программных словари, , таких как коды порядка в ассемблере или переводчика).

Answer 2

Который когда-либо является самым легким для вас, чтобы реализовать, вы не получите лучшую вставку, чем журнал (п) с отсортированного списка, и мы, вероятно, потребуется много более подробно, чем то, что вы предоставили, чтобы решить, есть ли другие факторы, которые делают другую структуру более подходящей.

Answer 3

Как вы делаете это в Java, рассмотреть вопрос об использовании TreeSet (хотя это набор, так что вы не можете иметь повторяющиеся записи) ...