Binary Search Tree: JAVA에서의 활용을 위주로

(https://baaaaaaaaaaaaaaaaaaaaaaarkingdog.tistory.com/1013의 내용을 위주로, JAVA에서의 활용을 보완하여 작성하였다.)

 

정의

• 이진 트리: 자식 노드가 2개 이하인 트리
• root, parent, child, leaf, subtree 등...의 용어: 모르면 공부하고, 알면 한 번 스스로 정의를 말해보면서 복습하자.
• 이진 검색 트리: 이진 트리이면서 모든 노드에 대해, 해당 노드의 왼쪽 서브트리의 모든 노드는 해당 노드보다 작고, 해당 노드의 오른쪽 서브트리의 모든 노드는 해당 노드보다 큰 트리

 

성질

• insert, search, update, delete가 모두 O(logN): 다만, 좀 무거운 연산이다.
• 원소가 크기 순으로 정렬되어 있음. → HashMap, PriorityQueue 등에 비해 갖는 차별점이자, 사용하는 이유

 

각 연산의 기본 원리

• insert: 넣는 값이랑 현재 위치의 노드값이랑 비교해서 작으면 왼쪽, 크면 오른쪽으로 간다.
• search: insert랑 비슷한 원리로 찾기
• erase
  • 자식 노드가 없을 때: 바로 지우면 끝
  • 자식 노드가 1개 있을 때: 지우고, 자식 노드를 이어붙임
  • 자식 노드가 2개 있을 때: 오른쪽 서브트리에서 가장 왼쪽에 있는 노드를 가지고와 현재 위치에 붙이고 삭제, 떨어진 부분이 있으면 보완

 

구현

앞서 언급한 모든 연산이 O(logN)의 시간복잡도를 가지려면 '원소가 골고루 퍼져있어야'한다. 이렇게 되도록 스스로 균형을 잡는 트리를 자가 균형 트리(self-balancing tree)라고 한다. 자가 균형 트리에는 AVL Tree, Red Black Tree 등이 있다. 다만 이 구현은 코딩테스트에서 미리 만들어둔 template를 복사하는게 아니면 시간 내 구현하기 매우 어려우므로, 구현보다는 library를 활용한 문제 풀이에서의 사용에 집중하도록 하자.

 

JAVA에서의 이진 검색 트리: TreeSet, TreeMap

TreeSet

TreeSet<Integer> tree = new TreeSet<>();
		
// 큰 원소가 가장 앞에: 큰 의미는 없다.
TreeSet<Integer> tree2 = new TreeSet<>(Collections.reverseOrder());

// 숫자 추가
tree.add(1);
tree.add(2);
tree.add(4);

// 숫자 조회: 맨 앞, 맨 뒤
tree.first(); // 1
tree.last(); // 4

// 해당 숫자보다 크거나 같은 가장 작은 원소
tree.ceiling(2); // 2
tree.ceiling(3); // 4
// 해당 숫자보다 작거나 같은 가장 큰 원소
tree.floor(2); // 2

// 해당 숫자보다 큰 가장 작은 원소
tree.higher(2); // 4
// 해당 숫자보다 작은 가장 큰 원소
tree.lower(3); // 2

// 포함하는가?
tree.contains(1); // true
tree.contains(3); // false

// tree의 크기
tree.size(); // 3

// tree에서 원소 제거
tree.remove(2); // true;
tree.remove(3); // 없는 원소를 제거하려고 함: return false

tree.add(10);
tree.add(11);

// iteration: for문 써도 된다는 정도 알아두자.
for (int x: tree) {
    System.out.printf(x+" "); // 1 4 10 11
}

// tree에서 첫 번째, 마지막 원소 빼기
tree.pollFirst(); // 1
tree.pollLast(); // 11

// tree 초기화
tree.clear();

 

TreeMap

TreeMap<Integer, Integer> map = new TreeMap<>();
		
// 추가하기
map.put(1, 1);
map.put(2, 2);
map.put(3, 4);

// key로 value 조회
map.get(1); // 1
map.get(3); // 4

// 첫 번째, 마지막 key 조회
map.firstKey();
map.lastKey();

// 해당 key보다 큰 가장 작은 key
map.higherKey(1); // 2
map.higherKey(2); // 3

// 해당 key보다 작은 가장 큰 key
map.lowerKey(2); // 1

// 해당 key, value를 포함하는가?
map.containsKey(3); // false
map.containsValue(4); // true, 다만 O(N)이라 사용 자제

// TreeMap의 크기
map.size();

// map에서 key로 원소 제거
map.remove(1);
map.remove(1); // false return

map.put(10, 10);
map.put(11, 100);

// iteration: Entry도 있음
for (int key: map.keySet()) {
    System.out.printf(map.get(key)+" "); // 2 4 10 100
}
for (Entry<Integer, Integer> entry: map.entrySet()) {
    System.out.printf(entry.getKey()+", "+entry.getValue()+" | ");
    // 2, 2 | 3, 4 | 10, 10 | 11, 100 |
}

// tree에서 첫 번째, 마지막 원소 추출
map.pollFirstEntry();
map.pollLastEntry();

// map 비우기
map.clear();

 

애석하게도(?) JAVA의 기본 lilbrary에는 C++에서 'multiset'라고 부르는, TreeSet이되 중복 원소를 포함하는 class는 없다. 하지만, 해당 원소가 몇 번 등장했는지는 따로 세어, (n, 0), (n, 1), (n, 2) ... 와 같이 pair로 저장할 수 있다. TreeSet은 순서가 있으니 순서만 정의하면 된다.

 

 

문제집

바킹독 선생님의 초이스

https://github.com/encrypted-def/basic-algo-lecture/blob/master/workbook/0x16.md