트리

이 포스팅은 Interview에 대한 대답 용도로 핵심부분만 요약해서 올린 포스팅입니다.

그러므로 자세한 부분은 다루지 않았고, 잘못된 부분에 대한 지적은 감사히 받겠습니다.

 

 

1. 정의

노드와 간선들로 이루어진 비선형 자료구조로 계층적 관계를 표현합니다.

 

2. 특징 / 특이사항

트리의 주목적은 탐색입니다.

트리는 계층적 관계에 있는 원소들을 나타내기에 편리한 추상데이터 타입입니다.

 

리눅스 파일시스템

자식 노드의 개수는 트리의 주요 특징 중 하나입니다.

하나의 노드가 가질 수 있는 자식노드의 최대숫자가 2보다 큰 B-tree나,

자식노드의 최대숫자를 2개로 한정한 이진트리가 대표적인 예시입니다.

 

3. 접근시간

트리가 균형을 이룬 경우, 최대 트리의 높이만큼 탐색이 이뤄지므로 O(logN)의 시간복잡도.

트리가 편향된 경우, 트리의 높이는 선형 자료구조와 같아지므로 O(N)의 시간복잡도를 가집니다.

 

4. 사용상황

1) 데이터베이스의 B-tree

2) 리눅스 파일시스템

3) heap

4) 이진검색트리 등