[면접 준비 - Algorithm]이진 트리 순회, 이진 탐색 트리(BST), 힙 트리

목차

 

Tree Traversals

 

특정 목적을 가지고 모든 노드를 한 번씩 방문하는 것을 트리 순회라 한다.

 

순회 방법은 크게 네 가지가 있으며, 공통적으로 왼쪽에서 오른쪽으로 진행한다.

 

이진트리는 그 정의상 서브 트리 역시 이진트리이기 때문에, 재귀 함수를 적용하기 편하다.

 

먼저 루트와 좌 우 서브트리 순서에 따른 분류를 보자.

 

 

전위 순회(Preorder Traversal)는 VLR의 순서로 방문한다. 아래와 같다.

 

참고로 이 방식은 그래프 순회의 깊이 우선 탐색(DFS)과 동일한 방법이다.

 

이어서 중위 순회(Preorder Traversal) 순회는 LVR이다. 아래와 같다.

 

마지막으로 후위 순회(Postorder Traversal) 순회는 LRV이다. 아래와 같다.

 

 

추가로 VRL 분류와 별개로 레벨 순서 순회(Level-order Traversal), 또는 너비 우선 탐색(BFS) 방식이 있다.

 

아래와 같다.

 

 

Binary Search Tree

 

이진 탐색 트리는 위의 이진 탐색과 연결 리스트(Linked List)를 결합한 구조이다.

 

이름에 걸맞은 효율적 탐색을 위해 아래와 같은 특징을 가지며,

 

• 중복 값을 다루지 않는다.
• 왼쪽 서브 트리 노드들은 루트 값보다 작다.
• 오른쪽 서브 트리 노드들은 루트 값보다 크다.
• 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.

이상적인 상황(포화 이진트리)에서 탐색/삽입/삭제 모두 시간복잡도가 O(log N)이 된다.

 

추가적으로 정리하자면 탐색의 경우 최악의 경우에도 O(log N)의 시간복잡도를 보장한다.

 

그러나 삽입의 경우, 여기에선 트리가 한쪽으로 치우쳐져 있을 경우 삽입 시간복잡도는 O(n)이 될 수 있다.

 

또한 삭제의 경우 트리 높이 조정을 위한 작업이 필요할 수 있으며, 이 경우 시간복잡도는 O(log N) 보다 높을 수 있다.

 

조금 더 정확하게 말하자면 BST의 시간 복잡도는 당연하게도 트리의 높이에 비례하며,

 

조금 유도해 보자면 포화 BST의 경우 노드의 개수를 N이라 했을 때 높이 h는 다음과 같이 구해진다.

 

$$N = 2^{h+1}-1$$

$$ 2^{h+1} = N+1 $$

$$ h+1 = log_{2}(N+1) $$

$$ h = log_{2}(N+1) - 1 $$

 

즉, 노드가 7개라면 높이는 2가 된다는 뜻이다. 따라서 Big-O표기법에 따라 시간복잡도는 O(log N)이 된다.

 

Heap Tree

 

힙 트리는 우선순위 큐를 구현하는데 필요한 자료구조이다.

 

정렬이 끝난 뒤 최댓값, 혹은 최솟값을 O(1)의 속도로 찾아내기 위한 규칙을 가지고 있으며

 

기본적으로 데이터 삽입/삭제 속도를 O(log N)을 유지하기 위해 완전 이진트리의 형태를 띠고 있다.

 

최댓값을 빠르게 찾기 위한 Max Heap과 최솟값을 위한 Min Heap, 그리고 두 장점을 합쳐둔 Min-Max Heap이 존재하며,

 

데이터 삽입과 삭제에 대한 규칙은 아래와 같다(Min Heap 기준).

 

• 데이터 삽입
  
  
  1. 가장 끝 자리에 노드 삽입
  2. 삽입한 노드와 부모 노드 비교
  3. 조건이 맞으면(Min Heap의 경우 부모 노드가 더 크면) 위치 교환
  4. 더 이상 교환할 수 없을 때까지 교환 반복

 

\

• 데이터 삭제
  1. 루트 노드 제거
  2. 가장 마지막 자리의 노드를 루트 자리로 이동
  3. 자식 노드와 비교
     
     
     1. (Min Heap의 경우) 작은 자식 노드가 없으면 교환하지 않고 끝낸다.
     2. 부모보다 작은 자식이 하나만 있으면 그 노드와 교환한다.
     3. 부모보다 작은 자식이 둘 있으면 둘 중 작은 값을 가진 노드와 교환한다.
  4. 더 이상 교환할 수 없을 때까지 반복

 

BST vs. Heap Tree

 

먼저 둘의 공통점은 데이터의 효율적인 탐색, 삽입, 삭제를 위한 트리 자료구조의 일종이라는 것이다.

 

그러나 위에서 보았듯이 둘 사이에는 몇 가지 차이점이 있는데, 이를 간결하게 정리하고 글으르 마치자.

 

	BST	Heap Tree
구조	이진트리	완전 이진트리
정렬	왼쪽 서브트리 < 루트 < 오른쪽 서브트리	자식 노드 < 부모 노드(변경 가능)
삽입 / 삭제	O(log N)	O(log N)
탐색	O(log N)	최댓값(최솟값)의 경우 O(N)
중복 값	허용하지 않음	허용함(변경 가능)
용도	정렬된 데이터	우선순위가 중요한 데이터(우선순위 큐)