TreeMap

Iz MaFiRaWiki

Razred TreeMap v programskem jeziku java je podatkovna struktura, ki ji pravimo 'preslikava'. Uporabljamo jo takrat, ko želimo poiskati določen podatek po njegovem ključu. Na primer, če si želimo ustvariti svoj Slovar slovenskega knjižnega jezika (SSKJ).


  • bandera => prapor, zastava
  • galona => angleška prostorninska mera za tekočine, približno 4,5 l: galona vode / kamion s sto galonami
  • juškniti => zavriskati, zaukati: zamahnil je s palico v pozdrav in kratko jušknil
  • kabrnek => grozd, dokler še nima razvitih jagod: na trti so šele kabrnki
  • takalikati => kotaliti, valiti: takalikati kroglico po tleh
  • žnabelj => ustnica: držati žnablje skupaj; ugrizniti se v žnabelj; spodnji žnabelj


TreeMap je razširitev razreda AbstractMap in implementira vmesnike SortedMap, Cloneable in Serializable.

TreeMap je implemtacija SortedMap vmesnika na osnovi rdeče-črnega drevesa. V razredu je zagotovljeno, da bodo vse preslikave urejene v naraščajočem zaporedju glede na ključ, oziroma glede na razred Comparable. Odvisno kateri konstruktor je uporabljen. Vse operacije (containsKey, put, get, remove) v razredu se izvedejo v log(n) času. TreeMap pozna urejanje na naravni način. To je vrstni red urejenosti ključev ( nek podatek bo pred drugim natanko tedaj, ko bo njegov ključ manjši od ključa drugega podatka).



Vsebina

Konstruktorji:

  • TreeMap()
  Ustvari novo prazno drevo, ki bo urejeno na naravni način. Vsi ključi vstavljeni v drevo se primerjajo z 
  k1.compareTo(k2)(ali comparator.compare(k1, k2)).

  • TreeMap(Comparator<? super K> c)
  Ustvari novo prazno drevo, ki bo urejeno glede na parameter c. Comparator primerja razrede tipa K (torej ključa k1 in k2)
  comparator.compare(k1, k2)


  • TreeMap(Map<? extends K,? extends V> m)
  Ustvari novo drevo, ki vsebuje vse preslikave iz parametra m in je urejeno na naravni način. Vsi ključi vstavljeni v 
  drevo se primerjajo z k1.compareTo(k2)(ali comparator.compare(k1, k2)).    
  • TreeMap(SortedMap<K,? extends V)
  Ustvari novo drevo, ki vsebuje vse preslikave iz parametra m in je urejeno na način, ki je določen v m. Vsi ključi  
  vstavljeni v drevo se primerjajo z k1.compareTo(k2)(ali comparator.compare(k1, k2)).


Metode:

  • public void clear()
  Odstrani vse preslikave iz drevesa.

  • public Object clone()
  Vrne kopijo objekta, vendar brez ključev in njunih vrednosti.

  • public Comparator<? super K> comparator()
  Vrne objekt po katerem so urejene preslikave. Če metoda vrne null, pomeni da je uporabljen naravni način urejanja.

  • public boolean containsKey(Object key)
  Vrne true, če ključ key obstaja v drevesu, sicer vrne false.

  • public boolean containsValue(Object value)
  Vrne true, če drevo vsebuje eno ali več vrednosti value, sicer vrne false. Primerjamo z value.equals(v)

  • Set<Map.Entry<K,V>> entrySet()
  Vrne drevo (ključe) prikazano v obliki razreda Set. Vrne ga v naraščajočem vrstnem redu. Set podpira odstranitev elementov
  z Iterator.remove, Set.remove, removeAll, retainAll in clear operacijo. Ne podpira add in addAll operacij dodajanja.
  • public K firstKey()
  Vrne prvi (najnižji) ključ v urejenem drevesu.

  • public V get(Object key)
  Vrne vrednost za ključ key.

  • public SortedMap<K,V> headMap(K toKey)
  Vrne novo drevo, ki vsebuje vse ključe strogo manjše od toKey.

  • public Set<K> keySet()
  Vrne drevo (vrednosti) prikazano v obliki razreda Set. Vrne ga v naraščajočem vrstnem redu. Set podpira odstranitev  
  elementov z Iterator.remove, Set.remove, removeAll, retainAll in clear operacijo. Ne podpira add in addAll 
  operacij dodajanja.

  • public K lastKey()
  Vrne zadnji (največji ključ) v trenutno zgrajenem drevesu.

  • public V put(K key, V value)
  Vstavi ključ in njegovo vrednost v drevo.

  • public void putAll(Map<? extends K,? extends V> map)
  Vstavi v drevo vse preslikave iz parametera map.

  • public V remove(Object key)
  Odstrani preslikavo iz drevesa, ki ima za ključ key.

  • int size()
  Vrne število preslikav v drevesu.
                 
  • public SortedMap<K,V> subMap(K fromKey, K toKey)
  Vrne preslikavo, ki vsebuje vse elemente med ključoma fromKey in toKey.

  • public SortedMap<K,V> tailMap(K fromKey)
  Vrne novo drevo, ki vsebuje vse ključe enake ali večje od fromKey.

  • public Collection<V> values()
  Vrne seznam vrednosti (preslikav) v drevesu.

Primer

  1. import java.util.*;
  2.  
  3. public class MojSlovar {
  4. public static void main(String[] args) {
  5.  
  6. TreeMap slovar = new TreeMap(); //naredimo novo preslikavo slovar. Na začetku je preslikava prazna.
  7.  
  8. //v slovar dodamo besede s prevodi
  9. slovar.put("bandera ", "prapor, zastava ");
  10. slovar.put("galona", "angleška prostorninska mera za tekočine, približno 4,5 l: galona vode / kamion s sto galonami");
  11. slovar.put("juškniti", " zavriskati, zaukati: zamahnil je s palico v pozdrav in kratko jušknil");
  12. slovar.put("kabrnek ", "grozd, dokler še nima razvitih jagod: na trti so šele kabrnki ");
  13. slovar.put("takalikati", "kotaliti, valiti: takalikati kroglico po tleh ");
  14. slovar.put("žnabelj ", "ustnica: držati žnablje skupaj; ugrizniti se v žnabelj; spodnji žnabelj ");
  15.  
  16. String beseda = args[0];
  17.  
  18. //z objektno metodo get poiščemo vrednost, ki pripada geslu besede. Ker metoda get vrne splošni objekt, ga moramo še
  19. //pretvoriti v String tako, da napišemo (String) pred klic metode.
  20. String prevod = (String)slovar.get(beseda);
  21.  
  22. //preverimo, ali je rezultat metode get enak null. Če je, potem besede ni v slovarju.
  23. if (prevod == null) {
  24. System.out.println("Besede \"" + beseda + "\" ni v slovarju.");
  25. }
  26. else {
  27. System.out.println(prevod);
  28. }
  29. }
  30. }

Izpiše:

  • v našem primeru je argument galona

C:Java>javac MojSlovar.java
C:Java>java MojSlovar galona
angleška prostorninska mera za tekočine, približno 4,5 l: galona vode / kamion s sto galonami
 


Zunanje povezave

Osebna orodja