[Data Structure] Tree

Tree

- Node와 Edge로 이루어진 자료구조

트리의 구조

 

특징

- 값을 가진(Node)와 노드를 연결하는 간선(Edge)로 이루어져 있음.

- 루트 노드 : 부모가 없는 노드(그림에서 1)

- 모든 노드는 0개 이상의 자식노드를 가지며, 부모-자식 관계라고 칭함

- 사이클이 존재할 수 없음(사이클이 생기면 트리가 아니라 그래프)

- 루트에서 노드 한개로 가는 경로는 유일함

- 노드의 개수가 N개일 때, 간선은 N-1개

 

트리 순회 방식

1. 전위 순회(pre-order) : root → 왼쪽 자식 → 오른쪽 자식 

2. 중위 순회(in-order) : 왼쪽 자식 → root → 오른쪽 자식 

3. 후위 순회(post-order) : 왼쪽자식 → 오른쪽 자식 → root

 

트리 장점 및 활용 예시

[장점]

- 계층적 관계를 표현하는 데 용이

- 편향 트리가 아닌 이상 Array나 Linked List에 비해 삽입/삭제 수행 시 O(logN) 이라는 적은 시간 소요

[활용]

- 최대/최소 힙, 우선순위 큐

- 디렉토리 구조

- 대진표, 조직도, 가족관계도 등

- HTML Tag 구조

- 주소 체계

- DBMS(Database Management System) ex. 인덱싱

- 검색엔진 알고리즘