[자료구조 및 프로그래밍] 10. BST 탐색 시간과 Height 사이 관계

지난 글에서는 이진 탐색트리의 개념과 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 가 됨을 알 수 있다.