트리란?
- 하나의 루트 노드를 가지며, 0개 이상의 자식 노드를 갖고 있다.
- 각 노드들은 간선으로 연결되어 있다.
- 비선형 자료구조이며 계층적 관계를 표현한다.
- 사이클이 없는 하나의 연결그래프이다.
- 노드가 N개인 트리는 항상 N-1개의 간선을 가진다.
- 루트에서 어떤 노드, 또는 임의의 두 노드 간의 경로는 유일하다.
- 순회하는 방법에는 Pre-Order, In-Order, Post-Order가 있다.
관련 용어
- 노드의 크기(Size): 자신을 포함한 모든 자손 노드의 개수
- 노드의 깊이: 루트에서 어떤 노드에 도달하기까지 거쳐야 하는 간선의 수
- 노드의 레벨: 트리의 특정 깊이를 가지는 노드의 집합
- 노드의 차수(Degree): 노드의 자식 수
- 트리의 차수: 트리의 최대 차수
- 트리의 높이: 루트 노드에서 가장 깊숙히 있는 노드의 깊이
트리 순회
아래와 같은 트리가 있다고 할 때, 여러가지 방법으로 순회해보자.
- 전위 순회 (Pre-Order)
루트노드 -> 왼쪽 서브트리 -> 오른쪽 서브트리의 순서로 순회하는 방식이다. 깊이 우선 순회라고도 한다.
E -> F -> A -> G -> C -> B -> I -> D -> H - 중위 순회 (In-Order)
왼쪽 서브트리 -> 루트노드 -> 오른쪽 서브트리의 순서로 순회하는 방식이다. 대칭 순회라고도 한다.
G -> A -> C -> F -> E -> I -> B -> H -> D - 후위 순회 (Post-Order)
왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트노드의 순서로 순회하는 방식이다.
G -> C -> A -> F -> I -> H -> D -> B -> E
트리의 종류
- 이진 트리
각 노드가 최대 두 개의 자식 노드를 갖는 트리 - 이진 탐색 트리
모든 노드가 특정 순서를 따르는 속성이 있는 이진 트리 (ex. 모든 왼쪽 자식들 <= n < 모든 오른쪽 자식들) - 균형 트리 (ex. Red-Black Tree, AVL Tree)
O(logN) 의 시간복잡도로 insert와 find를 할 수 있을 정도로 균형이 잡혀 있는 트리 - 이진 힙
트리의 마지막 단계에서 오른쪽 부분을 뺀 나머지 부분이 가득 채워져 있는 완전 이진 트리
최소 힙: 각 노드의 원소가 자식들의 원소보다 작다.
최대 힙: 각 노드의 원소가 자식들의 원소보다 크다.
'CS Study > 자료구조' 카테고리의 다른 글
힙이란? (0) | 2022.04.08 |
---|---|
스택(Stack), 큐(Queue) (0) | 2022.03.11 |