자바의 트리셋

Java는 요소 컬렉션을 효율적으로 사용하기 위한 광범위한 데이터 구조 세트를 제공합니다. 그러한 데이터 구조 중 하나는 Java에서 레드-블랙 트리를 구현한 TreeSet입니다. TreeSet은 고유한 요소를 저장하기 위해 정렬된 순서를 유지합니다. 초보자는 처음에는 Java TreeSet 클래스를 사용하는 것이 약간 어려울 수 있습니다. 이 기사에서는 TreeSet을 사용하는 방법을 알아보고 , 핵심 개념을 설명하고, Java 프로젝트에 TreeSet을 통합하는 데 도움이 되는 코드 예제를 제공합니다.

TreeSet 구조: 레드-블랙 트리

앞서 언급했듯이 Java TreeSet 클래스 구조는 Red-Black 트리로 알려진 자체 균형 이진 검색 트리로 구현됩니다. 이것이 무엇인지 설명해 보겠습니다... 레드-블랙 트리는 정렬된 데이터를 저장하고 구성하는 데 일반적으로 사용되는 균형 잡힌 이진 검색 데이터 구조를 나타냅니다. 균형을 유지하는 속성에서 이름이 유래되었습니다.

• 트리의 각 노드는 빨간색이거나 검은색입니다.
• Red-Black 트리의 루트는 항상 검은색입니다.
• 모든 리프 노드(NIL 노드 또는 null 링크)는 검정색입니다.
• 트리의 노드가 빨간색이면 그 자식은 검정색입니다.
• 노드에서 하위 노드까지의 모든 단순 경로에는 동일한 수의 검정색 노드가 포함됩니다.

레드-블랙 트리는 균형을 보장하여 삽입, 삭제 및 요소 조회 작업에 효율적인 성능을 나타냅니다. 이는 트리의 높이가 포함된 노드 수의 로그에 비례하여 유지되어 작업에 대한 로그 시간 복잡도가 발생함을 보장합니다. 레드-블랙 트리는 프로그래밍 언어, 데이터베이스(예: 내부 인덱스 구조) 및 정렬된 데이터에 대한 효율적인 저장 및 작업이 필요한 기타 시나리오의 균형 검색 트리 구현을 포함하여 다양한 도메인에서 폭넓게 적용됩니다.

TreeSet의 특징과 약점

TreeSet은 정렬된 방식으로 개체 컬렉션을 관리하는 데 유용한 도구로 만드는 몇 가지 주요 기능을 제공합니다. 장점:

• 정렬된 순서로 요소를 자동으로 유지 관리합니다. 요소를 추가하거나 제거하면 정렬된 상태를 유지하도록 트리 구조가 조정됩니다. 이를 통해 수동으로 정렬할 필요가 없으며 오름차순 또는 내림차순으로 효율적으로 액세스할 수 있습니다.
• 효율적인 검색, 삽입 및 삭제 작업. 이는 이진 검색 트리 구조를 활용하여 O(log N) 의 시간 복잡도로 이러한 작업을 가능하게 합니다 . 여기서 N은 요소의 개수입니다.
• TreeSet은 자연 순서 또는 사용자 정의 Comparator를 활용하여 요소의 고유성을 보장합니다 . 이는 고유한 요소가 필요한 컬렉션으로 작업할 때 유용합니다.

제한사항:

• 정렬된 순서를 유지하기 때문에 HashSet 보다 약간 느립니다 .
• 요소 비교를 위해 자연 순서 또는 사용자 정의 비교기 에 의존하므로 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]

여기서는 add() 메소드를 사용하여 TreeSet 에 4개의 숫자를 추가합니다 . 메인 메소드를 생성 하고 프로그램을 실행하면 출력은 정렬된 순서(2, 7, 18, 28)로 표시됩니다. TreeSet 에서 요소 제거 :

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 에 요소가 있는지 확인 중 :

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 의 크기 얻기 :

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: 4

TreeSet의 정렬 및 반복

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]
  }
}

위 코드에서는 Integer 유형의 TreeSet을 생성하고 Comparator.reverseOrder()를 사용하여 요소를 내림차순으로 정렬하는 사용자 지정 Comparator를 제공합니다. 결과 TreeSet에는 [7, 5, 3, 1] 요소가 포함됩니다 . TreeSet 을 반복하는 방법에는 여러 가지가 있습니다 . 반복자를 사용하거나 향상된 for-each 루프를 활용할 수 있습니다. 두 가지 접근 방식의 예를 살펴보겠습니다.

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);
    }
  }
}

위 코드에서는 names라는 TreeSet을 만들고 일부 요소를 추가합니다. 그런 다음 TreeSet을 반복하는 두 가지 방법 , 즉 반복자를 사용하고 향상된 for-each 루프를 활용하는 방법을 보여줍니다. TreeSet은 범위 기반 검색을 수행하는 메서드를 제공하므로 특정 기준에 따라 요소의 하위 집합을 검색할 수 있습니다. 범위 기반 검색의 세 가지 주요 방법은 다음과 같습니다.

• 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을 만들고 몇 가지 요소를 추가합니다. 그런 다음 subSet() , headSet() 및 tailSet() 메서드를 사용하여 범위 기반 검색을 보여줍니다 .

• 하위 집합 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());
  }
}

위 코드에서는 LengthComparator 라는 사용자 정의 비교기를 사용하여 names라는 TreeSet을 만듭니다 . LengthComparator 는 두 문자열의 길이를 비교하고 그에 따라 정렬합니다. 결과적으로 TreeSet은 문자열 길이를 기준으로 정렬되어 [Ivy, Rick, David, Johnny] 출력을 제공합니다 .

비교기를 사용한 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]
    }
  }

위 코드에서는 names라는 TreeSet을 만들고 일부 요소를 추가합니다. 그런 다음 사용자 정의 비교기 Comparator.reverseOrder()를 사용하여 sortedNames 라는 새 TreeSet을 만듭니다 . 원래 이름인 TreeSet 의 모든 요소를 ​​sortedNames 에 추가하여 TreeSet 의 임시 정렬 버전을 얻습니다 .

TreeSet을 다른 데이터 구조와 비교

TreeSet과 HashSet 비교

TreeSet 과 HashSet은 모두 Java에서 Set 인터페이스를 구현한 것입니다 . 그러나 그들 사이에는 상당한 차이가 있습니다. TreeSet : TreeSet은 고유한 요소를 정렬된 순서로 저장합니다. 자체 균형 이진 검색 트리(일반적으로 Red-Black 트리)를 사용하여 정렬된 순서를 유지하므로 삽입, 삭제 및 검색과 같은 작업에 로그 시간 복잡성이 발생합니다. TreeSet은 정렬된 컬렉션을 유지하고 범위 기반 작업을 수행하는 데 효율적입니다. 그러나 트리 구조로 인해 메모리 오버헤드가 높으며 null 요소를 허용하지 않습니다. HashSet : HashSet은 내부적으로 해시 코드와 해시 테이블을 사용하여 고유한 요소를 순서 없이 저장합니다. 삽입, 삭제, 검색과 같은 기본 작업에 지속적인 시간 복잡성을 제공합니다. HashSet은 빠른 요소 조회에 효율적이며 순서 유지를 위해 추가 메모리 오버헤드를 부과하지 않습니다. 그러나 요소의 특정 순서를 보장하지는 않습니다.

TreeSet을 사용하는 경우:

• 자동으로 정렬된 순서로 요소를 유지해야 하는 경우.
• 범위 기반 작업이 필요하거나 특정 범위 내의 요소를 효율적으로 찾아야 하는 경우.
• 중복 요소가 허용되지 않고 고유성이 필수적인 경우.
• 자동 정렬 및 범위 작업의 이점을 위해 약간 더 높은 메모리 사용량을 기꺼이 포기하려는 경우.

TreeSet과 ArrayList 비교

ArrayList 는 Java의 동적 배열 구현입니다. TreeSet 과 ArrayList 의 주요 차이점은 다음과 같습니다 .

• TreeSet : TreeSet은 고유 요소를 정렬된 순서로 저장하여 정렬된 컬렉션을 유지하고 범위 기반 검색을 수행하기 위한 효율적인 작업을 제공합니다. 작업에는 로그 시간 복잡도가 있습니다. TreeSet은 임의 액세스나 삽입 순서 유지에 적합하지 않습니다.
• ArrayList : ArrayList는 삽입 순서대로 요소를 저장하므로 인덱스를 사용하여 요소에 대한 빠른 무작위 액세스를 제공합니다. 인덱스로 요소에 액세스할 때 대부분의 작업에 대해 일정한 시간 복잡도가 있습니다. 그러나 목록 중간에 요소를 삽입하거나 제거하려면 요소 이동이 필요하므로 선형 시간 복잡도가 있습니다.

다른 데이터 구조를 고려해야 하는 경우

• 요소를 정렬된 순서로 유지 관리할 필요가 없고 빠른 요소 검색이나 순서가 지정되지 않은 컬렉션이 필요한 경우 HashSet이 더 나은 선택일 수 있습니다.
• 인덱스별로 요소에 자주 무작위로 액세스해야 하거나 삽입 순서를 유지해야 하는 경우 ArrayList가 더 적합합니다.