트리
- 자료 구조의 일종
- 사이클이 없는 연결 그래프
- 정점의 개수: V, 간선의 개수: V-1
- 정점 N개 간선 N개일 때에는 사이클이 1개 있음
루트 있는 트리
- 루트가 있는 트리
- 루트부터 아래로 방향을 정할 수 있다
- 깊이(Level): 루트에서부터 트리(루트의 깊이를 0으로 하는 경우와, 1로 하는 경우가 있다.)
- 높이: 깊이의 최댓값
- 조상, 자손: 조상의 정의에는 자신이 포함됨.
이진 트리(Binary Tree)
포화 이진 트리(Perfect Binary Tree)
- 리프 노드를 제외한 노드 자식의 수: 2
- 리프 노드의 지삭의 수: 0
- 모든 리프 노드의 깊이가 같아야 함
- 높이가 h인 트리 노드의 개수 = 2^h-1
완전 이진 트리(Complete Binary Tree)
- 리프 노드를 제외한 노드 자식의 수: 2
- 리프 노드의 자식의 수: 0
- 마지막 레벨에는 노드가 일부는 없을 수도 있음
- 오른쪽에서부터 몇 개가 사라진 형태
트리의 표현
- 트리는 그래프이기 때문에, 그래프의 표현과 같은 방식으로 저장할 수 있다.
- 또는
- 트리의 모든 노드는 부모를 하나 또는 0개만 가지기 때문에 부모만 저장하는 방식으로 저장할 수 있다.
- 부모가 0개인 경우는 트리의 루트인데, 이 경우 부모를 -1이나 0으로 처리하는 방식을 사용한다.
- 트리의 부모만 저장하는 방식(Union=Find)
- 부모는 한 번에 찾을 수 있지만, 자식을 찾는 것은 오래걸림
- O(N)
- 완전 이진 트리의 경우에는 배열로 표현할 수 있다.(Heap, Segment Tree)
- 부모의 노드가 x인 경우에 자식의 노드는 2x, 2x+1로 나타내면 된다.
- 이진 트리의 경우에는 구조체나 클래스를 이용할 수도 있다.
struct Node{
Node *left;
Node *right;
}
트리의 순회(Tree Traversal)
- 트리의 모든 노드를 방문하는 순서이다.
- 그래프의 경우에는 DFS와 BFS가 있었다.
- 트리에서도 위의 두 방법을 사용할 수 있다.
- DFS는 아래와 같이 3가지 출력 순서가 있다.
- 프리오더 : DFS 순서와 같음
- 노드 방문
- 왼쪽 자식 노드를 루트로 하는 서브 트리 프리오더
- 오른쪽 자식 노드를 루트로 하는 서브 트리 프리오더
- 이진트리가 아니어도 됨.
- 인오더: Binary Search Tree에서 삭제를 구현할 때 사용(인오더 Successor)
- 왼쪽 자식 노드를 루트로 하는 서브 트리 인오더
- 노드 방문
- 오른쪽 자식 노드를 루트로 하는 서브 트리 인오더
- 이진트리에서만 됨.
- 포스트오더: 자식에 대한 정보를 이용해서 현재 값을 이용할 때 사용
- 왼쪽 자식 노드를 루트로 하는 서브 트리 포스트오더
- 오른쪽 자식 노드를 루트로 하는 서브 트리 포스트오더
- 노드 방문
- 이진트리 아니어도 됨.
- 세 방법의 차이는 노드 방문 처리를 언제 할 것인가이다.
트리의 탐색(BFS)
- 트리의 탐색은 DFS/BFS 알고리즘을 이용해서 할 수 있다.
- 트리는 사이클이 없는 그래프이기 때문에
- 임의의 두 정점 사이의 경로는 1개이다.
- 따라서, BFS 알고리즘을 이용해서 최단 거리를 구할 수 있다.
- 이유: 경로가 1개라 찾은 그 경로가 최단 경로
