[자료구조] 트리(Tree)
1. 정의
1.1. 정의
트리(tree)는 계층적인 비선형 자료구조로, 노드(Node)와 그 노드들을 연결하는 간선(Edge)으로 구성된다.
트리는 다음과 같은 구조적 특징을 가진다.
- 노드
- 루트 노드(Root Node) : 트리의 시작점. 부모가 없는 최상위 노드
- 자식 노드(Child Node) : 부모 노드에서 뻗어 나온 하위 노드
- 부모 노드(Parent Node) : 다른 노드를 자식으로 거지는 노드
- 리프 노드(Leaf Node) : 자식이 없는 최하위 노드(말단 노드)
이처럼 루트 노드를 중심으로 뻗어나가는 모습이 마치 나무의 구조와 유사하다고 하여 '트리'라는 이름이 붙였다고 한다.
특징
- 노드 간 관계가 부모-자식 관계로 연결되는 계층 구조
- 순환이 없음(자식 노드의 자식이 부모로 연결되지 않음)
1.2. 관련 용어
- 경로(path) : 한 노드에서 다른 노드에 이르는 길 사이에 있는 노드들의 순서
- 길이(length) : 출발 노드에서 도착 노드까지 거치는 간선의 갯수
- 깊이(depth) : 루트 경로의 길이
- 레벨(level) : 루트 노드부터 노드까지 연결된 간선 수의 합
- 차수(degree) : 각 노드들의 자식의 개수
- 크기(size) : 노드의 개수
- 너비(width) : 가장 많은 노드를 지닌 레벨의 크기
1.3. 유형
트리에는 부모 노드 밑에 자식 노드의 갯수에 따라 여러 유형의 트리로 분류하며 대표적으로는 이진 트리(Binary Tree), 삼진 트리(Ternary Tree; 자식 노드의 갯수가 최대 3개), 트라이(Trie) 등이 있다.
여러 트리 중 현재 가장 많이 활용되고 있는 트리는 바로 이진 트리이다.
1.3.1. 이진 트리(Binary Tree)
자식 노드의 갯수가 최대 2개인 트리이다.
이진 트리는 3가지 유형으로 분류할 수 있다.
정 이진 트리(full binary tree)
- 모든 트리의 자식이 0개 혹은 2개인 이진 트리
완전 이진 트리(complete binary tree)
- 원소가 위부터 아래로, 왼쪽부터 오른쪽으로 채워진 이진 트리
- 마지막 레벨을 제외하고 모든 노드가 차있어야 함
포화 이진 트리(perfect binary tree)
- 모든 리프노드의 높이가 같고, 리프노드가 아닌 노드는 모두 2개의 자식을 갖는 이진 트리
2. 활용
트리는 데이터 간의 계층 관계를 표현하거나 효율적인 탐색 및 정렬이 필요한 곳에서 매우 유용한 자료구조이다.
2.1. 이진 탐색 트리(BST)
트리의 왼쪽 자식 노드는 부모보다 작고, 오른쪽 자식은 부모보다 큰 형태의 이진 트리이다.
효율적인 검색/삽입/삭제 연산이 가능해 시간 복잡도가 평균적으로 O(log n)이다.
2.2. 리눅스/윈도우 디렉터리 구조
리눅스와 윈도우의 디렉터리(폴더) 구조는 루트 디렉터리 아래 여러 하위 폴더가 있는 트리 구조로 이루어져있다.
2.3. HTML/XML 파싱
웹페이지나 문서 구조를 트리 형태로 표현하여 DOM(Document Object Model; 문서 객체 모델)을 통해 각 요소에 접근하고 탐색하는 데 사용된다.
2.4. 힙 트리
3. 참고자료
1. <파이썬 알고리즘 인터뷰>, 2020, 책만 출판사
2. https://namu.wiki/w/%ED%8A%B8%EB%A6%AC(%EA%B7%B8%EB%9E%98%ED%94%84)#rfn-2
3. https://velog.io/@hanif/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%9D%B4%EC%A7%84-%ED%8A%B8%EB%A6%AC