Понимание TreeMaps

Question

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

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

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

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

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

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

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

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

Answer 1

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

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

Answer 2

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

Answer 3

TreeMap - это Map (реализовано через дерево), а не дерево (реализовано через Map или иначе).

Answer 4

Я думаю, вы смешиваете две разные вещи. A TreeMap реализовано как Красно-Черное дерево.
По Java-документу:

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

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

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

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

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

Answer 5

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

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

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

• Каждый узел имеет 3 ссылки: РОДИТЕЛЬ, ЛЕВЫЙ и ПРАВО.
• Элементы LEFT всегда меньше родительского элемента.
• ПРАВЫЕ элементы всегда террированы или равны родительскому элементу.