📖저자님의 책 소개 영상: https://www.youtube.com/watch?v=Q13Uj_5bH9M

🗓️TIL (this week I learned)
월 🤒
화 개념정리
수 😴
목 몸풀기 문제 2

🔷 9. 트리⭐⭐

9-1 개념

(출처: 나무위키)

• 차수: 특정 노드에서 아래로 향하는 간선의 개수

🔹 트리의 특성 활용

• 인공지능: 분류모델(decision tree, random forest 등)
• 자동완성 기능
• 데이터베이스

➕참조
https://namu.wiki/w/%ED%8A%B8%EB%A6%AC(%EA%B7%B8%EB%9E%98%ED%94%84)

🔹그래프 vs 트리 차이점

• 트리는 순환 구조를 갖지 않는 그래프
• 부모 노드에서 자식 노드를 가리키는 단방향뿐.
• 하나의 부모 노드를 갖는다. 루트는 하나.

9-2 이진 트리 표현하기

1. 배열로 표현하기

• 빈 공간이 생긴다
• 배열로 트리를 표현하면, 자식이 없거나 쓰지 않는 인덱스들은 모두 빈 값이므로 메모리가 낭비된다.(단점)
• 나쁜 표현 방법은 아님. 구현 난이도가 쉬움! 메모리가 넉넉하다면 구현 시간을 단축하는 용도로 사용하면 좋다.

2. 이진 트리 순회하기
   순회: 데이터가 있을 때 그 데이터를 빠짐없이 방문하는 방법
   🔹전위 순회(preoder): 현재 노드를 부모 노드로 생각했을 때,
   부모노드 → 왼쪽 자식 노드 → 오른쪽 자식 노드 순서로 방문. 트리를 복사할 때 많이 사용
   🔹중위 순회(inoder): 현재 노드를 부모 노드로 생각했을 때,
   왼쪽 자식 노드 → 부모노드 → 오른쪽 자식 노드 순서로 방문. 이진 탐색 트리에서 정렬된 순서대로 값을 가져올 때 사용.
   🔹후위 순회(postoder): 현재 노드를 부모 노드로 생각했을 때
   왼쪽 자식 노드 → 오른쪽 자식 노드 → 부모노드 순서로 방문. 트리 삭제에 자주 활용.

3. 포인터로 표현하기

• 배열과 달리 인덱스 연산을 하지 않으므로 메모리 공간 낭비 x
• 구현 난이도는 조금 높음

9-3 이진 트리 탐색하기

1. 구축하기

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

2. 탐색하기

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

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

• 균형 이진 탐색 트리(balanced binary search tree)
  - AVL 트리 https://en.wikipedia.org/wiki/AVL_tree

  (출처: AVL tree - wikipedia)

• 레드 블랙 트리 https://en.wikipedia.org/wiki/Red%E2%80%93black_tree

🔹배열 탐색과 비교하면, 데이터 크기에 따라 하위 데이터 중 한 방향을 검색 대상에서 제외하므로 검색이 빠르다.

🔹시간 복잡도:

• 트리 균형이 유지된다는 전제에서 시간 복잡도는 $O(logN)$
• 균형이 맞지 않을 때는 배열과 비슷. 최악인 경우 $O(N)$