Za izvedbo se uporablja TreeMap v Javi Vmesnik zemljevida in NavigableMap skupaj z razredom AbstractMap. Zemljevid je razvrščen glede na naravni vrstni red njegovih ključev ali po a Primerjalnik na voljo ob ustvarjanju zemljevida, odvisno od uporabljenega konstruktorja. To se je izkazalo za učinkovit način razvrščanja in shranjevanja parov ključ-vrednost. Vrstni red shranjevanja, ki ga vzdržuje drevesni zemljevid, mora biti skladen z enakimi, tako kot kateri koli drug razvrščeni zemljevid, ne glede na eksplicitne primerjalnike. Izvedba drevesnega zemljevida ni sinhronizirana v smislu, da če do zemljevida hkrati dostopa več niti in vsaj ena od niti strukturno spremeni zemljevid, mora biti sinhroniziran od zunaj.
TreeMap v Javi je konkretna implementacija vmesnika java.util.SortedMap. Zagotavlja urejeno zbirko parov ključ-vrednost, kjer so ključi razvrščeni na podlagi njihovega naravnega vrstnega reda ali primerjalnika po meri, posredovanega konstruktorju.
TreeMap je implementiran z uporabo rdeče-črnega drevesa, ki je vrsta samouravnoteženega binarnega iskalnega drevesa. To zagotavlja učinkovito delovanje običajnih operacij, kot so dodajanje, odstranjevanje in pridobivanje elementov, s povprečno časovno kompleksnostjo O(log n).
Tu je primer uporabe razreda TreeMap:
Java
import> java.util.Map;> import> java.util.TreeMap;> public> class> Main {> >public> static> void> main(String[] args) {> >Map treeMap =>new> TreeMap();> >// Adding elements to the tree map> >treeMap.put(>'A'>,>1>);> >treeMap.put(>'C'>,>3>);> >treeMap.put(>'B'>,>2>);> >// Getting values from the tree map> >int> valueA = treeMap.get(>'A'>);> >System.out.println(>'Value of A: '> + valueA);> >// Removing elements from the tree map> >treeMap.remove(>'B'>);> >// Iterating over the elements of the tree map> >for> (String key : treeMap.keySet()) {> >System.out.println(>'Key: '> + key +>', Value: '> + treeMap.get(key));> >}> >}> }> |
>
>Izhod
Value of A: 1 Key: A, Value: 1 Key: C, Value: 3>
Lastnosti TreeMapa
Nekatere pomembne lastnosti drevesnega zemljevida so naslednje:
- Ta razred je član Zbirke Java Okvir.
- Razred izvaja Vmesniki zemljevidov vključno z NavigableMap, SortedMap in razširja razred AbstractMap.
- TreeMap v Javi ne dovoljuje ničelnih ključev (kot je Map), zato se vrže izjema NullPointerException. Vendar je lahko več ničelnih vrednosti povezanih z različnimi ključi.
- Pari vnosov, ki jih vrnejo metode v tem razredu, in njegovi pogledi predstavljajo posnetke preslikav v času, ko so bile izdelane. Ne podpirajo metode Entry.setValue.
Zdaj pa pojdimo naprej in razpravljajmo o sinhroniziranem drevesnem zemljevidu. Implementacija TreeMap ni sinhronizirana. To pomeni, da če več niti hkrati dostopa do drevesnega nabora in vsaj ena od niti spremeni nabor, ga je treba sinhronizirati zunaj. To se običajno doseže z uporabo metode Collections.synchronizedSortedMap. To je najbolje narediti v času ustvarjanja, da preprečite nenameren nesinhroniziran dostop do niza. To je mogoče storiti kot:
SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));>
Geeki, zdaj se gotovo sprašujete, kako TreeMap deluje interno?
Metode v TreeMap, medtem ko pridobivajo nabor ključev in vrednosti, vrnejo Iterator, ki je po naravi hiter. Tako bo vsaka sočasna sprememba vrgla ConcurrentModificationException. TreeMap temelji na podatkovni strukturi rdeče-črnega drevesa.
Vsako vozlišče v drevesu ima:
- 3 spremenljivke ( K ključ=Ključ, V vrednost=Vrednost, logična barva=Barva )
- 3 Reference ( Vstop levo = levo, vstop desno = desno, vnos parent = starš )
Konstruktorji v TreeMap
Da bi ustvarili TreeMap, moramo ustvariti objekt razreda TreeMap. Razred TreeMap je sestavljen iz različnih konstruktorjev, ki omogočajo možno ustvarjanje TreeMapa. V tem razredu so na voljo naslednji konstruktorji:
- TreeMap()
- TreeMap (komparator)
- TreeMap (zemljevid M)
- TreeMap(SortedMap sm)
Razpravljajmo o njih posamično skupaj z implementacijo vsakega konstruktorja, kot sledi:
Konstruktor 1: TreeMap()
Ta konstruktor se uporablja za izdelavo praznega drevesnega zemljevida, ki bo razvrščen po naravnem vrstnem redu svojih ključev.
Primer
Java
// Java Program to Demonstrate TreeMap> // using the Default Constructor> // Importing required classes> import> java.util.*;> import> java.util.concurrent.*;> // Main class> // TreeMapImplementation> public> class> GFG {> >// Method 1> >// To show TreeMap constructor> >static> void> Example1stConstructor()> >{> >// Creating an empty TreeMap> >TreeMap tree_map> >=>new> TreeMap();> >// Mapping string values to int keys> >// using put() method> >tree_map.put(>10>,>'Geeks'>);> >tree_map.put(>15>,>'4'>);> >tree_map.put(>20>,>'Geeks'>);> >tree_map.put(>25>,>'Welcomes'>);> >tree_map.put(>30>,>'You'>);> >// Printing the elements of TreeMap> >System.out.println(>'TreeMap: '> + tree_map);> >}> >// Method 2> >// Main driver method> >public> static> void> main(String[] args)> >{> >System.out.println(>'TreeMap using '> >+>'TreeMap() constructor:
'>);> >// Calling constructor> >Example1stConstructor();> >}> }> |
>
>Izhod
TreeMap using TreeMap() constructor: TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}> Konstruktor 2: TreeMap (komparator)
Ta konstruktor se uporablja za izdelavo praznega predmeta TreeMap, v katerem bodo elementi potrebovali zunanjo specifikacijo vrstnega reda razvrščanja.
Primer
Java
// Java Program to Demonstrate TreeMap> // using Comparator Constructor> // Importing required classes> import> java.util.*;> import> java.util.concurrent.*;> // Class 1> // Helper class representing Student> class> Student {> >// Attributes of a student> >int> rollno;> >String name, address;> >// Constructor> >public> Student(>int> rollno, String name, String address)> >{> >// This keyword refers to current object itself> >this>.rollno = rollno;> >this>.name = name;> >this>.address = address;> >}> >// Method of this class> >// To print student details> >public> String toString()> >{> >return> this>.rollno +>' '> +>this>.name +>' '> >+>this>.address;> >}> }> // Class 2> // Helper class - Comparator implementation> class> Sortbyroll>implements> Comparator {> >// Used for sorting in ascending order of> >// roll number> >public> int> compare(Student a, Student b)> >{> >return> a.rollno - b.rollno;> >}> }> // Class 3> // Main class> public> class> GFG {> >// Calling constructor inside main()> >static> void> Example2ndConstructor()> >{> >// Creating an empty TreeMap> >TreeMap tree_map> >=>new> TreeMap(> >new> Sortbyroll());> >// Mapping string values to int keys> >tree_map.put(>new> Student(>111>,>'bbbb'>,>'london'>),>2>);> >tree_map.put(>new> Student(>131>,>'aaaa'>,>'nyc'>),>3>);> >tree_map.put(>new> Student(>121>,>'cccc'>,>'jaipur'>),>1>);> >// Printing the elements of TreeMap> >System.out.println(>'TreeMap: '> + tree_map);> >}> >// Main driver method> >public> static> void> main(String[] args)> >{> >System.out.println(>'TreeMap using '> >+>'TreeMap(Comparator)'> >+>' constructor:
'>);> >Example2ndConstructor();> >}> }> |
>
>Izhod
TreeMap using TreeMap(Comparator) constructor: TreeMap: {111 bbbb london=2, 121 cccc jaipur=1, 131 aaaa nyc=3}> Konstruktor 3: TreeMap (zemljevid M)
Ta konstruktor se uporablja za inicializacijo TreeMap z vnosi iz danega zemljevida M, ki bodo razvrščeni z uporabo naravnega vrstnega reda ključev.
Primer
Java
// Java Program to Demonstrate TreeMap> // using the Default Constructor> // Importing required classes> import> java.util.*;> import> java.util.concurrent.*;> // Main class> public> class> TreeMapImplementation {> >// Method 1> >// To illustrate constructor> >static> void> Example3rdConstructor()> >{> >// Creating an empty HashMap> >Map hash_map> >=>new> HashMap();> >// Mapping string values to int keys> >// using put() method> >hash_map.put(>10>,>'Geeks'>);> >hash_map.put(>15>,>'4'>);> >hash_map.put(>20>,>'Geeks'>);> >hash_map.put(>25>,>'Welcomes'>);> >hash_map.put(>30>,>'You'>);> >// Creating the TreeMap using the Map> >TreeMap tree_map> >=>new> TreeMap(hash_map);> >// Printing the elements of TreeMap> >System.out.println(>'TreeMap: '> + tree_map);> >}> >// Method 2> >// Main driver method> >public> static> void> main(String[] args)> >{> >System.out.println(>'TreeMap using '> >+>'TreeMap(Map)'> >+>' constructor:
'>);> >Example3rdConstructor();> >}> }> |
>
>Izhod
TreeMap using TreeMap(Map) constructor: TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}> Konstruktor 4: TreeMap(SortedMap sm)
Ta konstruktor se uporablja za inicializacijo TreeMap z vnosi iz danega razvrščenega zemljevida, ki bo shranjen v istem vrstnem redu kot dani razvrščeni zemljevid.
Primer
Java
// Java Program to Demonstrate TreeMap> // using the SortedMap Constructor> // Importing required classes> import> java.util.*;> import> java.util.concurrent.*;> // Main class> // TreeMapImplementation> public> class> GFG {> >// Method> >// To show TreeMap(SortedMap) constructor> >static> void> Example4thConstructor()> >{> >// Creating a SortedMap> >SortedMap sorted_map> >=>new> ConcurrentSkipListMap();> >// Mapping string values to int keys> >// using put() method> >sorted_map.put(>10>,>'Geeks'>);> >sorted_map.put(>15>,>'4'>);> >sorted_map.put(>20>,>'Geeks'>);> >sorted_map.put(>25>,>'Welcomes'>);> >sorted_map.put(>30>,>'You'>);> >// Creating the TreeMap using the SortedMap> >TreeMap tree_map> >=>new> TreeMap(sorted_map);> >// Printing the elements of TreeMap> >System.out.println(>'TreeMap: '> + tree_map);> >}> >// Method 2> >// Main driver method> >public> static> void> main(String[] args)> >{> >System.out.println(>'TreeMap using '> >+>'TreeMap(SortedMap)'> >+>' constructor:
'>);> >Example4thConstructor();> >}> }> |
>
>Izhod
TreeMap using TreeMap(SortedMap) constructor: TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}> Metode v razredu TreeMap
| Metoda | Dejanje izvedeno |
|---|---|
| počisti() | Metoda odstrani vse preslikave iz tega TreeMapa in počisti zemljevid. |
| klon() | Metoda vrne plitvo kopijo tega TreeMapa. |
| containsKey(ključ predmeta) | Vrne true, če ta preslikava vsebuje preslikavo za navedeni ključ. |
| containsValue(vrednost predmeta) | Vrne true, če ta preslikava preslika enega ali več ključev v podano vrednost. |
| vnosSet() | Vrne nastavljeni pogled preslikav, ki jih vsebuje ta zemljevid. |
| firstKey() | Vrne prvi (najnižji) ključ trenutno v tem razvrščenem zemljevidu. |
| get (ključ predmeta) | Vrne vrednost, v katero ta preslikava preslika podani ključ. |
| headMap(predmet ključ_vrednost) | Metoda vrne pogled na del zemljevida, ki je strogo manjši od parametra key_value. |
| keySet() | Metoda vrne pogled Set ključev, ki jih vsebuje drevesni zemljevid. |
| lastKey() | Vrne zadnji (najvišji) ključ trenutno v tem razvrščenem zemljevidu. |
| put(ključ predmeta, vrednost predmeta) | Metoda se uporablja za vstavljanje preslikav v zemljevid. |
| putAll(Map zemljevid) | Kopira vse preslikave s podanega zemljevida na ta zemljevid. |
| odstrani (ključ predmeta) | Odstrani preslikavo za ta ključ iz tega drevesnega zemljevida, če je prisoten. |
| velikost () | Vrne število preslikav ključa in vrednosti v tem zemljevidu. |
| subMap((K startKey, K endKey) | Metoda vrne del tega zemljevida, katerega ključi segajo od startKey, vključno, do endKey, izključno. |
| vrednote() | Vrne pogled zbirke vrednosti, ki jih vsebuje ta zemljevid. |
Izvedba: Naslednji programi spodaj bodo bolje prikazali, kako ustvariti, vstaviti in prečkati TreeMap.
Ilustracija:
Java
// Java Program to Illustrate Operations in TreeMap> // Such as Creation, insertion> // searching, and traversal> // Importing required classes> import> java.util.*;> import> java.util.concurrent.*;> // Main class> // Implementation of TreeMap> public> class> GFG {> >// Declaring a TreeMap> >static> TreeMap tree_map;> >// Method 1> >// To create TreeMap> >static> void> create()> >{> >// Creating an empty TreeMap> >tree_map =>new> TreeMap();> >// Display message only> >System.out.println(>'TreeMap successfully'> >+>' created'>);> >}> >// Method 2> >// To Insert values in the TreeMap> >static> void> insert()> >{> >// Mapping string values to int keys> >// using put() method> >tree_map.put(>10>,>'Geeks'>);> >tree_map.put(>15>,>'4'>);> >tree_map.put(>20>,>'Geeks'>);> >tree_map.put(>25>,>'Welcomes'>);> >tree_map.put(>30>,>'You'>);> >// Display message only> >System.out.println(>'
Elements successfully'> >+>' inserted in the TreeMap'>);> >}> >// Method 3> >// To search a key in TreeMap> >static> void> search(>int> key)> >{> >// Checking for the key> >System.out.println(>'
Is key ''> + key> >+>'' present? '> >+ tree_map.containsKey(key));> >}> >// Method 4> >// To search a value in TreeMap> >static> void> search(String value)> >{> >// Checking for the value> >System.out.println(>'
Is value ''> + value> >+>'' present? '> >+ tree_map.containsValue(value));> >}> >// Method 5> >// To display the elements in TreeMap> >static> void> display()> >{> >// Displaying the TreeMap> >System.out.println(>'
Displaying the TreeMap:'>);> >System.out.println(>'TreeMap: '> + tree_map);> >}> >// Method 6> >// To traverse TreeMap> >static> void> traverse()> >{> >// Display message only> >System.out.println(>'
Traversing the TreeMap:'>);> >for> (Map.Entry e :> >tree_map.entrySet())> >System.out.println(e.getKey() +>' '> >+ e.getValue());> >}> >// Method 6> >// Main driver method> >public> static> void> main(String[] args)> >{> >// Calling above defined methods inside main()> >// Creating a TreeMap> >create();> >// Inserting the values in the TreeMap> >insert();> >// Search key '50' in the TreeMap> >search(>50>);> >// Search value 'Geeks' in the TreeMap> >search(>'Geeks'>);> >// Display the elements in TreeMap> >display();> >// Traversing the TreeMap> >traverse();> >}> }> |
>
>Izhod
TreeMap successfully created Elements successfully inserted in the TreeMap Is key '50' present? false Is value 'Geeks' present? true Displaying the TreeMap: TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You} Traversing the TreeMap: 10 Geeks 15 4 20 Geeks 25 Welcomes 30 You> Izvajanje različnih operacij na TreeMap
Po uvedbi Generics v Javi 1.5 je mogoče omejiti vrsto predmeta, ki se lahko shrani v TreeMap. Zdaj pa poglejmo, kako izvesti nekaj pogosto uporabljenih operacij na TreeMap.
Operacija 1: Dodajanje elementov
Da bi dodali element v TreeMap, lahko uporabimo metodo put(). Vendar se vrstni red vstavljanja ne ohrani v TreeMap. Interno se za vsak element ključi primerjajo in razvrščajo v naraščajočem vrstnem redu.
Primer
Java
// Java Program to Illustrate Addition of Elements> // in TreeMap using put() Method> // Importing required classes> import> java.util.*;> // Main class> class> GFG {> >// Main driver method> >public> static> void> main(String args[])> >{> >// Default Initialization of a TreeMap> >TreeMap tm1 =>new> TreeMap();> >// Inserting the elements in TreeMap> >// using put() method> >tm1.put(>3>,>'Geeks'>);> >tm1.put(>2>,>'For'>);> >tm1.put(>1>,>'Geeks'>);> >// Initialization of a TreeMap using Generics> >TreeMap tm2> >=>new> TreeMap();> >// Inserting the elements in TreeMap> >// again using put() method> >tm2.put(>new> Integer(>3>),>'Geeks'>);> >tm2.put(>new> Integer(>2>),>'For'>);> >tm2.put(>new> Integer(>1>),>'Geeks'>);> >// Printing the elements of both TreeMaps> >// Map 1> >System.out.println(tm1);> >// Map 2> >System.out.println(tm2);> >}> }> |
>
>Izhod
{1=Geeks, 2=For, 3=Geeks} {1=Geeks, 2=For, 3=Geeks}> Operacija 2: Spreminjanje elementov
Po dodajanju elementov, če želimo spremeniti element, lahko to storimo tako, da znova dodamo element z metodo put(). Ker so elementi v drevesnem zemljevidu indeksirani s ključi, lahko vrednost ključa spremenite tako, da preprosto vstavite posodobljeno vrednost za ključ, za katerega želimo spremeniti.
Primer
Java
// Java program to Illustrate Updation of Elements> // in TreeMap using put() Method> // Importing required classes> import> java.util.*;> // Main class> class> GFG {> >// Main driver method> >public> static> void> main(String args[])> >{> >// Initialization of a TreeMap> >// using Generics> >TreeMap tm> >=>new> TreeMap();> >// Inserting the elements in Map> >// using put() method> >tm.put(>3>,>'Geeks'>);> >tm.put(>2>,>'Geeks'>);> >tm.put(>1>,>'Geeks'>);> >// Print all current elements in map> >System.out.println(tm);> >// Inserting the element at specified> >// corresponding to specified key> >tm.put(>2>,>'For'>);> >// Printing the updated elements of Map> >System.out.println(tm);> >}> }> |
>
>Izhod
{1=Geeks, 2=Geeks, 3=Geeks} {1=Geeks, 2=For, 3=Geeks}> Operacija 3: Odstranjevanje elementa
Če želite odstraniti element iz TreeMap, lahko uporabimo metodo remove(). Ta metoda prevzame vrednost ključa in odstrani preslikavo za ključ iz tega drevesnega zemljevida, če je prisoten v zemljevidu.
Primer
Java
execvp
// Java program to Illustrate Removal of Elements> // in TreeMap using remove() Method> // Importing required classes> import> java.util.*;> // Main class> class> GFG {> >// Main driver method> >public> static> void> main(String args[])> >{> >// Initialization of a TreeMap> >// using Generics> >TreeMap tm> >=>new> TreeMap();> >// Inserting the elements> >// using put() method> >tm.put(>3>,>'Geeks'>);> >tm.put(>2>,>'Geeks'>);> >tm.put(>1>,>'Geeks'>);> >tm.put(>4>,>'For'>);> >// Printing all elements of Map> >System.out.println(tm);> >// Removing the element corresponding to key> >tm.remove(>4>);> >// Printing updated TreeMap> >System.out.println(tm);> >}> }> |
>
>Izhod
{1=Geeks, 2=Geeks, 3=Geeks, 4=For} {1=Geeks, 2=Geeks, 3=Geeks}> Operacija 4: Ponavljanje skozi TreeMap
Obstaja več načinov za ponavljanje po zemljevidu. Najbolj znan način je uporaba a za vsako zanko in dobi ključe. Vrednost ključa se najde z uporabo metoda getValue(). .
Primer
Java
// Java Program to Illustrate Iterating over TreeMap> // using> // Importing required classes> import> java.util.*;> // Main class> class> GFG {> >// Main driver method> >public> static> void> main(String args[])> >{> >// Initialization of a TreeMap> >// using Generics> >TreeMap tm> >=>new> TreeMap();> >// Inserting the elements> >// using put() method> >tm.put(>3>,>'Geeks'>);> >tm.put(>2>,>'For'>);> >tm.put(>1>,>'Geeks'>);> >// For-each loop for traversal over Map> >// via entrySet() Method> >for> (Map.Entry mapElement : tm.entrySet()) {> >int> key = (>int>)mapElement.getKey();> >// Finding the value> >String value = (String)mapElement.getValue();> >// Printing the key and value> >System.out.println(key +>' : '> + value);> >}> >}> }> |
>
>Izhod
1 : Geeks 2 : For 3 : Geeks>
Prednosti TreeMap:
- Razvrščen vrstni red: TreeMap zagotavlja razvrščen vrstni red svojih elementov na podlagi naravnega vrstnega reda njegovih ključev ali primerjalnika po meri, posredovanega konstruktorju. Zaradi tega je uporaben v situacijah, ko morate pridobiti elemente v določenem vrstnem redu.
- Predvidljiv vrstni red ponovitev: ker so elementi v TreeMap shranjeni v razvrščenem vrstnem redu, lahko predvidite vrstni red, v katerem bodo vrnjeni med ponovitvijo, kar olajša pisanje algoritmov, ki obdelujejo elemente v določenem vrstnem redu.
- Učinkovitost iskanja: TreeMap zagotavlja učinkovito implementacijo vmesnika Map, ki vam omogoča pridobivanje elementov v logaritemskem času, zaradi česar je uporaben v iskalnih algoritmih, kjer morate hitro pridobiti elemente.
- Samouravnoteženje: TreeMap je implementiran z uporabo rdeče-črnega drevesa, ki je vrsta samouravnoteženega binarnega iskalnega drevesa. To zagotavlja učinkovito delovanje za dodajanje, odstranjevanje in pridobivanje elementov ter vzdrževanje razvrščenega vrstnega reda elementov.
Slabosti TreeMapa:
- Počasno vstavljanje elementov: Vstavljanje elementov v TreeMap je lahko počasnejše od vstavljanja elementov v običajen zemljevid, saj mora TreeMap ohraniti razvrščeni vrstni red svojih elementov.
- Omejitev ključa: ključi v TreeMap morajo implementirati vmesnik java.lang.Comparable ali pa mora biti zagotovljen primerjalnik po meri. To je lahko omejitev, če morate uporabiti ključe po meri, ki ne izvajajo tega vmesnika.
Referenčne knjige:
Java Collections Mauricea Naftalina in Philipa Wadlerja. Ta knjiga nudi celovit pregled ogrodja zbirk Java, vključno z TreeMap.
Java na kratko David Flanagan. V tej knjigi je hitra referenca za osnovne funkcije Jave, vključno z TreeMap.
Java Generics and Collections Mauricea Naftalina in Philipa Wadlerja. Ta knjiga ponuja izčrpen vodnik po generikih in zbirkah v Javi, vključno z TreeMap.