S4) Unit 1. [자료구조/ 알고리즘] Tree & Graph

📣  Tree 란?

𝟭. Tree의 정의

✔️ 계층적인 자료를 표현하는 데 이용되는 자료구조
➰ 하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 비선형 구조
➰ 아래로만 뻗어나가기 때문에 사이클(시작 노드에서 출발해 다른 노드를 거쳐 시작 노드로 돌아오는 것)이 없는 하나의 연결 그래프
 

𝟮. Tree의 구조와 특징

➰ 루트라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선(edge)로 연결한다.
➰ 각 데이터를 노드(Nodee)라고 하며, 두 개의 노드가 상하 계층으로 연결되면 부모(Parent Node)/ 자식(Child Node) 관계를 맺는다.
➰ 자식이 없는 노드는 리프 노드(Leaf Node)라고 부른다.
 
1️⃣ 깊이(Depth)
➰ 루트로부터 하위 계층의 특정 노드까지의 깊이를 표현할 수 있는데, 루트 노드는 깊이를 0으로 두고 위 그림에서 루트 A의 깊이는 0이고, B와 C의 깊이는 1이다.
 
2️⃣ 높이(Height)
➰ 리프 노드를 기준으로 루트까지의 높이를 표현할 수 있는데, 리프 노드와 직간접적으로 연결된 노드의 높이를 표현하며, 부모 노드는 자식 노드의 가장 높은 높이 값에 +1한 값을 가진다.
➰ 리프 노드의 높이를 0으로 두고 위 그림에서 H, I, E, F, J의 높이는 0이다 -> 자식이 없기 때문에 리프 노드이다.
➰ D와 G의 높이는 1이고, B와 C의 높이는 2이다 -> 이때, B는 D의 높이 + 1, C는 G의 높이 + 1을 높이로 가진다.
➰ 루트 A의 높이는 3이다.
 
3️⃣ 레벨(Level)
➰ 트리 구조에서 같은 깊이를 가지고 있는 노드를 묶어서 레벨로 표현할 수 있다.
➰ 깊이가 0인 루트 A의 레벨은 1, 깊이가 1인 B와 C의 레벨은 2이다.
➰ D, E, F, G의 레벨은 3이다.
➰ 같은 레벨에 있는 노드를 형제 노드(Sibling Node)라고 한다.
 

𝟯. Tree의 실사용 예제

✔️ 컴퓨터의 디렉토리 구조
➰ 모든 폴더는 하나의 폴더(루트 폴더, /)에서 시작되어 가지를 뻗어나가는 모양새를 띈다.
➰ 사용자들이 편하게 사용하기 위한 파일 시스템은 트리 구조를 이용해서 만들어져 있다.

---

📣  이진 트리(Binary Tree)

𝟭. Binary Tree의 정의

✔️ 자식 노드가 최대 두 개인 노드로 구성된 트리 (왼쪽 자식 노드, 오른쪽 자식 노드)
 

𝟮. Binary Tree의 특징

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

---

📣  이진 탐색 트리(Binary Search Tree) 란?

𝟭. 이진 탐색 트리의 정의

✔️ 이진 탐색의 속성이 이진 트리에 적용된 특별한 형태의 이진 트리
✚ 이진 탐색이란?

✔️ 정렬된 데이터 중에서 특정한 값을 찾기 위한 알고리즘 중 하나

➰ 오름차순으로 정렬된 정수의 배열을 같은 크기의 두 부분 배열로 나눈 후, 두 부분 중 탐색이 필요한 부분에서만 탐색하도록 탐색 범위를 제한하여 원하는 값을 찾는 알고리즘.

1. 배열의 중간에 내가 찾고자 하는 값이 있는지 확인한다.
2. 중간값이 내가 찾고자 하는 값이 아닐 경우, 오름차순으로 정렬된 배열에서 중간값보다 큰 값인지 작은 값인지 판단한다.
3. 찾고자 하는 값이 중간값보다 작은 값일 경우, 배열의 맨 앞부터 중간값 전까지의 범위를 탐색 범위로 잡고 탐색을 반복 수행한다.
4. 찾고자 하는 값이 중간값보다 큰 값일 경우, 배열의 중간값의 다음 값부터 맨 마지막까지를 탐색 범위로 잡고 탐색을 반복 수행한다.

➰ 루트 노드는 이진 탐색에서 리스트의 중간값이 된다.
➰ 각 노드에 중복되지 않는 키가 있다.
➰ 루트 노드의 왼편 서브 트리의 값들은 모두 루트 노드의 값보다 작은 값들이 있고, 오른편 서브 트리의 값들은 루트 노드의 값보다 큰 값들이 있어야 한다.
➰ 좌우 서브 트리 모두 이진 탐색 트리여야 한다.
 

𝟮. 이진 탐색 트리 특징

1️⃣ 기존 이진 트리보다 탐색이 빠르다(이진 탐색 트리의 높이가 h인 경우 O(h) 의 시간복잡도를 갖는다)
✚ 이진 탐색 트리의 탐색 과정

1. 루트 노드의 키와 찾고자 하는 값을 비교합니다. 만약 찾고자 하는 값이라면 탐색을 종료한다.
2. 찾고자 하는 값이 루트 노드의 키보다 작다면 왼쪽 서브 트리로 탐색을 진행한다.
3. 찾고자 하는 값이 루트 노드의 키보다 크다면 오른쪽 서브 트리로 탐색을 진행한다.
4. 찾고자 하는 값이 없다면 그대로 연산을 종료하게 된다.

=> 5를 찾기 위해 3회 탐색 진행

---

📣  트리 순회란?

𝟭. 트리 순회의 정의

✔️ 특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것
 

𝟮 . 트리 순회의 방법

1️⃣ 전위 순회(Preorder Traverse)
✔️ 루트 -> 왼쪽에 있는 모든 노드 -> 오른쪽에 있는 모든 노드 (부모 노드가 제일 먼저 방문 되는 순회)
➰ A -> B -> D -> H -> I -> E -> J -> K -> C -> F -> ...
➰ 주로 트리를 복사할 때 사용
 
2️⃣ 중위 순회(Inorder Traverse)
✔️ 루트를 가운데에 두고, 제일 왼쪽 끝에 있는 노드부터 순회하기 시작해서 끝나면 루트를 거쳐 오른쪽에 있는 노드를 탐색
➰ H -> D -> I -> B -> J -> E -> K -> A -> L -> F -> M -> C -> ...
➰ 이진 탐색 트리의 오름차순으로 값을 가져올 때 사용
 
3️⃣ 후위 순회(Postorder Traverse)
✔️ 루트를 가장 마지막으로 순회하며, 제일 왼쪽 끝에 있는 노드 부터 순회하기 시작해서 루트를 거치치 않고 오른쪽 노드를 순회한 뒤 루트를 방문한다.
➰ H -> I -> D -> J -> K -> E -> B -> L -> M -> F -> ... -> A
➰ 트리를 삭제할 때 사용
 
4️⃣ 레벨 순회(Levelorder Traverse)
✔️ 루트를 기준으로 순회하는 것이 아닌 트리의 레벨 기준으로 노드들을 방문
➰ A -> B -> C -> D -> E-> F -> G ... -> O

---

📣  Graph 란?

𝟭. Graph의 정의

✔️ 여러 개의 점이 서로 복잡하게 연걸된 관계를 표현한 자료구조

𝟮. Graph의 구조

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

𝟯. Graph의 표현 방식

1️⃣ 인접 행렬 
✔️ 두 정점을 이어주는 간선이 있다면 이 두 정점은 인접하다라고 이야기한다.
➰ 인접 행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 2차원 배열이다.
➰ 이어져 있다면 1, 없다면 0으로 표시한다.
➰ 이 위 그림에서 A의 진출차수는 1개이다.
    ㄴ [0][2] === 1
➰ B의 진출차수는 2개이다.
    ㄴ [1][0] === 1
    ㄴ [1][2] === 1
 
✔️ 두 정점 사이의 관계 유무를 확인하기에 용이하며, 가장 빠른 경로를 찾고자 할 때 주로 사용된다.
 
2️⃣ 인접 리스트
✔️ 인접 리스트는 각 정점이 어떤 정접과 인접하는지를 리스트의 형태로 표현한다.
➰ 각 정점마다 하나의 리스트를 가지고 있으며, 이 리스트는 자신과 인접한 다른 정점을 담고 있다.

위 그림의 인접리스트

 
➰ B에는 간선이 2개가 존재하는데, 어디를 먼저 적는지는 중요하지 않다.
 
✔️ 메모리를 효율적으로 사용하고 싶을 때 인접 리스트를 사용한다(인접 행렬은 연결 가능한 모든 경우의 수를 저장하기 때문에 상대적으로 메모리를 많이 차지한다)
 

𝟰. Graph의 실사용 예제

✔️ 포털 사이트의 검색 엔진, SNS에서 사람들과의 관계, 내비게이션 등 
➰ 모든 예시가 수 많은 정점을 가지고 있고, 서로 관계가 있는 정점은 간선으로 이어져 있다.
➰ 가중치 그래프(필요한 정보를 더 담을 수 있다)를 사용하면 더 자세한 정보를 담을 수 있다.

---

📣  BFS & DFS

𝟭. BFS(Breadth-First Search)

✔️ 너비 우선 탐색(deep이 아닌 wide하게 탐색하는 방법)
➰ 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법
➰ 최단 경로를 찾을 때 사용한다.

 

𝟮. DFS(Depth-First Search)

✔️ 깊이 우선 탐색(wide가 아닌 deep하게 탐색하는 방법)
➰ 하나의 경로를 끝까지 탐색한 후, 아니라면 다음 경로로 넘어가 탐색한다.