[💻 코드스테이츠 FE 44기] 자료 구조 - 트리(Tree), 그래프(Graph)

✔️ 시작

트리(Tree), 그래프(Graph)에 대한 이론을 학습하고 알고리즘을 풀어 보았다.

---

📍 배운 것

✔️ 트리(Tree)

• 이름 그대로 나무의 형태를 가지고 있다. (정확히는 나무를 거꾸로 뒤집어 놓은 듯한 모습)
• 여러 구조 단방향 그래프의 한 구조로, 하나의 뿌리로 부터 가지가 사방으로 뻗은 형태
  

이진트리(Binary tree)

• 자식 노드가 최대 두 개인 노드로 구성된 트리
  - 두 개의 자식 노드는 왼쪽 자식 노드와 오른쪽 자식 노드로 나눌 수 있다.
• 자료의 삽입, 삭제 방법에 따라 나뉜다.
  - 이진트리(Full binary tree), 완전 이진트리(Complete binary tree), 포화 이진트리(Perfect binary tree)

소주 뚜껑 게임 (업 앤 다운) 처럼 기준 값을 정해서 빠르게 찾는다.

이진트리 특징

• 정 이진트리 : 각 노드가 0개 혹은 2개의 자식 노드를 갖는다.
• 포화 이진트리 : 정 이진트리이면서 완전 이진트리인 경우
  - 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리
• 완전 이진트리 : 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 외쪽이 채워져 있어야한다.

• 이러한 이진트리는 이진 탐색 트리와 이진 힙 구현에 사용 되고
• 효율 적인 검색과 정렬을 위해 사용 된다.

✔️ 이진 탐색 트리(Binary Search Tree)

이진 탐색?

• 정렬된 데이터 중에서 특정한 값을 찾기 위한 탐색 알고리즘 중 하나
• 노드를 기준으로 왼쪽이 작거나 같고, 오른쪽은 큰 값이 위치하는 트리로 전부 정렬 되어있다.

❗️ 이진 탐색 트리와 이진 트리는 다른 개념이다.

차이점이 있다면 이진 탐색 트리는 정렬 되어있고 이진 트리는 정렬되어있지 않다.

이진 탐색 트리 특징

• 각 노드에 중복되지 않는 키(key)가 있다.
• 루트노드의 왼쪽 서브 트리 : 해당 노드의 키보다 작은 키를 갖는 노드들로 이루어져 있다.
• 루트노드의 오른쪽 서브 트리 : 해당 노드의 키보다 큰 키를 갖는 노드들로 이루어져 있다.
• 좌우 서브 트리도 모두 이진 탐색 트리여야 한다.

모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가지는 특징이 있다.

기존 이진 트리보다 탐색이 빠르다는 장점이 있다.
트리의 높이가 h(height)라면 o(h)의 복잡도를 가지게 된다.
트리 안에 찾고자 하는 값이 없더라도 최대 h번(트리의 높이) 만큼 연산과 탐색이 진행된다.
1. 루트 노드의 키와 찾고자 하는 값을 비교 한다.
- 만약 찾고자 하는 값이라면 탐색을 종료
2. 찾고자 하는 값이 루트 노드의 키보다 작다면 왼쪽 서브 트리로 탐색을 진행
3. 찾고자 하는 값이 루트 노드의 키보다 크다면 오른쪽 서브 트리로 탐색을 진행

전위 순회(preorder traverse)

1. 가장 먼저 방문하는 노드는 루트이다.
2. 루트에서 시작해 왼쪽의 노드들을 순차적으로 둘러본 뒤
3. 왼쪽의 노드 탐색이 끝나면 오른쪽 노드를 탐색한다.

부모 노드가 제일 먼저 방문되는 순회 방식
(트리를 복사할 때 사용)

전위 순회할 경우

1 - 6 - 4 - 7 - 9 - 8 - 10 - 5 - 2 - 3 - 11

중위 순회(inorder traverse)

1. 루트를 가운데에 두고 순회한다.
2. 제일 왼쪽 끝에 있는 노드 부터 순회하기 시작해
3. 루트를 기준으로 외쪽에 있는 노드의 순회가 끝나면 루트를 거쳐
4. 오른쪽에 있는 노드로 이동해 마저 탐색한다.

부모 노드가 서브 트리의 방문 중간에 방문되는 순회 방식
(이진 탐색 트리의 오름차순으로 값을 가져올 때 사용)

중위 순회할 경우

7 - 4 - 8 - 9 - 10 - 6 - 5 - 1 - 3 - 2 11

후위 순회(postorder traverse)

1. 루트를 가장 마지막 부터 순회한다.
2. 제인 왼쪽 끝에 있는 노드부터 순회하기 시작해
3. 루트를 거치지 않고 오른쪽으로 이동해 순회한 뒤,
4. 제일 마지막에 루트를 방문한다.

트리를 삭제할 때 사용한다.
(자식 노드가 먼저 삭제되어야 상위 노드를 삭제할 수 있기 때문)

중위 순회할 경우

7 - 8 - 10 - 9 - 4 - 5 - 6 - 3 - 11 - 2 - 1

레벨 순회 (levelorder traverse)

1. 트리의 레벨 기준으로 노드들을 방문 순회 한다.
2. 루트 노드를 시작으로 아래로 뻗어나가 노드들을 방문하며 루트 노드의 레벨이 1이라고 했을 때
3. 아래로 내려갈 수록 레벨은 증가하는 특징을 볼 수 있다.
4. 동일한 레벨에 여러 노드가 존재할 경우 왼쪽에서 오른쪽 순서로 노드를 순회한다.

레벨 순회할 경우

1 - 6 - 2 - 4 - 5 - 3 - 11 - 7 - 9 - 8 - 10

순회 방식을 나누는 이유?

모든 노드를 방문하기 위해서는 일정한 조건이 필요하고,
트리 구조를 유지보수하거나 특정 목적을 위해서도 순회 방법에 대한 정의는 필수적으로 필요하기 때문

✔️ 그래프(Graph)

• 여러 개의 점이 서로 복잡하게 연결된 관계를 표현한 자료구조
• 거미줄 처럼 여러 개의 점이 선으로 이어져 있는 복잡한 네트워크망과 같은 모습

그래프의 구조

• 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있다.
• 간접적인 관계인 경우 몇 개의 점과 선에 걸쳐 이어진다.
• 정점(vertex, node) : 하나의 점을 그래프에서 정점이라 한다.
• 간선(edge) : 정점을 이어두는 각 하나의 선은 간선이라 한다.

표현 방식

인접 행렬

1이 간선을 의미 한다.

• 만약 A라는 정점과 B라는 정점이 있다면 1(true), 이어져 있지 않다면 0(false)로 표시한 일종의 표
• 만약 가중치 그래프인 경우 1 대신 관계에서 의미 있는 값을 저장한다.

• 두 정점을 이어주는 간선이 있다면 두 정점은 인접하다고 한다.
• 서로 다른 정점들이 인접한 상태인지를 표시한 행렬로 2차원 배열의 형태로 나타낸다. [0][1]

인접 리스트

• 각 정점이 어떤 정점과 인접하는지를 리스트 형태로 표현
• 각 정점 마다 하나의 리스트를 가지고 있으며, 이 리스트는 자신과 인접한 다른 정점을 담고 잇다.

인정 행렬, 인접 리스트는 언제 사용?

인접 행렬

• 두 정점 사이에 관계가 있는지, 없는지 확인하기에 용이
• 가장 빠른 경로(shortest path)를 찾고자 할 때 주로 사용

인접 리스트

• 메모리를 효율적으로 사용하고 싶을 때

BFS(Breadth-First Search)

• 너비 우선 탐색
• 노드의 인접한 이웃들을 먼저 방문하고 이웃의 이웃 노드를 방문

최단 경로 찾을 때 사용

BFS는 현재 있는 노드에서 가까운 곳부터 탐색하므로 경로를 탐색하는 도중 가장 먼저 발견한 해답이 최단거리라는 보장이 되기 때문

DFS(Depth-First Search)

• 깊이 우선 탐색(주로 스택을 사용한다.)
• 갈 수 있는 한 깊게 들어 간 후 더 이상 갈 수 없을 때 이전으로 돌아간다.
• 하나의 경로를 끝까지 탐색한 후, 원하는 값이 아니면 다음 경로로 넘어가 탐색한다.

---

✏️ 마치며

트리(Tree), 그래프(Graph)에 대한 이론에 대해 학습했다.

자료구조, 알고리즘은 해당 과 학생이 한 학기 동안 배우는 내용이라고 할 수 있다.
그걸 이틀 만에 배울려고 하니 어려운건 사실이다.

그래도 어떤식으로 동작하는지만 알아도 괜찮지 않을까 싶어서
도형을 그려 같이 첨부해 두었다.

관련 알고리즘... 솔직히 너무 어려웠다.

분명 나중에 가면 필요하겠지만...
지금은 레퍼런스 코드 참고하면서
이런식으로 진행하는 구나.. 정도로 익혀 두려고 한다.