트리 (Tree)

1. 트리 (Tree) 구조

트리(Tree)란 Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조이다. 특히 트리 중 이진 트리(Binary Tree) 구조는 탐색(검색) 알고리즘 구현을 위해 많이 사용된다.

 

 

2. 알아둘 용어

• Node: 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 Branch 정보 포함)
• Root Node: 트리 맨 위에 있는 노드
• Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄
• Parent Node: 어떤 노드의 상위 레벨(상단)에 연결된 노드
• Child Node: 어떤 노드의 하위 레벨(하단)에 연결된 노드
• Leaf Node (Terminal Node): Child Node가 하나도 없는 노드
• Sibling (Brother Node): 동일한 Parent Node를 가진 노드
• Depth: 트리에서 Node가 가질 수 있는 최대 Level

http://www.fun-coding.org/00_Images/tree.png

 

위 그림을 보면, 최상단 노드의 위치를 높이로 표현했다. 이 경우 Level 0이 최상단이다. Level 0부터 Level 2까지의 깊이가 있어서 Depth라고 지칭한다.

 

만약 Sibling이 연결되어 있으면 사이클(cycle)이 발생한 것이라고 볼 수 있는데, 트리(Tree) 자료구조는 사이클을 이루지 않는 것이 중요하다.

 

 

3. 이진 트리와 이진 탐색 트리 (Binary Search Tree)

• 이진 트리: 노드의 최대 Branch가 2인 트리
• 이진 탐색 트리 (Binary Search Tree, BST): 왼쪽 노드는 해당 노드보다 작은 값이고, 오른쪽 노드는 해당 노드보다 큰 값을 가지고 있는 이진 트리

https://www.javatpoint.com/binary-search-tree

 

 

4. 자료 구조 이진 탐색 트리의 주요 용도와 장점

• 주요 용도: 데이터 검색(탐색)
• 장점: 탐색 속도를 개선할 수 있음

이진 트리와 정렬된 배열 간의 탐색 비교

 

https://blog.penjee.com/5-gifs-to-understand-binary-search-tree/#binary-search-tree-insertion-node

 

위의 이진 트리와 정렬된 배열 간의 탐색을 비교하는 GIF를 보면, 이진 탐색 트리에서는 27을 찾는 데에 3번이면 가능했지만, 정렬된 배열에서는 10번이 걸렸다. 탐색 속도를 개선할 수 있는 것이다.

 

 

5. 이진 탐색 트리의 시간 복잡도와 단점

시간 복잡도 (탐색시)

• depth (트리의 높이)를 h라고 표기한다면, O(h)
• n개의 노드를 가진다면, h = log n 에 가까우므로, 시간 복잡도는 O(log n)이다. (빅오 표기법에서 log n 에서의 log의 밑은 10이 아니라, 2이다. 즉, 한 번 실행할 때마다, 50%의 실행할 수도 있는 명령을 제거한다는 의미이다. 다시 말해, 50%의 실행시간을 단축시킬 수 있다는 것을 의미한다.)

이진 트리 탐색 단점

평균 시간 복잡도는 O(log n) 이지만, 이는 트리가 균형 잡혀 있을 때의 평균 시간복잡도이며, 다음 예와 같이 구성되어 있을 경우, 최악의 경우는 O(n)으로 링크드 리스트 등과 동일한 성능을 보여준다.

 

http://www.fun-coding.org/00_Images/worstcase_bst.png

 

 

 

 

 

[참고자료]

패스트캠퍼스 개발자 취업 합격 패스 With 코딩테스트, 기술면접 초격차 패키지 Online 강의자료