Tree, BinaryTree

트리 (Tree)

Tree 구조는 계층적인 구조를 표현할 수 있는 자료구조이다.

Tree 구조는 루트 노드에서 시작하여 여러개의 하위 노드들이 연결된 형태로 구성되며, 각 노드는 각자의 하위 노드들을 가질 수 있다.

Java에서는 Tree 구조를 구현하기 위해 다음의 인터페이스와 클래스들을 사용한다.

아래 인터페이스와 클래스들은 중복값을 허용하지 않는다.

 

사용 인터페이스

• java.util.Set
  Tree 구조를 구현하기 위한 인터페이스로, 이 인터페이스를 implements 하는 클래스들은 모두 Tree 구조를 갖는다.
  
  
• java.util.SortedSet
  Set 인터페이스를 상속받으며, 정렬된 Tree 구조를 표현하기 위한 인터페이스이다.

사용 클래스

• java.util.TreeSet
  SortedSet 인터페이스를 implements하는 클래스로, 기본적으로 오름차순 정렬이다

 

 

 

 

---

 

 

이진 트리 (BinaryTree)

• 각 노드가 최대 두 개의 자식 노드를 가지는 트리 자료구조이다.
• 이진 트리에서 자식 노드가 없는 노드를 리프(leaf) 노드라고 한다.
• 각 노드는 최대 두 개의 자식 노드를 가질 수 있다.
• 왼쪽 자식 노드는 현재 노드보다 작은 값을, 오른쪽 자식 노드는 현재 노드보다 큰 값을 가진다.
• 왼쪽 서브트리는 현재 노드보다 작은 값의 모임이며, 오른쪽 서브트리는 현재 노드보다 큰 값의 모임이다.

 

이진 탐색 트리 (Binary Search Tree)

• 이진 트리는 탐색(Binary Search)을 위한 자료구조로 많이 사용된다.
• 이진 탐색 트리(Binary Search Tree)는 이진 트리의 한 종류로, 모든 노드가 위의 특징을 만족해야 한다. 이진 탐색 트리에서는 특정 값을 가진 노드를 빠르게 찾을 수 있다.
• Java에서 이진 트리를 구현하려면 TreeNode 클래스와 같은 노드 클래스를 만들고, 노드 클래스를 이용하여 이진 트리를 구현할 수 있다.
• 이진 탐색 트리를 구현하려면, 각 노드가 key-value 쌍을 가지도록 하고, key 값으로 노드를 정렬한다.
• 또한, 삽입(insertion), 삭제(deletion), 탐색(search) 등의 기능을 구현해야 한다.
• 자바에서 이진 트리를 사용하는 방법에는 직접 구현하는 것 외에도 **java.util.TreeMap**과 java.util.TreeSet 클래스를 사용하는 방법이 있다.

 

 

 

---

 

TreeSet

• TreeSet은 이진 검색 트리를 사용하여 원소를 저장한다.
• 이진 검색 트리를 사용하므로 삽입, 삭제, 검색의 시간복잡도는 O(log N) 이다.
• 트리의 각 노드는 Key와 Value를 가지며 노드의 정렬 기준은 Key이다.

 

TreeSet 클래스 생성자

TreeSet 클래스의 생성자는 다음과 같다.

 

• 기본생성자
  빈 TreeSet 객체를 생성한다.

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

 

• Comparator를 인자로 받는 생성자
  지정된 Comparator를 사용하여 원소를 정렬하는 TreeSet 객체를 생성한다.

TreeSet<Integer> treeSet = new TreeSet<>(new Comparator<Integer>() {
		    @Override
		    public int compare(Integer o1, Integer o2) {
		        return o1 - o2;
		    }
		}
);

 

• SortedSet을 인자로 받는 생성자
  주어진 SortedSet의 모든 원소를 포함하는 TreeSet 객체를 생성한다.

SortedSet<Integer> sortedSet = new TreeSet<>();
sortedSet.add(1);
sortedSet.add(2);
sortedSet.add(3);

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

 

• Collection을 인자로 받는 생성자
  주어진 컬렉션의 모든 원소를 포함하는 TreeSet 객체를 생성한다.

List<String> list = new ArrayList<>();
list.add("apple");
list.add("banana");
list.add("cherry");

TreeSet<String> treeSet = new TreeSet<>(list);

 

• 다른 TreeSet을 인자로 받는 생성자

TreeSet<String> originalTreeSet = new TreeSet<>();
originalTreeSet.add("apple");
originalTreeSet.add("banana");
originalTreeSet.add("cherry");

TreeSet<String> newTreeSet = new TreeSet<>(originalTreeSet);

 

TreeSet 메서드

• add(E e)
  주어진 원소를 TreeSet에 추가한다.

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

treeSet.add("apple");
treeSet.add("banana");
treeSet.add("cherry");

 

• contains(Object o)
  주어진 원소가 TreeSet에 포함되어 있는지 여부를 반환한다.

boolean containsBanana = treeSet.contains("banana");
System.out.println("containsBanana: " + containsBanana);
//containsBanana: true

 

• first()
  TreeSet의 가장 작은 원소를 반환한다.

String firstElement = treeSet.first();
System.out.println("firstElement: " + firstElement);
//firstElement: apple

 

• last()
  TreeSet의 가장 큰 원소를 반환한다.

String lastElement = treeSet.last();
System.out.println("lastElement: " + lastElement);
//lastElement: cherry

 

• iterator()
  TreeSet의 iterator를 반환한다.

System.out.print("treeSet: ");
for (String element : treeSet) {
    System.out.print(element + " ");
}
System.out.println();
//treeSet: apple banana cherry

 

• remove(Object o)
  주어진 원소를 TreeSet에서 삭제한다.

treeSet.remove("banana");

 

• size()
  TreeSet의 원소 개수를 반환한다.

int size = treeSet.size();
//size: 2

 

• clear()
  TreeSet의 모든 원소를 삭제한다.

treeSet.clear();

 

• isEmpty()
  TreeSet이 비어 있는지 여부를 반환한다.

boolean isEmpty = treeSet.isEmpty();
System.out.println("isEmpty: " + isEmpty);
//isEmpty: true

 

 

---

 

TreeMap

 

TreeMap 클래스의 생성자

• 기본생성자
  기본 생성자로써 TreeMap 객체를 생성한다. 이때 기본적으로는 key 값들이 정렬되도록 Comparator 를 지정해줘야 한다.

TreeMap<String, Integer> treeMap = new TreeMap<>();

• Comparator를 인자로 받는 생성자
  Comparator 를 사용하여 TreeMap 객체를 생성한다.

TreeMap<String, Integer> treeMap = new TreeMap<>(new Comparator<String>() {
    @Override
    public int compare(String o1, String o2) {
        return o1.compareTo(o2);
    }
});

 

TreeMap 클래스의 주요 메서드

• put(K key, V value)
  key와 value를 TreeMap에 추가한다.

treeMap.put("banana", 5);
treeMap.put("apple", 3);
treeMap.put("cherry", 1);
treeMap.put("dragonfruit", 2);

 

• get(Object key)
  key에 해당하는 value를 반환한다.

Integer value = treeMap.get("banana"); // 5

 

• remove(Object key)
  key에 해당하는 entry를 TreeMap에서 삭제한다.

treeMap.remove("banana");

 

• firstKey()
  TreeMap의 첫번째 key를 반환한다.

String firstKey = treeMap.firstKey(); // "apple"

 

• lastKey()
  TreeMap의 마지막 key를 반환한다.

String lastKey = treeMap.lastKey(); // "dragonfruit"

 

• keySet()
  TreeMap의 key들을 Set 형태로 반환한다.

Set<String> keys = treeMap.keySet();

 

• values()
  TreeMap의 value들을 Collection 형태로 반환한다.

Collection<Integer> values = treeMap.values();

 

• entrySet()
  TreeMap의 entry들을 Set 형태로 반환한다.

Set<Map.Entry<String, Integer>> entries = treeMap.entrySet();

 

• size()
  TreeMap의 크기를 반환한다.

int size = treeMap.size();

 

• isEmpty()
  TreeMap이 비어있는지 여부를 반환한다.

boolean isEmpty = treeMap.isEmpty();

 

• clear()
  TreeMap의 모든 entry를 삭제한다.

boolean isEmpty = treeMap.isEmpty();

 

 

 

---

 

이진 탐색 트리를 꼭 구현해야 할까?

자료구조를 선택할 때는 해당 자료구조가 가지는 특징과 자신이 해결해야 하는 문제의 특성을 고려하여 선택해야 한다.

이진탐색 문제의 경우 TreeSet이나 TreeMap을 사용해 충분히 해결할 수 있다.

원소들의 삽입과 삭제가 빈번하게 일어나지 않기 때문이다.

하지만 반대로 원소들의 삽입과 삭제가 빈번하게 일어나는 경우, TreeSet과 TreeMap은 비교적 느릴 수 있다.

이진트리는 일반적으로 원소 삽입과 삭제 시간 복잡도가 O(log n)이므로, 원소가 많을수록 처리 시간이 늘어난다.