트리란?(Tree)

1. 트리란

 그래프의 일종으로 계층적인 구조를 지니는 자료 구조

 

* 결정 트리 : 인공지능에서 사용

 

주요 개념

노드, 루트, 서브트리, 간선, 부모 노드, 자식 노드, 형제 관계, 조상 노드, 자손 노드, 단말 노드, 트리의 높이

 

2. 이진 트리 : 공집합이거나, 왼쪽 서브 트리, 오른쪽 서브 트리로 이루어진 트리

- 이진 트리의 성질 : n개의 노드 n-1개의 간선(그래야지 모두가 중복되지 않고 연결되있음)

- 이진 트리의 높이 : 최대 2^h -1 h는 높이

 

3. 순회의 종류

- 전위 순회 : VLR 부모 먼저 계산 하고 싶을 때

- 중위 순회 : LVR 디렉토리 용량 계산

- 후위 순회 : LRV 자식 먼저 계산하고 싶을 때

 

4. 스레드 이진 트리

- 중위 순회 시 L쪽에 상단 위치를 저장하여 순회하는 방법

 

5. 이진 탐색 트리

 - 탐색을 위한 트리

 - 왼쪽은 루트보다 작은 값 오른쪽은 루트보다 큰 값을 가진다

 - 자식들도 이진 탐색 트리 구조로 되어있음

 - 노드의 키가 유일하다.

5.1 이진 탐색에서 삭제 연산

 - 자식이 없는 경우 : 삭제한다

 - 자식이 하나 있는 경우 : 삭제하고 자식을 현재 위치로 한다

 - 자식이 둘 있는 경우 : 오른쪽 서브 트리의 가장 작은 값으로 값을 넣는다