💻 [코테04] 9장 트리

9장. 트리

09-1. 트리 개념

• 데이터를 저장하고 탐색하기에 유용한 구조
• 트리의 특성을 활용하는 분야 : 인공지능, 자동 완성 기능, 데이터베이스

1) 나무를 거꾸로 뒤집어 놓은 모양의 트리

• 트리를 구성하는 노드
• 노드를 연결하는 에지
• 부모-자식, 형제 관계를 가지는 노드
• 자식이 없는 말단 노드
• 아래로 향하는 간선의 개수, 차수

09-2. 이진 트리 표현하기

• 배열이나 포인터로 구현 가능

1) 배열로 표현하기

• 아래와 같은 규칙 필요
• 루트 노드는 배열 인덱스 1번에 저장
• 왼쪽 자식노드의 배열 인덱스는 부모 노드의 배열 인덱스 * 2
• 오른쪽 자식 노드의 배열 인덱스는 부모 노드의 배열 인덱스 * 2 + 1

2) 이진 트리 순회하기

• 순회 : 어떤 데이터가 있을 때 그 데이터를 빠짐 없이 방문하는 것
• 전위 순회 : 현재 노드를 부모 노드로 생각했을 때 부모 노드, 왼쪽 자식 노드, 오른쪽 자식 노드 순서로 방문
• 중위 순회 : 현재 노드를 부모 노드로 생각했을 때 왼쪽 자식 노드, 부모 노드, 오른쪽 자식 노드 순서로 방문
• 후위 순회 : 현재 노드를 부모 노드로 생각했을 때 왼쪽 자식 노드, 오른쪽 자식 노드, 부모 노드 순서로 방문

3) 포인터로 표현하기

• 포인터로 표현한 트리는 배열과 달리 인덱스 연산을 하지 않으므로 메모리 공간을 낭비하지 않음

09-3. 이진 트리 탐색하기

• 이진 트리에서 가장 중요한 것 : 탐색을 효율적으로 할 수 있도록 트리 구축

1) 이진 탐색 트리 구축하기

• 데이터 크기를 따져 크기가 작으면 왼쪽 자식 위치에, 크거나 같으면 오른쪽 자식 위치에 배치하는 독특한 정렬 방식

2) 이진 탐색 트리 탐색하기

• 찾으려는 값이 현재 노드의 값과 같으면 탐색을 종료하고 크면 오른쪽 노드를 탐색
• 본인이 찾으려는 값이 현재 노드의 값보다 작으면 왼쪽 노드 탐색
• 값을 찾으면 종료. 노드가 없을 때까지 계속 탐색했는데 값이 없으면 현재 트리에 값이 없는 것임.

3) 이진 탐색 트리와 배열 탐색의 효율 비교

• 두 자료구조의 삽입과 탐색 시간 복잡도 : 이진 탐색 트리의 균형이 맞지 않으면 O(N)으로 같음