자료 구조에 따른 시간 복잡도 비교 - Tree편

이번 포스팅에서는

Tree와 Binary Search Tree라는 자료구조와 함께

시간 복잡도를 알아보고자 합니다 :D 

 

먼저, Tree는 

일상 생활 속에서 예시를 찾아보면

회사의 조직도

출처 : 10page 연구소

를 생각해 볼 수 있습니다 :D 

 

예시를 바탕으로 트리 자료구조에 대해서 간략하게 설명을 해보면,

tree 는 먼저, node와 edge로 이뤄져 있습니다:D 

여기서 node는 자료를 담고 있는 부분이고,

edge는 각각의 노드들을 연결하고 있는 선과 같습니다.

 

이 때, tree는 맨 위에 root node(직역하면 뿌리가 되는 노드)가 있고,

그 아래에 해당 root node의 child node가 edge로 연결되어 있는 구조입니다.

여기서 root node는 child node에게 있어서 parent node가 되겠죠.

또한, 위의 부사장이 또 하나의 parent node라고 할 때 그 아래에 

영업부, 자동화사업부, 총무부는 부사장의 child node가 되고,

위의 세 부서(child node들)는 siblings 형재 자매 관계라고 부릅니다.

또한, 가장 아래에 있는 시스템 설계팀, 시스템 제작팀 등 더 이상 child node를 갖지 않는

노드들을 leaf라고 합니다.

단어에서 느끼셨겠지만, tree 자료구조는 말그대로 나무의 형태와 닮은 자료구조이고

명칭들도 나무에서 가져왔다는 것을 알 수 있습니다 :D 

 

출처 : tutorialspoint

이 때, tree 자료구조에는 depth(깊이) 라는 용어와 height(높이)라는 용어가 있는데,

이 둘의 차이점을 짚고서 정의부분을 넘어가도록 하겠습니다.

먼저, 깊이는 위와 같이 root node를 기점으로 root node의 깊이는 0, 그 다음 child node의 깊이는 1

이런식으로 말그대로 깊이를 나타냅니다.

그러나, height(높이)는, 특정 노드에서 가장 아래 노드까지의 깊이 차이라고 할 수 있을 것 같습니다.

구체적으로 말해보면, 예를 들어, 위의 그림에서

B의 깊이는 1이고, H의 깊이는 3입니다.

이 때, 노드 B의 높이(height)를 구해보면, 3-1인 2가 됩니다.

달리 표현해보면, 높이는 특정 노드로부터 가장 아래에 있는 노드까지의 거리라고도 표현해볼 수 있습니다.

 

그럼 다음으로

tree의 특징을 정리해보면 다음과 같습니다.

tree는 뒤에서 배울 이진 트리와 달리 

순서의 규칙이 없습니다. 즉, 마음대로 추가하면 됩니다.

또한, 일반 트리는 이진 트리와 달리 하나의 부모 노드에 

자식 노드의 개수가 정해져있지 않습니다(이진 트리는 2개로 제한).

 

이러한 트리의 정의와 특징을 바탕으로

트리 자료구조의 시간 복잡도를 보면,

출처 : 코드스테이츠

 

위의 예시는 html의 태그들을 트리로 표현해본 것인데요(실제로 트리구조로 되어있음)

이 때, 특정한 값(노드 속의  value)를 찾는다고 했을 때

시간 복잡도는 어떻게 될까를 생각해보면

 

트리는 아까 말했듯이

순서가 정해져 있지 않기 때문에 결국 특정 값을 찾으려면

인덱스가 없었던 linked list와 같이 앞에서부터 하나하나 탐색해야 합니다:D 

정리를 안하면 어떻게 되는지 여실히 보여주는?? 부분인 것 같기도 한데요!

 

Anyway!

트리는 이렇듯 특정 값을 탐색하거나, 조회 할 때 O(n)의 시간복잡도를 가집니다.

이에 더하여, 특정 노드의 chlid node를 생성해주려면 => 일단 특정 노드를 찾고[O(n)],

그 노드의 childNode에 추가해주면 된다[O(1)]. 

삭제의 경우, 삭제하고자 하는 노드의 부모 노드를 찾은 뒤에[O(n)]

삭제하고자 하는 노드를 부모 노드의 childNode 리스트에서 지워주면 된다[O(1)].

 

여기까지  Tree에 대해서 살펴봤고,

다음 포스팅에서

binary tree 및 binary search tree를 살펴보겠습니다 :D