지난 글: [알고리즘] - 힙
이진 탐색 트리(binary search tree)는 데이터 구조의 하나로, 그래프의 트리 구조를 사용한다. 이진 탐색 트리에서는 각 노드에 데이터가 저장된다.
1
15
/ \
9 23
/ \ / \
3 12 17 28
\
8각 노드는 최대 두개의 자식 노드를 갖는다.이 그림은 이진 탐색 트리의 예다. 각 노드에 적혀 있는 숫자가 데이터이며, 여기에서 같은 숫자는 존재하지 않는다는 가정하에 공부한다.
2
이진 탐색 트리는 두 가지 성질을 지닌다. 첫 번째 성질은, 모든 노드는 왼쪽 가지에 포함되는 어떤 숫자보다도 큰 숫자가 된다는 것이다. 두 번째 성질은, 모든 노드는 그 노드의 오른쪽 가지에 포함되는 어떤 숫자보다 작은 숫자가 된다는 것이다.
3
이 두 개의 성질로부터 다음 조건이 성립된다. 먼저, 이진 탐색 트리의 최소 노드는 최상단에 있는 노드로부터 왼쪽 가지만 계속 따라가면 나오는 가장 끝에 있는 노드가 된다. 이 예에서는 3이 최솟값이 된다.
4
반대로, 이진 탐색 트리에서 최대 노드는 최상단의 노드로부터 오른쪽 가지만 계속 따라가다 보면 나오는 가장 끝에 있는 노드가 최댓값이 된다. 이 예에서는 28이 최댓값이다.
5
이진 탐색 트리에 노드를 추가하는 경우의 순서를 보자. 예로 1을 추가하는 경우이다. 노드 추가 위치를 이진 탐색 트리의 최상단 노드부터 탐색해 간다. 추가하려는 1을 현재 노드 값과 비교해 작으면 왼쪽으로, 크면 오른쪽으로 간다.
1: 15
/ \
9 23
/ \ / \
3 12 17 28
\
8에서 1 < 15 이므로 왼쪽으로 진행한다.
6
15
/ \
1 : 9 23
/ \ / \
3 12 17 28
\
8에서 1 < 9 이므로 왼쪽으로 진행한다.
7
15
/ \
9 23
/ \ / \
1 : 3 12 17 28
\
8에서 1 < 3 이므로 왼쪽으로 진행해야 하지만, 노드가 없으므로 새로운 노드를 추가한다.
15
/ \
9 23
/ \ / \
3 12 17 28
/ \
1 8이것으로 1 추가 작업이 완료되었다.
8
다음은 4를 추가해보자. 위 예와 마찬가지로 이진 탐색 트리의 최상단 노드부터 탐색해 추가할 위치를 찾는다.
4: 15
/ \
9 23
/ \ / \
3 12 17 28
/ \
1 8에서 4 < 15 이므로 왼쪽으로 진행.
9
15
/ \
4: 9 23
/ \ / \
3 12 17 28
/ \
1 8에서 4 < 9 이므로 왼쪽으로진행.
10
15
/ \
9 23
/ \ / \
4: 3 12 17 28
/ \
1 8에서 4 > 3이므로 오른쪽으로 진행.
11
15
/ \
9 23
/ \ / \
3 12 17 28
/ \
1 8 : 4에서 4 < 8이므로 왼쪽으로 진행해야 하지만 왼쪽에 노드가 없으므로 새로운 노드 추가.
15
/ \
9 23
/ \ / \
3 12 17 28
/ \
1 8
/
4이것으로 4의 추가 작업이 완료.
12
다음은 이진 탐색 트리에서 노드를 삭제하는 순서를 보자. 예로 28을 삭제하는 경우다. 자식 노드가 없는 노드는 대상 노드를 삭제만 하면 작업이 끝난다.
15
/ \
9 23
/ \ /
3 12 17
/ \
1 8
/
4
13
다음은 8을 삭제해보자. 자식 노드가 하나인 노드를 삭제할 때는 대상 노드를 삭제하고 삭제한 노드의 위치로 자식 노드를 이동시키면 끝이다.
15
/ \
9 23
/ \ /
3 12 17
/ \
1 4
14
마지막으로 9를 삭제해보자. 자식 노드가 두 개인 경우는 먼저 대상 노드를 삭제하고, 삭제한 노드의 왼쪽 가지에서 최대 노드를 찾는다. 그리고 삭제한 노드의 위치로 이동시킨다. 이것으로 이진 탐색 트리의 두 가지 성질을 유지하며 노드를 삭제했다. 이동 대상 노드(여기서는 4)도 자식 노드를 지니는 경우에는 같은 처리를 재귀적으로 반복하면 된다고 한다.
15
/ \
4 23
/ \ /
3 12 17
/
1
15
이번에는 이진 탐색 트리에서 노드를 탐색하는 순서를 보자. 예로 12를 탐색하는 경우, 이진 탐색 트리의 최상단 노드부터 탐색을 시작한다. 추가할 때와 마찬가지로 12를 현재 노드 값과 비교해서 작으면 왼쪽으로, 크면 오른쪽으로 진행한다.
12: 15
/ \
4 23
/ \ /
3 12 17
/
1에서 12 < 15 이므로 왼쪽으로 진행한다.
16
15
/ \
12: 4 23
/ \ /
3 12 17
/
1에서 12 > 4 이므로 오른쪽으로 진행한다. 그럼 12를 발견하므로 검색 작업이 완료되었다.
이진 탐색 트리는 데이터를 탐색할 때나 추가할 때의 최적의 위치를 찾을 때, 앞서 본 두 가지 성질을 기준으로 현재 위치의 데이터와 대소를 비교하기만 하면 왼쪽으로 진행하는게 좋을지 오른쪽으로 진행하는게 좋을지를 알 수 있다. 이것은 트리의 높이(깊이 또는 단계)만큼만 비교하면 되므로 노드가 n개 있고 트리가 균형 잡힌 경우라면 최대 log2n회의 비교로 이동할 수 있다. 따라서 계산 시간은 O(log n)이 될 수도 있다.
오늘도 할만했다. 데이터 구조를 배우는게 생각보다 흥미롭고 재미있다.
참고 서적:
