Понимание TreeMaps

Question

это вопрос новичка относительно древовидных карт. Я прочитал Java API и другую документацию, но до сих пор неясно, как это работает.

Насколько я понимаю, Дерево в Java (или любом другом языке) похоже на семейное древо; где вы говорите:

Layer 1                               OldestGuy    
Layer 2       OldGuy1       Oldguy2         OldGuy3        OldGuy4           OldGuy5
Layer 3   Guy1 Guy2 Guy3 Guy4 Guy5  Guy6........ etc

Там, где уровень 1 имеет 1 значение (т. Е. Центральный узел), и оттуда может быть произвольное количество значений (или парней) в каждом последующем слое, и некоторые из «ветвей» могут быть длиннее других (например, его). мог бы пойти OldestGuy -> OldGuy1 -> Guy1 & Guy2 ... Guyn, в то время как другая ветвь просто OldestGuy -> OldGuy4)

Имея это в виду, я пытаюсь добавить значения в TreeMap в определенных местах определенных ветвей, в то же время создавая определенные соединения, но все, что мне кажется, это те же результаты, что и в HashMap.

(кажется, что я хочу сделать, требуется что-то большее, чем TreeMap .... так как ключ (или слой (?) Будет одинаковым для нескольких разных значений)

Любые предложения / объяснения были бы фантастическими, потому что мне кажется, что я серьезно лаю не на то дерево.

Я видел примеры того, как это делается с помощью googles .jar (например, семейного древа), но я просто пытаюсь понять это, так как, похоже, существует много конфликтов между TreeMap и Trees и тем, как вы можете хранить данные в их.

Answer 1

TreeMap - это просто реализация Map, в которой за кулисами используется красно-черное дерево. Детали дерева вам не доступны, поэтому вы не можете хранить элементы в произвольных местах.

Другими словами, TreeMap не является древовидной структурой данных общего назначения. Если это то, что вы действительно хотите, возможно, взгляните на вопрос переполнения стека: Структура данных дерева Java? .

Answer 2

public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, Serializable

• Карта дерева не использует хеширование для хранения ключей. Это использовать Красно-черный дерево (самобалансирующееся дерево двоичного поиска.).
• TreeMap сортируется в соответствии с естественным порядком его ключей. Древовидная карта всегда будет иметь все отсортированные элементы .
• Работа древовидной карты основана на древовидной структуре данных .
• Карта дерева не синхронизирована и, следовательно, не является поточно-ориентированной .
• Древовидная карта в java не допускает нулевой ключ , но допускает несколько нулевых значений .

Работа древовидной карты основана на древовидной структуре данных.

• Каждый узел имеет 3 ссылки: PARENT, LEFT и RIGHT.
• ЛЕВЫЕ элементы всегда меньше, чем родительский элемент.
• ПРАВЫЕ элементы всегда больше или равны родительскому элементу.

Answer 3

Я думаю, что вы путаете две разные вещи. TreeMap реализован как Красно-Черное дерево .
Согласно документу Java:

Реализация NavigableMap на основе красно-черного дерева. Карта отсортирована в соответствии с естественным упорядочением ключей или компаратором предоставляется во время создания карты, в зависимости от того, какой конструктор используется.

Эта реализация обеспечивает гарантированные затраты времени журнала (n) для Содержит ключи, получить, положить и удалить операции. Алгоритмы адаптация тех в Cormen, Leiserson и Rivest's Введение Алгоритмы.

Итак, по сути, если вы хотите иметь предсказуемое упорядочение ключей, вы должны либо оставить TreeMap, чтобы упорядочить ключи, используя естественное упорядочение, либо реализовать интерфейс Comparator самостоятельно. Опять же, из Javadoc:

Обратите внимание, что порядок поддерживается древовидной картой, как любая отсортированная карта, и должен ли быть предоставлен явный компаратор, должен быть в соответствии с равно, если эта отсортированная карта правильно реализовать интерфейс карты. (См. Comparable или Comparator для точного определение в соответствии с равными.) Это так, потому что карта Интерфейс определяется в терминах операции равенства, но отсортированный Карта выполняет все ключевые сравнения, используя ее CompareTo (или сравнение) метод, поэтому два ключа, которые считаются равными этим методом, из точка зрения отсортированной карты, равная. Поведение отсортированной карты четко определенный, даже если его порядок не совпадает с равным; это просто не соблюдает общий контракт интерфейса Map.

Теперь неясно, хотите ли вы расположить ключи так, как я упомянул (т. Е. Естественный порядок) или иным образом (т. Е. Порядок вставки или что-то еще?).
Например, если вы предпочитаете порядок вставки, LinkedHashMap может оказаться лучше для вашего случая.
Если дело обстоит иначе, укажите это:].

Answer 4

TreeMap - это Карта (реализована с помощью дерева), а не дерево (реализовано с помощью Карта или иным образом).

Answer 5

Java TreeMap использует дерево в качестве внутренней структуры данных для получения O (log n) поисков и вставок, но не раскрывает свою древовидную структуру в своем интерфейсе. Так что, например, нет способа получить узел дерева и всех его потомков или представить семейное дерево, используя его.