지난 글에서는 이진 탐색트리의 개념과 Search, Add, Delete 의 구현에 대해 정리하였다.
이번 글에서는 BST의 핵심인 '탐색' 과 탐색 시간에 대해 좀 더 깊게 정리해보자.
BST의 탐색 시간
모든 BST의 기능 중에서 제일 중요한 것은 BST 의 이름에도 들어있는 '탐색' 기능이다.
탐색 시간이 얼마나 걸리는지 ( 탐색을 위해 비교를 몇 번이나 하는지) 는 어떻게 측정할까?
답은 정확하게 BST 의 노드 중 찾으려는 노드의 depth + 1 (level + 1) 이다.
[트리에서 Depth, Height, Level ]
Depth = 루트 노드의 depth를 0 으로 정의할 때, 자식 노드의 depth는 부모 노드의 depth + 1 이다.
Level = Depth 와 같다. depth 와 level 은 '노드' 의 특성이다.
Height = 노드의 특징이 아니라 트리의 특성이다. 모든 노드의 level 중 가장 깊은 level 과 같다.
왜 + 1 을 해야 할까?
이 노드가 나와 같은지 다른지 체크하기 위해서는 반드시 최소 한번의 비교가 필요하기 때문이다.
depth = 0 에서 바로 원하는 값을 찾았더라도, depth = 0 인 노드의 key 가 내가 찾으려는 키인지 한 번은 비교를 해야한다.
따라서, 최대 탐색 시간은 트리의 height 의 비례하게 된다. (트리의 height = max (depth) 이므로 )
그리고 만약 모든 키가 동일한 확률로 탐색된다면, 평균 탐색 시간은 BST의 평균 depth 에 비례한다.
이를 통해 우리는 BST의 형태가 효율적인 탐색에 아주 중요함을 알 수 있다.
카탈란 수 내용을 정리하면서, 같은 n 개의 노드를 가지고 있더라도 이진 트리의 형태는 매우 다양할 수 있음을 정리하였다. 가장 탐색이 오래 걸리는 트리는 일직선 형태로 늘어선 트리이고, 가장 탐색이 빠른 트리는 완전 이진 트리 형태로 현재 level 의 모든 노드를 꽉꽉 채우는 트리이다. 즉, 트리의 높이가 낮으면 낮을 수록, 탐색 시간은 더 빠르다.
예를 들어, 아래와 같이 2^h+1 - 1 개의 노드를 가진 이진 트리를 생각해보자.
루트 노드가 1개이므로, 이 노드를 이용해 높이를 최소화 하면 총 h 의 높이를 가진 이진트리를 만들 수 있다.
각 레벨마다 2^level 개수의 노드가 있을 것이다.
h = 2 일 때, 모든 노드의 수는 2 ^ (2+1) - 1 = 7 개이다.
7개의 노드를 직선으로 늘어서면 아래와 같은 모양이된다.
이 두 경우에 대해, BST의 '평균 depth' 를 구해보자.
평균 dpeth 는 간단히 모든 노드의 depth 를 더하고 노드의 갯수로 나누어주면 된다.
첫번째 케이스의 모든 depth 합은 depth * (해당 depth 를 가진 노드의 수) 가 되는데,
각 depth 를 가진 노드의 수는 2 ^ depth 이므로
0 * 1 + 1 * 2 + 2 * 4
= 0 + 2 + 8
= 10
으로 모든 depth 의 합은 10이고, 평균 depth 는 10/7 로 대략 1.4xx 가 나온다.
두번째 케이스의 모든 depth 합은 depth * (해당 depth 를 가진 노드의 수) 에서
각 depth 를 가진 노드의 수는 1개 이므로
0 + 1 + 2 + 3 + 4 + 5 + 6
= 21
평균 depth 는 21 / 7 = 3 이다.
평균 depth 의 차이가 2배 이상 난다.
이를 일반화해보자.
모든 노드가 이진트리를 꽉 채워져 있을 때는, 모든 노드의 depth 합이
0*2^0 + 1*2^1 + 2*2^2 + .... + h*2^h 개 있었다.
이 식을 2배하면
0*2^1 + 1*2^2 + 2*2^3 + .... + h*2^(h+1) 이 된다.
이 두 식을 서로 빼면
- ( -1 + 2^0 + 2^1 + 2^2 + ... + 2^h) + h*2^(h+1)
= - 2^(h+1) + 2 + h*2^(h+1)
= (h-1) * 2^(h+1) + 2
= (h-1) * (2^(h+1) - 1) + 2 + (h - 1)
= (h-1) * (2^(h+1) - 1) + h + 1
이때 모든 노드의 개수 n 이 2^(h+1) - 1 개 이므로
이 식을 n 으로 나눈 평균 depth 는 아래와 같이 된다.
h-1 + (h+1) / n
이때 트리의 높이 h 는 log(n) 에 비례하므로
log(n) - 1 + (log(n) + 1) / n
이고 이는 log(n) - 1 + log(n) / n 과 근접하다.
따라서 평균 depth 가 log(n) 으로 표현됨을 알 수 있고, 평균 depth 가 탐색 시간에 영향을 미치므로
최적의 조건에서는 탐색 시간이 O(log(n)) 임을 알 수 있다.
반면, 노드가 일직선으로 늘어서 있는 최악의 케이스에서는
(0 + 1 + 2 + .... + n - 1) / n
= n(n-1) / (2 * n)
= (n-1) / 2
가 평균 노드 depth 이므로, 탐색 시간이 선형 시간인 O(n) 으로 표현됨을 알 수 있다.
따라서 일반적으로 BST 의 탐색시간은 이 최적의 케이스와 최악의 케이스 사이에 있을 것이다.
그리고 보통 프로그래밍을 할 때는 랜덤 케이스에서 BST의 평균 depth 는 O(log n) 으로 생각한다.
이것으로 BST 의 형태에 따른 BST의 탐색 시간을 생각해보았다.
이때 특정 노드를 탐색하는 '비교 횟수' 는 d+1 이지만, 모든 노드의 평균 깊이를 구할 때는 +1 을 하지 않는 것에 주의하자.
이진 트리의 높이 계산
이렇게 BST의 높이를 통해 BST의 탐색 시간을 고민해보았는데, 이 BST의 높이를 프로그래밍으로 구할 때는 어떻게 구할 수 있을까?
BST의 높이는 '모든 노드의 depth 중에서 최댓값' 이라고 하였다.
따라서 각 노드의 depth를 모두 구해보고, 그 중에 최댓값을 취하면 된다.
각 노드의 depth 는 부모 노드의 dpeth + 1 로 재귀적으로 표현된다.
또한 루트 노드의 depth = 0 이므로 재귀의 base 케이스도 알고 있다.
이를 점화식으로 표현하면 아래와 같이 표현된다.
h(T) = if ( T is empty) then c else max(h(left(T)), h(right(T))) + 1
이때 과연 c 값은 어떤 값이 되어야 할까?
간단하다. root 만 존재하는 이진트리를 생각해보면 된다.
root 노드는 자식이 모두 빈 이진트리 이므로, max( c, c ) + 1 를 depth 로 가질 것이다.
그런데 root node 의 depth = 0 이므로, max(c, c) = -1 이 되어야 하고, 따라서 c = - 1 이다.
이제 BST의 높이를 재귀적으로 구해보자.
height(T) {
if (t == null) { // leaf node
return -1;
}
l <- height( left(T) )
r <- height( right(T) )
if ( l < r ) {
return r + 1;
} else {
return l + 1;
}
}
그런데 이 재귀함수의 동작을 통해서 배울 수 있는 재미있는 점이 하나 있다.
한번 Extended Binary Tree 를 생각해보자.
Extended Binary Tree 는 공집합까지 노드로 생각하는 Binary Tree 인데, 일반적으로 아래가 성립한다.
1) 만약 이진트리가 n 개의 internal node 를 가지고 있다면, 이진 트리에는 n+1 개의 external node (leaf node) 가 있다.
2) 어떤 이진트리 T에 대한 위 height 함수의 recursion tree 는 정확하게 그 이진트리의 Extended Binary Tree 이다.
따라서, 이 함수의 총 호출 횟수는 n + n + 1 = 2n + 1 이다.
이유는 간단하다. height 함수의 종료 조건이 extended binary tree 의 leaf 노드에서 발생하기 때문이다.
또 height 함수는 postorder 방식, DFS 방식으로 동작하고 있다는 것과, 콜 스택 크기는 height + 1 임도 기억하자.
(extended binary tree 의 leaf 노드까지 호출하니까 최대 콜 스택 크기는 height + 1 이다.)
이진 트리의 총 노드의 개수
이번엔 이진 트리의 총 노드의 개수를 구해보자.
이는 아까 높이를 구하는 방법과 비슷하다.
이진 트리는 왼쪽 서브트리와 오른쪽 서브트리를 루트로 묶은 재귀적인 개념이므로
어떤 이진 트리의 노드의 개수는 왼쪽 서브트리 노드 개수 + 오른쪽 서브트리 노드 개수 + 1 이다.
그렇다면 base 조건이 height 와 조금 달라짐을 알 수 있다.
만약 root 노드만 있는 이진트리라면, 이 트리의 노드 개수는 1개 이므로
왼쪽 서브트리 노드 개수 + 오른쪽 서브트리 노드 개수 + 1 = 1
에서 왼쪽 서브트리 노드 개수 = 오른쪽 서브트리 노드 개수 = 0 임을 알 수 있다.
따라서 base 케이스는 0 을 반환한다.
size(T) {
if (T == null) { // leaf node
return 0;
}
return size( left(T) ) + size( right(T) ) + 1;
}
그리고 이 함수에서도 아까 height 함수에서 봤던대로 recursion tree 가 extended binary tree 가 됨을 알 수 있다.
'CS > 자료구조' 카테고리의 다른 글
| [자료구조 및 프로그래밍] 11.5. Python Heapq 모듈 뜯어보기 (2) | 2023.12.02 |
|---|---|
| [자료구조 및 프로그래밍] 11. 우선순위 큐와 Heap (0) | 2023.12.02 |
| [자료구조 및 프로그래밍] 9. 이진 탐색 트리 (3) | 2023.10.22 |
| [자료구조 및 프로그래밍] 8. 이진 트리의 순회 (0) | 2023.10.22 |
| [자료구조 및 프로그래밍] 7. 트리와 이진트리 (0) | 2023.10.20 |
