JAVA のツリーマップ - TECHCODEVIEW.COM

Java の TreeMap は実装に使用されます。マップインターフェース NavigableMap と AbstractMap クラス。マップは、キーの自然な順序に従って、またはコンパレータ使用されるコンストラクターに応じて、マップの作成時に提供されます。これは、キーと値のペアを並べ替えて保存する効率的な方法であることがわかります。ツリーマップによって維持される格納順序は、明示的なコンパレータに関係なく、他の並べ替えられたマップと同様に、equals と一致する必要があります。ツリーマップの実装は、マップが複数のスレッドによって同時にアクセスされ、少なくとも 1 つのスレッドがマップを構造的に変更する場合、外部で同期する必要があるという意味で同期されません。

Java の TreeMap は、java.util.SortedMap インターフェースの具体的な実装です。これは、キーと値のペアの順序付きコレクションを提供します。キーは、自然な順序またはコンストラクターに渡されるカスタム Comparator に基づいて順序付けされます。

TreeMap は、自己平衡型二分探索ツリーの一種である赤黒ツリーを使用して実装されます。これにより、要素の追加、削除、取得などの一般的な操作の効率的なパフォーマンスが提供され、平均時間計算量は O(log n) になります。

TreeMap クラスの使用方法の例を次に示します。

ジャワ

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

ツリーマップの機能

ツリーマップの重要な機能のいくつかは次のとおりです。

このクラスはのメンバーです Java コレクションフレームワーク。
クラスが実装するのは、マップインターフェース NavigableMap 、 SortedMap を含み、 AbstractMap クラスを拡張します。
Java の TreeMap では null キー (Map など) が許可されないため、NullPointerException がスローされます。ただし、複数の null 値を異なるキーに関連付けることはできます。
このクラスとそのビューのメソッドによって返されるエントリペアは、マッピングが作成された時点のスナップショットを表します。 Entry.setValue メソッドはサポートされていません。

それでは、先に進んで、Synchronized TreeMap について説明しましょう。 TreeMap の実装は同期されません。これは、複数のスレッドがツリーセットに同時にアクセスし、少なくとも 1 つのスレッドがセットを変更する場合、外部で同期する必要があることを意味します。これは通常、Collections.synchronizedSortedMap メソッドを使用して実現されます。これは、セットへの偶発的な非同期アクセスを防ぐために、作成時に行うのが最適です。これは次のようにして実行できます。

SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));

マニアの皆さん、TreeMap が内部でどのように動作するのか疑問に思われたのではないでしょうか?

TreeMap 内のメソッドは、キーセットと値を取得する際に、本質的にフェイルファストである Iterator を返します。したがって、同時変更を行うと ConcurrentModificationException がスローされます。 TreeMap は、赤黒ツリーデータ構造に基づいています。

ツリー内の各ノードには次のものがあります。

3 つの変数 ( K key=キー、V value=値、boolean color=カラー )
3 参考文献 ( 左のエントリ = 左、右のエントリ = 右、エントリの親 = 親 )

TreeMap のコンストラクター

TreeMap を作成するには、TreeMap クラスのオブジェクトを作成する必要があります。 TreeMap クラスは、TreeMap の作成を可能にするさまざまなコンストラクターで構成されています。このクラスで使用できるコンストラクターは次のとおりです。

ツリーマップ()
TreeMap(コンパレータコンプ)
ツリーマップ(マップM)
ツリーマップ(ソートマップ sm)

次のようにすべてのコンストラクターを実装しながら、それらについて個別に説明します。

コンストラクター 1: ツリーマップ()

このコンストラクターは、キーの自然な順序を使用して並べ替えられる空のツリーマップを構築するために使用されます。

例

ジャワ

// 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 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: ツリーマップ(マップM)

このコンストラクターは、キーの自然な順序を使用して並べ替えられる、指定されたマップ M からのエントリで TreeMap を初期化するために使用されます。

例

ジャワ

// 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: ツリーマップ(ソートマップ sm)

このコンストラクターは、指定された並べ替えられたマップと同じ順序で保存される、指定された並べ替えられたマップからのエントリで TreeMap を初期化するために使用されます。

例

ジャワ

// 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 の浅いコピーを返します。
containsKey(オブジェクトキー)	このマップに指定されたキーのマッピングが含まれている場合は true を返します。
containsValue(オブジェクト値)	このマップが 1 つ以上のキーを指定された値にマップする場合は true を返します。
エントリーセット()	このマップに含まれるマッピングのセットビューを返します。
firstKey()	このソートされたマップの現在最初の (最も低い) キーを返します。
get(オブジェクトキー)	このマップが指定されたキーをマップする値を返します。
headMap(オブジェクトのkey_value)	このメソッドは、パラメーター key_value より厳密に小さいマップ部分のビューを返します。
キーセット()	このメソッドは、ツリーマップに含まれるキーの Set ビューを返します。
lastKey()	このソートされたマップ内に現在ある最後の (最も高い) キーを返します。
put(オブジェクトキー, オブジェクト値)	このメソッドは、マッピングをマップに挿入するために使用されます。
putAll(地図マップ)	指定されたマップからこのマップにすべてのマッピングをコピーします。
削除(オブジェクトキー)	このキーのマッピングが存在する場合は、この TreeMap から削除します。
サイズ（）	このマップ内のキーと値のマッピングの数を返します。
subMap((K startKey, K endKey)	このメソッドは、キーの範囲が startKey (両端を含む) から endKey (両端を含まない) までであるこのマップの部分を返します。
値()	このマップに含まれる値のコレクションビューを返します。

実装： 以下のプログラムは、TreeMap を作成、挿入、および移動する方法をより適切に示します。

図：

ジャワ

// 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

ツリーマップ上でさまざまな操作を実行する

Java 1.5 でのジェネリックの導入後、TreeMap に格納できるオブジェクトのタイプを制限できるようになりました。次に、ツリーマップ上で頻繁に使用されるいくつかの操作を実行する方法を見てみましょう。

操作 1: 要素の追加

TreeMap に要素を追加するには、put() メソッドを使用します。ただし、挿入順序はツリーマップには保持されません。内部的には、要素ごとにキーが比較され、昇順に並べ替えられます。

例

ジャワ

// 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 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 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: ツリーマップの反復処理

マップを反復処理するには複数の方法があります。最も有名な方法は、 for-each ループそして鍵を入手します。キーの値は、 getValue() メソッド 。

例

ジャワ

// 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 は、キーの自然な順序またはコンストラクターに渡されたカスタム Comparator に基づいて、要素のソートされた順序を提供します。これは、要素を特定の順序で取得する必要がある状況で役立ちます。
予測可能な反復順序: TreeMap 内の要素は並べ替えられた順序で格納されるため、反復中に要素が返される順序を予測でき、特定の順序で要素を処理するアルゴリズムの作成が容易になります。
検索パフォーマンス: TreeMap は Map インターフェイスの効率的な実装を提供し、対数時間で要素を取得できるため、要素を迅速に取得する必要がある検索アルゴリズムで役立ちます。
自己平衡型: TreeMap は、自己平衡型二分探索ツリーの一種である赤黒ツリーを使用して実装されます。これにより、要素の追加、削除、取得の効率的なパフォーマンスが得られるだけでなく、要素の並べ替え順序も維持されます。

ツリーマップの欠点:

要素の挿入が遅い: TreeMap は要素の並べ替え順序を維持する必要があるため、TreeMap への要素の挿入は、通常の Map への要素の挿入よりも遅くなる可能性があります。
キーの制限: TreeMap 内のキーは java.lang.Comparable インターフェイスを実装するか、カスタム Comparator を提供する必要があります。このインターフェイスを実装していないカスタムキーを使用する必要がある場合、これが制限になる可能性があります。