Java は、要素コレクションを効率的に操作するための膨大なデータ構造セットを提供します。このようなデータ構造の 1 つは、Java での赤黒ツリーの実装である TreeSet です。TreeSet は、一意の要素を格納するためにソートされた順序を維持します。初心者にとって、Java TreeSetクラスの使用は最初は少し難しいと感じるかもしれません。この記事では、 TreeSet の使用方法を説明し、その中心的な概念を説明し、 Java プロジェクトに TreeSetを組み込むのに役立つコード例を提供します。
![Java university]()
![Java webinar]()
ツリーセット構造: 赤黒ツリー
前に述べたように、Java TreeSetクラス構造は、赤黒ツリーとして知られる自己平衡二分探索ツリーとして実装されます。これが何であるかを説明しましょう... 赤黒ツリーは、並べ替えられたデータを保存および整理するために一般的に使用されるバランスの取れた二分探索データ構造を表します。その名前は、バランスを維持する特性に由来しています。- ツリー内の各ノードは赤または黒です。
- 赤黒木の根元は常に黒いです。
- すべてのリーフ ノード (NIL ノードまたはヌル リンク) は黒です。
- ツリーのノードが赤の場合、その子は黒になります。
- ノードからその子孫ノードへのすべての単純なパスには、同じ数の黒いノードが含まれます。
TreeSet の特徴と弱点
TreeSet は、オブジェクトのコレクションを並べ替えて管理するための貴重なツールとなるいくつかの重要な機能を提供します。利点:- ソートされた順序での要素の自動メンテナンス。要素を追加または削除すると、要素が並べ替えられるようにツリー構造が調整されます。これにより、手動で並べ替える必要がなくなり、昇順または降順で効率的にアクセスできるようになります。
- 効率的な検索、挿入、削除操作。二分探索ツリー構造を利用し、これらの操作をO(log N)の時間計算量で実現します。ここでNは要素の数です。
- TreeSet は、要素の自然な順序付けまたはカスタムComparatorを利用して、要素の一意性を保証します。これは、個別の要素を必要とするコレクションを操作する場合に便利です。
- ソート順を維持するため、HashSetよりもわずかに遅くなります。
- 要素の比較には自然順序付けまたはカスタムComparatorに依存するため、null 要素は許可されません。
Java TreeSet: 主な操作の例
次に、Java でTreeSet を作成し、コレクションのサイズを取得し、コレクションに要素を追加し、要素を削除し、要素がTreeSet内にあるかどうかを確認する方法を示します。これらのコード例は、 TreeSetを操作するときの主な操作(インスタンスの作成、要素の追加、要素の削除、要素の存在の確認、 TreeSetのサイズの取得) を示しています。TreeSetインスタンスの作成と要素の追加:
// Creating a TreeSet of Integer type
TreeSet<Integer> numbers = new TreeSet<>();
// Adding elements to the TreeSet
numbers.add(18);
numbers.add(2);
numbers.add(7);
numbers.add(28);
System.out.println(numbers); // Output: [2, 7, 18, 28]
TreeSet<String> names = new TreeSet<>();
names.add("Johnny");
names.add("Ivy");
names.add("David");
names.add("Ricky");
// Removing an element from the TreeSet
names.remove("David");
System.out.println(names); // Output: [Ivy, Johnny, Ricky]
TreeSet<String> musicalInstrument = new TreeSet<>();
musicalInstrument.add("Piano");
musicalInstrument.add("Drums");
musicalInstrumentfruits.add("Violin");
musicalInstrument.add("Double Bass");
// Checking if an element exists in the TreeSet
boolean containsPiano = musicalInstrument.contains("Piano");
boolean containsCello = musicalInstrument.contains("Cello");
System.out.println(containsPiano); // Output: true
System.out.println(containsCello); // Output: false
TreeSet<Character> letters = new TreeSet<>();
letters.add('A');
letters.add('B');
letters.add('C');
letters.add('D');
// Getting the size of the TreeSet
int size = letters.size();
System.out.println(size); // Output: 4TreeSet での並べ替えと反復
Java のTreeSet は、要素のコレクションを並べ替えたり反復したりするための強力な機能を提供します。このセクションでは、要素の並べ替え、 TreeSet の反復処理、 subSet()、headSet()、およびtailSet()メソッドを使用した範囲ベースの検索の実行に関するさまざまな手法を検討します。デフォルトでは、TreeSet は要素をソート順に自動的に維持します。ただし、 TreeSet の作成中にComparatorを提供することで、並べ替え動作をカスタマイズできます。例を見てみましょう:
import java.util.Comparator;
import java.util.TreeSet;
public class TreeSetSortingExample {
public static void main(String[] args) {
// Create a TreeSet with custom sorting
TreeSet<Integer> numbers = new TreeSet<>(Comparator.reverseOrder());
// Add elements to the TreeSet
numbers.add(5);
numbers.add(3);
numbers.add(7);
numbers.add(1);
System.out.println(numbers); // Output: [7, 5, 3, 1]
}
}
import java.util.TreeSet;
import java.util.Iterator;
public class TreeSetIterationExample {
public static void main(String[] args) {
TreeSet<String> names = new TreeSet<>();
names.add("Johnny");
names.add("Ivy");
names.add("Ricky");
names.add("David");
// Iterating using an iterator
Iterator<String> iterator = names.iterator();
while (iterator.hasNext()) {
String name = iterator.next();
System.out.println(name);
}
// Iterating using the enhanced for-each loop
for (String name : names) {
System.out.println(name);
}
}
}- subSet(E fromElement, E toElement) : fromElement (包含)からtoElement (排他)までの要素のサブセットを返します。
- headSet(E toElement) : toElementより小さい要素のサブセットを返します。
- tailSet(E fromElement) : fromElement以上の要素のサブセットを返します。
import java.util.TreeSet;
public class TreeSetRangeSearchExample {
public static void main(String[] args) {
TreeSet<Integer> numbers = new TreeSet<>();
numbers.add(1);
numbers.add(3);
numbers.add(5);
numbers.add(7);
numbers.add(9);
// Performing range-based search using subSet()
TreeSet<Integer> subset = new TreeSet<>(numbers.subSet(3, 8));
System.out.println(subset); // Output: [3, 5, 7]
// Performing range-based search using headSet()
TreeSet<Integer> headSet = new TreeSet<>(numbers.headSet(6));
System.out.println(headSet); // Output: [1, 3, 5]
// Performing range-based search using tailSet()
TreeSet<Integer> tailSet = new TreeSet<>(numbers.tailSet(5));
System.out.println(tailSet); // Output: [5, 7, 9]
}
}- サブセットTreeSet には 、3 (両端を含む) から 8 (両端を含まない) までの要素( [3, 5, 7] )が含まれます。
- headSet TreeSet には 、6 未満の要素 ( [1, 3, 5] )が含まれています。
- tailSet TreeSetには、5 以上の要素 ( [5, 7, 9] )が 含まれています。
TreeSet のコンパレータ: カスタム基準による並べ替え
自然な順序付けを除き、 TreeSet の並べ替えにカスタムComparatorを使用できます。このセクションでは、コンパレータの概念とTreeSetにおけるその役割について詳しく説明します。カスタム コンパレーターを使用してTreeSetを作成する方法を検討し、特定の基準に基づいてTreeSetを並べ替えるコード例を示します。コンパレータとは何ですか?
Comparatorは、オブジェクトのカスタム並べ替えを可能にする Java のインターフェイスです。これは、特定の属性またはプロパティに基づいて要素の順序を定義する方法を提供します。Comparatorインターフェイスを実装し、そのCompare()メソッドをオーバーライドすることで、 TreeSet内で要素を並べ替える方法を指定できます。カスタム コンパレータを使用した TreeSet の作成
カスタム コンパレータを使用してTreeSetを作成するには、 TreeSetインスタンスの作成時にコンパレータを引数として指定する必要があります。例を見てみましょう:
import java.util.Comparator;
import java.util.TreeSet;
public class TreeSetComparatorExample {
public static void main(String[] args) {
// Create a TreeSet with a custom comparator
TreeSet<String> names = new TreeSet<>(new LengthComparator());
// Add elements to the TreeSet
names.add("Johnny");
names.add("Ivy");
names.add("Rick");
names.add("David");
System.out.println(names); // Output: [Ivy, Johnny, David, Rick]
}
}
class LengthComparator implements Comparator<String> {
@Override
public int compare(String s1, String s2) {
return Integer.compare(s1.length(), s2.length());
}
}コンパレーターを使用した TreeSet のソートの例
カスタム コンパレータを使用してTreeSetを作成する以外に、コンパレータを使用して、自然な順序を変更せずにTreeSetを一時的に並べ替えることもできます。例を見てみましょう:
import java.util.Comparator;
import java.util.TreeSet;
public class TreeSetTest {
public static void main(String[] args) {
TreeSet<String> names = new TreeSet<>();
names.add("Johnny");
names.add("Ivy");
names.add("Ricky");
names.add("David");
// Sort TreeSet temporarily using a comparator
TreeSet<String> sortedNames = new TreeSet<>(Comparator.reverseOrder());
sortedNames.addAll(names);
System.out.println(sortedNames); // Output: [Ricky, Johnny, Ivy, David]
System.out.println(names); // Output: [David, Ivy, Johnny, Ricky]
}
}
TreeSet と他のデータ構造の比較
TreeSet と HashSet の比較
TreeSetとHashSet は両方とも、Java のSetインターフェイスの実装です。ただし、それらの間には大きな違いがあります。 TreeSet : TreeSet は、一意の要素をソート順に格納します。自己平衡型二分探索ツリー (通常は赤黒ツリー) を使用してソート順序を維持するため、挿入、削除、検索などの操作の時間が対数的に複雑になります。TreeSet は、並べ替えられたコレクションを維持し、範囲ベースの操作を実行するのに効率的です。ただし、ツリー構造のためメモリ オーバーヘッドが高く、null 要素は許可されません。 HashSet : HashSet は、内部でハッシュ コードとハッシュテーブルを使用して、順序付けされていない方法で一意の要素を格納します。挿入、削除、検索などの基本的な操作に一定の時間の複雑さを提供します。HashSet は要素の高速検索に効率的であり、順序を維持するために追加のメモリ オーバーヘッドを課すことはありません。ただし、要素の特定の順序は保証されません。TreeSet を使用する場合:
- 要素を自動的にソート順に維持する必要がある場合。
- 範囲ベースの操作が必要な場合、または特定の範囲内の要素を効率的に検索する必要がある場合。
- 重複した要素が許可されず、一意性が重要な場合。
- 自動ソートと範囲操作の利点と引き換えに、メモリ使用量を多少高くしても構わない場合。
TreeSet と ArrayList の比較
ArrayList はJava の動的配列実装です。TreeSetとArrayListの主な違いは次のとおりです。- TreeSet : TreeSet は一意の要素をソートされた順序で保存し、ソートされたコレクションを維持し、範囲ベースの検索を実行するための効率的な操作を提供します。操作には対数的な時間複雑性があります。TreeSet は、ランダム アクセスや挿入順序の維持には適していません。
- ArrayList : ArrayList は要素を挿入順に格納し、インデックスを使用して要素への高速ランダム アクセスを提供します。インデックスによって要素にアクセスする場合、ほとんどの操作の時間計算量は一定です。ただし、リストの途中で要素を挿入または削除するには、要素を移動する必要があるため、線形の時間計算量が必要になります。
他のデータ構造を考慮する場合
- 要素をソートされた順序で維持する必要がなく、高速な要素検索または順序付けされていないコレクションが必要な場合は、HashSet の方が良い選択肢になる可能性があります。
- インデックスによる要素へのランダム アクセスを頻繁に行う必要がある場合、または挿入順序を維持する必要がある場合は、ArrayListの方が適しています。
GO TO FULL VERSION