트리는 자식이라 부르는 서로 다른 원소를 많이 나열할 수 있는 자료구조다. 여기서는 트리의 전체 형태를 살피기 보다는 대표되는 형태인 이진 트리에 대해 자세히 보자.([트리 = 이진 트리 or 완전 이진 트리] 가 아님을 생각해야한다.)
이진 트리는 모든 원소가 최대 두개의 자식을 갖는 것을 말한다. 물론 하나이거나 없는 노드도 포함이다. 이진 검색 트리는 이진트리에서 하나의 규칙이 추가된 자료구조다. 부모노드보다 큰 자식노드는 우측, 작은 자식노드는 좌측에 놓는 것이다. 그렇게 되면 루트 노드부터 대상값과 비교하면서 큰지, 작은지만 확인하면 원하는 노드를 O(log n)만큼 걸리게 된다. 말 그대로 탐색에 유리한 자료구조이다. 코드를 보자.
public class SimpleTree<E extends Comparable> {
private E value;
private SimpleTree<E> leftNode;
private SimpleTree<E> rightNode;
// 값 존재유무 확인
public boolean search(final E toFind) {
// 1. 검색하는 값이 해당 노드인지 확인
if (toFind.equals(value)) {
return true;
}
// 2. 검색하는 값이 왼쪽 노드에 있는지 탐색
if (toFind.compareTo(value) < 0 && left != null>) {
return left.search(toFind);
}
// 3. 검색하는 값이 오른쪽 노드에 있는지 탐색
return right != null && right.search(toFind);
}
}
데이터 삽입 절차는 아래와 같다.
- 루트 노드와 입력된 값을 비교한다.
- 루트노드보다 작으면 왼쪽, 크면 오른쪽 자식으로 이동한다.
- 1~2번을 반복하면서 이동하려는 자식노드가 비워져 있다면 입력값은 해당 위치에 저장한다.
코드로 살펴보자
public class SimpleTree<E extends Comparable> {
// ... 위 코드는 생략
// 트리에 값 입력
public void insert(final E toInsert) {
// 해당 노드와 입력할 값을 비교하여 작다면 left, 크다면 right로 전달
if (toInsert.compareTo(value) < 0) {
// left가 없으면 입력된 값을 left로 설정
if (left == null) {
left = new SimpleTree<>(toInsert, null, null);
}
else {
left.insert(toInsert);
}
}
else {
// right가 없으면 입력된 값을 right로 설정
if (right == null) {
right = new SimpleTree<>(toInsert, null, null);
}
else {
right.insert(toInsert);
}
}
}
}
만약 면접 중에 트리를 구현해야 한다면, 전체 코드를 외우기 보다 구두로 적은 풀이방법을 기억하여 코드로 구현하는 편이 성공률이 높을 것이다.
책에서는 Null 객체로 트리를 구성하는 방법을 이야기하지만 '이런 방법이 있구나' 정도만 확인하면 좋을 것 같다.
이진힙은 이진트리의 파생된 자료구조로 최대값을 루트로 정하는 Max heap과 최소값을 루트로 정하는 Min heap이 있다.