트리 자료구조 이해하기

트리란?

자료구조의 일종

사이클이 없는 연결 그래프

모든 정점이 연결되어 있어야한다.

정점의 개수: V

간선의 개수: V-1

 

정점이 n개, 간선이 n개인 경우 -> 사이클이 딱 "1개" 있는 그래프

정점이 n개, 간선이 n-1개인 경우 -> 사이클이 없는 "트리"

 

이진트리?

자식을 최대 2개만 가지고 있는 트리

 

포화 이진트리?

리프 노드를 제외한 노드의 자식의 수: 2

리프 노드의 자식의 수: 0

모든 리프 노드의 깊이가 같아야 함.

높이가 h인 트리 노드의 개수: 2^h - 1

 

완전 이진트리?

리프 노드를 제외한 노드의 자식의 수: 2

리프 노드의 자식의 수: 0

마지막 레벨에는 노드가 일부는 없을 수도 있음.

오른쪽에서부터 몇개가 사라진 형태

 

트리의 표현

1. 그래프와 같은 방식으로 저장

2. 부모만 저장(루트의 경우 -1이나 0으로 저장)

 

부모만 저장하는 방식의 장단점

장점: 부모 찾기 쉬움 O(1)

단점: 자식 찾는거 오래 걸림 O(n)

 

완전 이진트리의 경우 배열로 표현 가능

부모의 노드가 x인 경우 자식 노드는 2*x, 2x + 1 로 표현 가능

 

이진트리의 경우 구조체나 클래스로 표현 가능.

 

트리의 순회

1. dfs의 경우

- 프리오더

: 노드방문 -> 왼쪽 자식 노드를 루트로 하는 서브 트리 프리오더 -> 오른쪽 자식 노드를 루트로 하는 서브트리 프리오더

 

- 인오더

: 왼쪽 자식 노드를 루트로 하는 서브 트리 인오더 -> 노드방문 -> 오른쪽 자식 노드를 루트로 하는 서브트리 인오더

: bst(binary search tree)에서 삭제 구현할때 "만" 쓰인다.

:이진트리에서만 사용 가능

 

- 포스트오더

:왼쪽 자식 노드를 루트로 하는 서브 트리 포스트오더 -> 오른쪽 자식 노드를 루트로 하는 서브트리 포스트오더 -> 노드방문

: 제일 많이 쓰이는 순회 방식

: 자식의 정보를 이용해 현재 노드의 정보를 계산할때 거의 포스트 오더가 쓰임

 

즉, 부모의 값을 이용해 자식의 값을 구하는 경우 -> 프리오더

자식의 값을 이용해 부모의 값을 구하는 경우 -> 포스트오더

bst에서 삭제 구현시 -> 인오더