TreeMaps Overview

this is a noobie question regarding tree maps. I read the Java API and other documentation, but it is still unclear how this works.

In my opinion, a tree in java (or any language) is like a family tree; where do you say:

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

Where level 1 has 1 value (i.e. the central node), and from there in each subsequent layer there can be arbitrary amounts of values ​​(or guys), and some of the "branches" can be longer than others (for example, it can go OldestGuy β†’ OldGuy1 β†’ Guy1 and Guy2 ... Guyn, while at the same time the other branch is just OldestGuy β†’ OldGuy4)

With that in mind, I am trying to add values ​​to TreeMap in certain places of certain branches when creating certain connections, but all I seem to get is the same results as HashMap.

(it seems that what I want to do is require something more than TreeMap .... since the key (or layer (?) will be the same for several different values)

Any suggestions / explanations would be fantastic because I feel as though I am seriously barking the wrong tree with this.

I saw examples of this using googles.jar (like a family tree image), but I'm just trying to figure it out, as there seem to be a lot of conflicts between TreeMap and trees and how you can store data in them.

+6
source share
5 answers

TreeMap is just a Map implementation that uses a red-black tree behind the scenes. The details of the tree are not displayed to you, so you cannot store items in arbitrary places.

In other words, TreeMap not a general-purpose tree data structure. If this is what you really want, perhaps look at this question: Java tree data structure? .

+8
source
 public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, Serializable 
  • The tree map does not use hashing to store keys. It uses a Red-Black tree (a self-balancing binary search tree.).
  • TreeMap is sorted according to the natural order of its keys. A tree map will always have sorted items .
  • Working with a tree map is based on a tree data structure.
  • The tree map is not synchronized and therefore not thread safe .
  • The tree map in java does not support a null key , but allows multiple null values .

Working with a tree map is based on a tree data structure.

  • Each node has 3 links: PARENT, LEFT and RIGHT.
  • LEFT elements are always smaller than the parent element.
  • RIGHT elements are always terra or equal to the parent element.
+2
source

Java TreeMap uses the tree as an internal data structure to search and insert O (log n), but does not expose its tree structure in its interface. Thus, there is no way, for example, to get a node tree and all its descendants or to represent its family tree.

0
source

TreeMap is a Map (implemented through a tree), not a tree (implemented through a Map or otherwise).

0
source

I think you mix two different things. A TreeMap is implemented as a Red-Black Tree .
In the Java doc:

Implementation of NavigableMap based on Red-Black. The card is sorted in accordance with the natural order of its keys or the comparator, provided the card is created, depending on which constructor is used.

This implementation provides a guaranteed logarithmic (n) time value for containsKey, get, put and remove operations. Algorithms are an adaptation of those in Cormen, Leiserson and Rivest. to the algorithms.

So, essentially, if you want to have a predictable ordering of your keys, you must either leave TreeMap to order your keys using the natural order or implement the Comparator interface yourself. Again, from Javadoc:

Please note that the ordering supported by the tree map, like any sorted map, and whether an explicit comparator should be set, must be in accordance with the equalities if this sorted map must correctly implement the map interface. (See Comparative or Comparator for an exact definition of what is consistent with equals.) This is because the Map interface is defined in terms of the equality operation, but the sorted map performs all key mappings using the compareTo (or comparison) method, so there are two keys that are considered equal this method, are the point of view of the sorted card is equal. The behavior of an ordered map is clearly defined, even if its ordering does not match the equal; it just does not comply with the general map interface contract.

Now it’s unclear whether you want to put your keys in the way I mentioned (for example, the natural order) or in another way (i.e. the insertion order or something else?).
For example, if you prefer the insertion order, LinkedHashMap might be better for your business.
If something else is happening, indicate:].

0
source

Source: https://habr.com/ru/post/909903/


All Articles