Na implementáciu sa používa stromová mapa v jazyku Java Mapové rozhranie a NavigableMap spolu s triedou AbstractMap. Mapa je zoradená podľa prirodzeného poradia jej kľúčov alebo podľa a Porovnávač poskytované v čase vytvorenia mapy v závislosti od použitého konštruktora. Toto sa ukazuje ako efektívny spôsob triedenia a ukladania párov kľúč – hodnota. Poradie ukladania udržiavané stromovou mapou musí byť konzistentné s rovnakým ako každá iná triedená mapa, bez ohľadu na explicitné porovnávače. Implementácia stromovej mapy nie je synchronizovaná v tom zmysle, že ak k mape pristupuje viacero vlákien súčasne a aspoň jedno z vlákien štrukturálne modifikuje mapu, musí byť synchronizovaná externe.
TreeMap v Jave je konkrétna implementácia rozhrania java.util.SortedMap. Poskytuje usporiadanú kolekciu párov kľúč-hodnota, kde sú kľúče usporiadané na základe ich prirodzeného poradia alebo vlastného komparátora odovzdaného konštruktorovi.
TreeMap je implementovaný pomocou červeno-čierneho stromu, čo je typ samovyvažujúceho binárneho vyhľadávacieho stromu. To poskytuje efektívny výkon pre bežné operácie, ako je pridávanie, odstraňovanie a získavanie prvkov, s priemernou časovou zložitosťou O (log n).
Tu je príklad, ako používať triedu 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));> >}> >}> }> |
>
>Výkon
Value of A: 1 Key: A, Value: 1 Key: C, Value: 3>
Vlastnosti stromovej mapy
Niektoré dôležité vlastnosti stromovej mapy sú nasledovné:
- Táto trieda je členom Kolekcie Java Rámec.
- Trieda implementuje Mapové rozhrania vrátane NavigableMap , SortedMap a rozširuje triedu AbstractMap.
- TreeMap v jazyku Java nepovoľuje nulové kľúče (ako Map), a preto je vyvolaná výnimka NullPointerException. K rôznym kľúčom však možno priradiť viacero hodnôt null.
- Vstupné páry vrátené metódami v tejto triede a jej zobrazenia predstavujú snímky mapovaní v čase, keď boli vytvorené. Nepodporujú metódu Entry.setValue.
Teraz poďme vpred a diskutujme o synchronizovanej stromovej mape. Implementácia stromovej mapy nie je synchronizovaná. To znamená, že ak viaceré vlákna pristupujú k množine stromov súčasne a aspoň jedno z vlákien množinu upravuje, musí byť synchronizovaná externe. To sa zvyčajne dosiahne pomocou metódy Collections.synchronizedSortedMap. Najlepšie je to urobiť v čase vytvorenia, aby ste predišli náhodnému nesynchronizovanému prístupu k súprave. Dá sa to urobiť takto:
SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));>
Geeks, teraz sa musíte pýtať, ako funguje TreeMap interne?
Metódy v stromovej mape pri získavaní sady kľúčov a hodnôt vracajú Iterátor, ktorý je svojou povahou rýchly. Každá súbežná úprava teda vyvolá výnimku ConcurrentModificationException . Stromová mapa je založená na červeno-čiernej stromovej dátovej štruktúre.
Každý uzol v strome má:
- 3 premenné ( K kľúč = kľúč, hodnota V = hodnota, booleovská farba = farba )
- 3 referencie ( Vstup vľavo = ľavý, vstup vpravo = vpravo, vstup rodič = rodič )
Konštruktéri v TreeMap
Aby sme vytvorili TreeMap, musíme vytvoriť objekt triedy TreeMap. Trieda TreeMap pozostáva z rôznych konštruktorov, ktoré umožňujú možné vytvorenie TreeMap. V tejto triede sú dostupné nasledujúce konštruktory:
- TreeMap()
- TreeMap (Comparator comp)
- Stromová mapa (Mapa M)
- Stromová mapa (SortedMap sm)
Poďme o nich diskutovať jednotlivo spolu s implementáciou každého konštruktora takto:
Konštruktor 1: TreeMap()
Tento konštruktor sa používa na vytvorenie prázdnej stromovej mapy, ktorá bude zoradená podľa prirodzeného poradia jej kľúčov.
Príklad
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();> >}> }> |
>
>Výkon
TreeMap using TreeMap() constructor: TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}> Konštruktor 2: TreeMap (Comparator comp)
Tento konštruktor sa používa na vytvorenie prázdneho objektu TreeMap, v ktorom budú prvky potrebovať externú špecifikáciu poradia triedenia.
Príklad
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();> >}> }> |
>
>Výkon
TreeMap using TreeMap(Comparator) constructor: TreeMap: {111 bbbb london=2, 121 cccc jaipur=1, 131 aaaa nyc=3}> Konštruktor 3: Stromová mapa (Mapa M)
Tento konštruktor sa používa na inicializáciu TreeMap s položkami z danej mapy M, ktoré budú zoradené podľa prirodzeného poradia klávesov.
Príklad
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();> >}> }> |
>
>Výkon
TreeMap using TreeMap(Map) constructor: TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}> Konštruktor 4: Stromová mapa (SortedMap sm)
Tento konštruktor sa používa na inicializáciu TreeMap so záznamami z danej zoradenej mapy, ktoré budú uložené v rovnakom poradí ako daná zoradená mapa.
Príklad
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();> >}> }> |
>
>Výkon
TreeMap using TreeMap(SortedMap) constructor: TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}> Metódy v triede TreeMap
| Metóda | Akcia vykonaná |
|---|---|
| jasný() | Metóda odstráni všetky mapovania z tejto stromovej mapy a vymaže mapu. |
| klon() | Metóda vráti plytkú kópiu tejto stromovej mapy. |
| obsahuje kľúč (kľúč objektu) | Vráti hodnotu true, ak táto mapa obsahuje mapovanie pre zadaný kľúč. |
| obsahujeValue(hodnota objektu) | Vráti hodnotu true, ak táto mapa mapuje jeden alebo viac kľúčov na zadanú hodnotu. |
| entrySet() | Vráti nastavený pohľad na mapovania obsiahnuté v tejto mape. |
| firstKey() | Vráti prvý (najnižší) kľúč aktuálne v tejto zoradenej mape. |
| get (kľúč objektu) | Vráti hodnotu, na ktorú táto mapa mapuje zadaný kľúč. |
| headMap(hodnota kľúča objektu) | Metóda vráti pohľad na časť mapy striktne menšiu ako parameter key_value. |
| keySet() | Metóda vráti pohľad Set kľúčov obsiahnutých v stromovej mape. |
| lastKey() | Vráti posledný (najvyšší) kľúč aktuálne v tejto zoradenej mape. |
| put (kľúč objektu, hodnota objektu) | Metóda sa používa na vloženie mapovania do mapy. |
| putAll (mapa mapy) | Skopíruje všetky mapovania zo zadanej mapy do tejto mapy. |
| odstrániť (kľúč objektu) | Odstráni mapovanie pre tento kľúč z tejto stromovej mapy, ak existuje. |
| veľkosť () | Vráti počet mapovaní kľúč – hodnota v tejto mape. |
| subMap((K startKey, K endKey) | Metóda vráti časť tejto mapy, ktorej kľúče sú v rozsahu od startKey, vrátane, po endKey, exkluzívne. |
| hodnoty() | Vráti zobrazenie kolekcie hodnôt obsiahnutých v tejto mape. |
Implementácia: Nasledujúce programy vám lepšie ukážu, ako vytvoriť, vložiť a prechádzať cez stromovú mapu.
Ilustrácia:
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();> >}> }> |
>
>Výkon
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> Vykonávanie rôznych operácií na TreeMap
Po zavedení Generics v Jave 1.5 je možné obmedziť typ objektu, ktorý je možné uložiť do TreeMap. Teraz sa pozrime, ako vykonať niekoľko často používaných operácií na stromovej mape.
Operácia 1: Pridávanie prvkov
Na pridanie prvku do stromovej mapy môžeme použiť metódu put() . Poradie vloženia sa však v stromovej mape nezachová. Interne sa kľúče pre každý prvok porovnávajú a triedia vo vzostupnom poradí.
Príklad
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);> >}> }> |
>
>Výkon
{1=Geeks, 2=For, 3=Geeks} {1=Geeks, 2=For, 3=Geeks}> Operácia 2: Zmena prvkov
Po pridaní prvkov, ak chceme prvok zmeniť, môžeme to urobiť opätovným pridaním prvku pomocou metódy put() . Keďže prvky v stromovej mape sú indexované pomocou kľúčov, hodnotu kľúča je možné zmeniť jednoduchým vložením aktualizovanej hodnoty pre kľúč, ktorý chceme zmeniť.
Príklad
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);> >}> }> |
>
>Výkon
{1=Geeks, 2=Geeks, 3=Geeks} {1=Geeks, 2=For, 3=Geeks}> Operácia 3: Odstraňuje sa prvok
Na odstránenie prvku zo stromovej mapy môžeme použiť metódu remove() . Táto metóda prevezme hodnotu kľúča a odstráni mapovanie kľúča z tejto stromovej mapy, ak sa na mape nachádza.
Príklad
Java
python sort dictionary
// 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);> >}> }> |
>
>Výkon
{1=Geeks, 2=Geeks, 3=Geeks, 4=For} {1=Geeks, 2=Geeks, 3=Geeks}> Operácia 4: Iterácia cez TreeMap
Existuje niekoľko spôsobov, ako iterovať cez mapu. Najznámejším spôsobom je použitie a pre každú slučku a získajte kľúče. Hodnota kľúča sa zistí pomocou getValue() metóda .
Príklad
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);> >}> >}> }> |
>
>Výkon
1 : Geeks 2 : For 3 : Geeks>
Výhody TreeMap:
- Usporiadané poradie: Stromová mapa poskytuje zoradené poradie svojich prvkov na základe prirodzeného poradia svojich kľúčov alebo vlastného porovnávača odovzdaného konštruktorovi. To je užitočné v situáciách, keď potrebujete získať prvky v určitom poradí.
- Predvídateľné poradie iterácií: Pretože prvky v stromovej mape sú uložené v zoradenom poradí, môžete predpovedať poradie, v ktorom sa vrátia počas iterácie, čo uľahčuje písanie algoritmov, ktoré spracovávajú prvky v špecifickom poradí.
- Výkon vyhľadávania: TreeMap poskytuje efektívnu implementáciu rozhrania mapy, ktorá vám umožňuje získavať prvky v logaritmickom čase, vďaka čomu je užitočná pri vyhľadávacích algoritmoch, kde potrebujete prvky rýchlo získať.
- Samovyvažovanie: TreeMap sa implementuje pomocou červeno-čierneho stromu, čo je typ samovyvažujúceho binárneho vyhľadávacieho stromu. To poskytuje efektívny výkon pri pridávaní, odstraňovaní a získavaní prvkov, ako aj pri udržiavaní zoradeného poradia prvkov.
Nevýhody TreeMap:
- Pomalé vkladanie prvkov: Vkladanie prvkov do stromovej mapy môže byť pomalšie ako vkladanie prvkov do bežnej mapy, pretože stromová mapa musí zachovať zoradené poradie svojich prvkov.
- Obmedzenie kľúča: Kľúče v stromovej mape musia implementovať rozhranie java.lang.Comparable alebo musí byť poskytnutý vlastný komparátor. Toto môže byť obmedzenie, ak potrebujete použiť vlastné kľúče, ktoré neimplementujú toto rozhranie.
Referenčná literatúra:
Java Collections od Mauricea Naftalina a Philipa Wadlera. Táto kniha poskytuje komplexný prehľad o rámci Java Collections, vrátane stromovej mapy.
Java v kocke od Davida Flanagana. Táto kniha poskytuje rýchlu referenciu o základných funkciách Java, vrátane stromovej mapy.
Java Generics and Collections od Mauricea Naftalina a Philipa Wadlera. Táto kniha poskytuje komplexného sprievodcu generikami a zbierkami v jazyku Java, vrátane stromovej mapy.