Для реалізації використовується TreeMap у Java Інтерфейс карти і NavigableMap разом із класом AbstractMap. Карта сортується відповідно до природного порядку її ключів або за a компаратор надається під час створення карти, залежно від того, який конструктор використовується. Це виявляється ефективним способом сортування та зберігання пар ключ-значення. Порядок зберігання, який підтримується деревовидною картою, має бути узгодженим із рівними, як і будь-яка інша відсортована карта, незалежно від явних компараторів. Реалізація карти дерева не синхронізована в тому сенсі, що якщо до карти одночасно звертаються кілька потоків і принаймні один із потоків структурно змінює карту, її потрібно синхронізувати зовні.
TreeMap в Java є конкретною реалізацією інтерфейсу java.util.SortedMap. Він надає впорядковану колекцію пар ключ-значення, де ключі впорядковані на основі їх природного порядку або спеціального компаратора, переданого конструктору.
TreeMap реалізовано за допомогою червоно-чорного дерева, яке є типом самобалансуючого бінарного дерева пошуку. Це забезпечує ефективну продуктивність для типових операцій, таких як додавання, видалення та отримання елементів із середньою складністю часу O(log n).
Ось приклад використання класу 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));> >}> >}> }> |
>
>Вихід
Value of A: 1 Key: A, Value: 1 Key: C, Value: 3>
Особливості TreeMap
Деякі важливі функції карти дерева:
- Цей клас є членом Колекції Java Каркас.
- Клас реалізує Інтерфейси карти включаючи NavigableMap, SortedMap і розширює клас AbstractMap.
- TreeMap у Java не допускає нульових ключів (наприклад, Map), тому виникає виняткова ситуація NullPointerException. Однак кілька нульових значень можуть бути пов’язані з різними ключами.
- Пари записів, які повертаються методами в цьому класі, і його перегляди представляють знімки відображень на момент їх створення. Вони не підтримують метод Entry.setValue.
Тепер давайте рухатися вперед і обговорювати Synchronized TreeMap. Реалізація TreeMap не синхронізована. Це означає, що якщо кілька потоків одночасно отримують доступ до дерева, і принаймні один із потоків змінює набір, його потрібно синхронізувати зовні. Зазвичай це досягається за допомогою методу Collections.synchronizedSortedMap. Найкраще це робити під час створення, щоб запобігти випадковому несинхронізованому доступу до набору. Це можна зробити так:
SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));>
Виродки, тепер вам, мабуть, цікаво, як TreeMap працює всередині?
Методи в TreeMap під час отримання набору ключів і значень повертають ітератор, який є безвідмовним за своєю природою. Таким чином, будь-яка одночасна модифікація викличе ConcurrentModificationException. TreeMap базується на структурі даних червоно-чорного дерева.
Кожен вузол у дереві має:
- 3 Змінні ( K key=Ключ, V value=Значення, boolean color=Колір )
- 3 Література ( Вхід ліворуч = Ліворуч, Вхід праворуч = Праворуч, Вхід parent = Батько )
Конструктори в TreeMap
Щоб створити TreeMap, нам потрібно створити об’єкт класу TreeMap. Клас TreeMap складається з різних конструкторів, які дозволяють можливе створення TreeMap. У цьому класі доступні такі конструктори:
- TreeMap()
- TreeMap (компаратор)
- TreeMap (карта M)
- TreeMap(SortedMap sm)
Давайте обговоримо їх окремо разом із реалізацією кожного конструктора наступним чином:
Конструктор 1: TreeMap()
Цей конструктор використовується для створення порожньої карти дерева, яка буде відсортована за природним порядком її ключів.
приклад
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();> >}> }> |
>
>Вихід
TreeMap using TreeMap() constructor: TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}> Конструктор 2: TreeMap (компаратор)
Цей конструктор використовується для створення порожнього об’єкта TreeMap, для елементів якого потрібна буде зовнішня специфікація порядку сортування.
приклад
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();> >}> }> |
>
>Вихід
TreeMap using TreeMap(Comparator) constructor: TreeMap: {111 bbbb london=2, 121 cccc jaipur=1, 131 aaaa nyc=3}> Конструктор 3: TreeMap (карта M)
Цей конструктор використовується для ініціалізації TreeMap записами з даної карти M, які будуть відсортовані за допомогою природного порядку ключів.
приклад
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();> >}> }> |
>
>Вихід
TreeMap using TreeMap(Map) constructor: TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}> Конструктор 4: TreeMap(SortedMap sm)
Цей конструктор використовується для ініціалізації TreeMap записами з заданої відсортованої карти, які зберігатимуться в тому ж порядку, що й дана відсортована карта.
приклад
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();> >}> }> |
>
>Вихід
TreeMap using TreeMap(SortedMap) constructor: TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}> Методи в класі TreeMap
| метод | Дія виконана |
|---|---|
| очистити() | Метод видаляє всі відображення з цього TreeMap і очищає карту. |
| клонувати() | Метод повертає поверхневу копію цього TreeMap. |
| містить ключ (ключ об'єкта) | Повертає true, якщо ця карта містить відображення для вказаного ключа. |
| containsValue(значення об'єкта) | Повертає true, якщо ця карта зіставляє один або кілька ключів із вказаним значенням. |
| entrySet() | Повертає набір відображень, які містяться на цій карті. |
| firstKey() | Повертає перший (найнижчий) ключ на даний момент у цій відсортованій карті. |
| отримати (ключ об'єкта) | Повертає значення, якому ця карта відображає вказаний ключ. |
| headMap(ключ_значення об'єкта) | Метод повертає вигляд частини карти, яка строго менша за параметр key_value. |
| keySet() | Метод повертає представлення Set ключів, що містяться в карті дерева. |
| lastKey() | Повертає останній (найвищий) ключ на цій відсортованій карті. |
| put(ключ об'єкта, значення об'єкта) | Метод використовується для вставки відображення в карту. |
| putAll (карта карти) | Копіює всі зіставлення з указаної карти на цю карту. |
| видалити (ключ об'єкта) | Видаляє зіставлення для цього ключа з цієї TreeMap, якщо воно є. |
| розмір() | Повертає кількість зіставлень ключ-значення в цій карті. |
| subMap((K startKey, K endKey) | Метод повертає частину цієї карти, ключі якої варіюються від startKey, включно, до endKey, винятково. |
| значення() | Повертає перегляд колекції значень, які містяться на цій карті. |
Реалізація: Наведені нижче програми краще продемонструють, як створювати, вставляти та переглядати TreeMap.
Ілюстрація:
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();> >}> }> |
>
>Вихід
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> Виконання різних операцій на TreeMap
Після появи Generics у Java 1.5 можна обмежити тип об’єкта, який можна зберігати в TreeMap. Тепер давайте подивимося, як виконувати кілька часто використовуваних операцій на TreeMap.
Операція 1: Додавання елементів
Щоб додати елемент до TreeMap, ми можемо використати метод put(). Однак порядок вставки не зберігається в TreeMap. Внутрішньо для кожного елемента ключі порівнюються та сортуються в порядку зростання.
приклад
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);> >}> }> |
>
>Вихід
{1=Geeks, 2=For, 3=Geeks} {1=Geeks, 2=For, 3=Geeks}> Операція 2: Зміна елементів
Після додавання елементів, якщо ми хочемо змінити елемент, це можна зробити, знову додавши елемент за допомогою методу put(). Оскільки елементи у карті дерева індексуються за допомогою ключів, значення ключа можна змінити, просто вставивши оновлене значення для ключа, для якого ми хочемо змінити.
приклад
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);> >}> }> |
>
>Вихід
{1=Geeks, 2=Geeks, 3=Geeks} {1=Geeks, 2=For, 3=Geeks}> Операція 3: Видалення елемента
Щоб видалити елемент із TreeMap, ми можемо використати метод remove(). Цей метод приймає значення ключа та видаляє відображення для ключа з цієї деревоподібної карти, якщо він присутній у карті.
приклад
Java
загальність у java
// 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);> >}> }> |
>
>Вихід
{1=Geeks, 2=Geeks, 3=Geeks, 4=For} {1=Geeks, 2=Geeks, 3=Geeks}> Операція 4: Ітерація TreeMap
Існує кілька способів ітерації по карті. Найвідомішим способом є використання a для кожного циклу і отримати ключі. Значення ключа можна знайти за допомогою метод getValue(). .
приклад
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);> >}> >}> }> |
>
>Вихід
1 : Geeks 2 : For 3 : Geeks>
Переваги TreeMap:
- Відсортований порядок: TreeMap забезпечує відсортований порядок своїх елементів на основі природного порядку його ключів або спеціального компаратора, переданого конструктору. Це робить його корисним у ситуаціях, коли потрібно отримати елементи в певному порядку.
- Передбачуваний порядок ітерації: оскільки елементи в TreeMap зберігаються в відсортованому порядку, ви можете передбачити порядок, у якому вони повертатимуться під час ітерації, що полегшує написання алгоритмів, які обробляють елементи в певному порядку.
- Ефективність пошуку: TreeMap забезпечує ефективну реалізацію інтерфейсу Map, що дозволяє отримувати елементи за логарифмічний час, що робить його корисним у пошукових алгоритмах, де потрібно швидко отримувати елементи.
- Самобалансування: TreeMap реалізовано за допомогою червоно-чорного дерева, яке є типом самобалансованого бінарного дерева пошуку. Це забезпечує ефективну продуктивність для додавання, видалення та отримання елементів, а також збереження впорядкованого порядку елементів.
Недоліки TreeMap:
- Повільне вставлення елементів: вставлення елементів у TreeMap може бути повільнішим, ніж у звичайну карту, оскільки TreeMap має підтримувати впорядкований порядок своїх елементів.
- Обмеження щодо ключа: ключі в TreeMap мають реалізовувати інтерфейс java.lang.Comparable або має бути надано спеціальний компаратор. Це може бути обмеженням, якщо вам потрібно використовувати власні ключі, які не реалізують цей інтерфейс.
Довідники:
Колекції Java від Моріса Нафталіна та Філіпа Уодлера. У цій книзі представлено вичерпний огляд структури Java Collections, включаючи TreeMap.
Java in Nutshell Девід Фланаган. У цій книзі наведено коротку довідку про основні функції Java, включаючи TreeMap.
Java Generics and Collections by Maurice Naftalin і Philip Wadler. У цій книзі міститься вичерпний посібник із генериків і колекцій у Java, включаючи TreeMap.