TreeSet, Red-Black Tree

Set interface를 구현한 클래스.

BinarySearchTree(이진탐색트리) 구조로 이루어져 있으며, 그 중에서도 성능을 향상시킨 Red-Black Tree로 구현되어있다.

일반적인 이진탐색트리의 경우, 입력값이 분산되어 들어오지 않고 한 쪽에 치우쳐서, 편향되어서 들어온다면 효율적이지 못하게 된다.

이 문제를 보완한 방식이 레드-블랙 트리이다.

레드-블랙 트리는 부모노드를 기준으로 왼쪽 오른쪽으로 배치해 편향되지 않은 구조가 되도록 한다.

 

• TreeSet 생성
  • TreeSet 생성

  TreeSet<Integer> treeSet = new TreeSet<Integer>();
  

  • TreeSet 생성, 타입 파라미터 생략

  TreeSet<Integer> treeSet = new TreeSet<>();
  

  • treeSet_1의 값을 갖는 TreeSet 생성

  TreeSet<Integer> treeSet = new TreeSet<>(treeSet_1);
  

  
  
  HashSet처럼 선언 시 크기를 지정할 수는 없다.

 

 

• TreeSet 메소드 정리
  • 입력 (add)

  TreeSet<Integer> treeSet = new TreeSet<>();
  treeSet.add(4);
  treeSet.add(2);
  treeSet.add(7);
  treeSet.add(1);
  
  System.out.println(treeSet);
  

  → [1, 2, 4, 7]
  입력값이 TreeSet 안에 없으면 주가하여 true 반환하고
  입력값이 TreeSet 안에 있으면 false 를 반환한다.
  
  
  
  • 삭제 (remove)

  TreeSet<Integer> treeSet = new TreeSet<>();
  treeSet.add(4);
  treeSet.add(2);
  treeSet.add(7);
  treeSet.add(1);
  
  treeSet.remove(1);
  
  System.out.println(treeSet.remove(100));
  System.out.println(treeSet);
  

  → false
  → [2, 4, 7]
  삭제할 값이 TreeSet 안에 있으면 삭제하여 true 반환하고
  삭제할 값이 TreeSet 안에 없으면 false 를 반환한다.
  
  
  
  • 전체 삭제 (clear)

  TreeSet<Integer> treeSet = new TreeSet<>();
  treeSet.add(4);
  treeSet.add(2);
  treeSet.add(7);
  treeSet.add(1);
  
  treeSet.clear();
  
  System.out.println(treeSet);
  

  → []
  
  
  
  • TreeSet 크기 (size)

  TreeSet<Integer> treeSet = new TreeSet<>();
  treeSet.add(4);
  treeSet.add(2);
  treeSet.add(7);
  treeSet.add(1);
  
  System.out.println(treeSet.size());
  

  → 4
  
  
  
  • 전체 출력

  TreeSet<Integer> treeSet = new TreeSet<>();
  treeSet.add(4);
  treeSet.add(2);
  treeSet.add(7);
  treeSet.add(1);
  
  System.out.println(treeSet);
  

  → [1, 2, 4, 7]
  
  
  
  • 최소값 출력

  TreeSet<Integer> treeSet = new TreeSet<>();
  treeSet.add(4);
  treeSet.add(2);
  treeSet.add(7);
  treeSet.add(1);
  
  System.out.println(treeSet.first());
  

  → 1
  
  
  
  • 최대값 출력

  TreeSet<Integer> treeSet = new TreeSet<>();
  treeSet.add(4);
  treeSet.add(2);
  treeSet.add(7);
  treeSet.add(1);
  
  System.out.println(treeSet.last());
  

  → 7
  
  
  
  • 입력값보다 큰 데이터 중 최소값 출력

  TreeSet<Integer> treeSet = new TreeSet<>();
  treeSet.add(4);
  treeSet.add(2);
  treeSet.add(7);
  treeSet.add(1);
  
  System.out.println(treeSet.higher(2));		
  System.out.println(treeSet.higher(7));
  

  → 4
  null
  
  
  
  • 입력값보다 작은 데이터 중 최대값 출력

  TreeSet<Integer> treeSet = new TreeSet<>();
  treeSet.add(4);
  treeSet.add(2);
  treeSet.add(7);
  treeSet.add(1);
  
  System.out.println(treeSet.lower(4));		
  System.out.println(treeSet.lower(1));
  

  → 2
  null