[C/F TIL] 62일차 - 자료구조, Tree, Graph

Code States
Front-end boost camp
Today
I
Learned

🎃 62일차

🎃 Tree

• 이름 그대로 나무(를 거꾸로 뒤집어 놓은)의 형태
• 단방향 그래프의 한 구조
• 하나의 뿌리로부터 가지가 사방으로 뻗은 형태
• 계층적으로 표현이 되고 아래로만 뻗어 나가기 때문에 사이클이 없다!
  

✔️ Tree의 구조와 특징

• 노드(Node) : 트리 구조를 이루는 모든 개별 데이터
• 루트(Root) : 트리 구조의 시작점이 되는 노드
• 부모 노드(Parent node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드
• 자식 노드(Child node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드
• 리프(Leaf) : 트리 구조의 끝 지점, 자식 노드가 없는 노드
  
• 깊이 : 루트로부터 하위 계층의 특정 노드까지의 깊이를 표현할 수 있음, 루트 노드는 지면에 있는 것처럼 깊이가 0임.
  -- 위 그림에서 루프 A의 깊이는 0이고 B와 C의 깊이는 1임.
  -- D, E, F, G의 깊이는 2
• 레벨 : 같은 깊이를 가지고 있는 노드를 묶어서 레벨로 표현. 같은 레벨에 나란히 있는 노드를 형제 노드라고 함
  -- 깊이가 0인 루트 A의 level은 1
  -- 깊이가 1인 B와 C의 level은 2
  -- D, E, F, G의 level은 3
• 높이 : 리프 노드를 기준으로 루트까지의 높이를 표현, 리프 토드와 직간접적으로 연결된 노드의 높이를 표현하며 부모 노드 자식 노드의 가장 높은 높이 값에 +1한 값을 높이로 가짐
  -- H, I, E, F, J의 높이는 0
  -- D, G의 높이는 1
  -- B와 C의 높이는 2 / 이때 B는 D의 높이 + 1, H의 높이 + 1을 가짐
  -- 따라서, A의 높이는 3
• 서버트리 : 큰 트리의 내부에, 트리 구조를 갖춘 작은 트리
  -- (D, H, I)로 이루어진 작은 트리도 서브 트리
  -- (B, D, E)나 (C, F, G, J)도 서브 트리

• 트리 예시 : 파일 탐색기, 월드컵 토너먼트 대진표, 가계도, 조직도 등

🎃 이진트리, 이진 탐색 트리

✔️ 이진 트리 : 자식 노드가 최대 두 개인 노드로 구성된 트리

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

✔️ 이진 탐색 트리

• 이진 탐색? : 정렬된 데이터 중에서 특정한 값을 찾기 위한 탐색 알고리즘 중 하나
• 이진 탐색 알고리즘은? 오름차순으로 정렬된 정수의 배열을 같은 크기의 두 부분 배열로 나눈 후, 두 부분 중 탐색이 필요한 부분에서만 탐색하도록 탐색 범위를 제한하여 원하는 값을 찾는 알고리즘
  -- 1. 배열의 중간에 내가 찾고자 하는 값이 있는지 확인
  -- 2. 중간값이 내가 찾고자 하는 값이 아닐 경우, 오름차순으로 정렬된 배열에서 중간값보다 큰 값인지 작은 값인지 판단
  -- 3. 찾고자 하는 값이 중간값보다 작은 값일 경우, 배열의 맨 앞부터 중간값 전까지의 범위를 탐색 범위로 잡고 탐색을 반복 수행
  -- 4. 찾고자 하는 값이 중간값보다 큰 값일 경우, 배열의 중간값의 다음 값부터 맨 마지막까지를 탐색 범위로 잡고 탐색을 반복 수행
• 특징
  -- 각 노드에 중복되지 않는 키(Key)가 있다.
  -- 루트노드의 왼쪽 서브 트리는 해당 노드의 키보다 작은 키를 갖는 노드들로 이루어져 있다.
  -- 루트노드의 오른쪽 서브 트리는 해당 노드의 키보다 큰 키를 갖는 노드들로 이루어져 있다.
  -- 좌우 서브 트리로 모두 이진 탐색 트리여야 함
  -- 즉, 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가짐
  -- 기존 이진트리보다 탐색이 빠름
  -- 트리 안에 찾고자 하는 값이 없더라고 최대 h번(트리의 높이) 만큼의 연산 및 탐색이 진행

🎃 트리 순회

• 특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것
• 전위 순회 : 부모 노드가 제일 먼저 방문되는 순회 방식
  -- 가장 먼저 방문하는 노드는 루트
  -- 루트에서 시작해 왼쪽의 노드들을 순차적으로 둘러본 뒤, 왼쪽의 노드 탐색이 끝나면 오른쪽 노드를 탐색
• 중위 순회 : 부모 노드가 서브 트리의 방문 중간에 방문되는 순회 방식
  -- 이진 탐색 트리의 오름차순으로 값을 가져올때 쓰임
• 후위 순회 : 루트를 가장 마지막에 순회, 트리를 삭제할 때 사용
  -- 왼쪽 끝에 있는 노드부터 순회 시작, 루트를 거치지 않고 오른쪽으로 이동해 순회한 뒤 제일 마지막 루트 방문
• 레벨 순회 : 트리의 레벨 기준으로 노드들 방문
  -- 루트 노드를 시작으로 아래로 뻗어나가며 노드들을 방문하며 루트 노드의 레벨이 1이라고 했을 때 아래로 내려갈수록 레벨 증가

순회 방식을 나누는 이유?

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

🎃 Graph

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

✔️ graph의 구조

• 직접적인 관계가 있는 경우 두 점 사아를 이어주는 선 존재
• 간접적인 관계라면 몇 개의 점과 선에 걸쳐 이어짐
• 하나의 점 : 정점(vertex)/ 하나의 선 : 간선(edge)

✔️ graph의 표현 방식

• 인접 행렬 : 두 정점을 바로 이어주는 간선이 있다면 두 정점은 인접하다.고 얘기함
  -- 한 개의 큰 표와 같은 모습을 한 인접 행렬은 두 정점 사이에 관계가 있는지, 없는지 확인하기에 용이함
  -- 가장 빠른 경로를 찾고자 할 때 주로 사용

• 인접 리스트 : 각 정점이 어떤 정점과 인접하는지 리스트 형태로 표현, 자신과 인접한 다른 정점을 담고 있다.
  -- 메모리를 효율적으로 사용하고 싶을 때 사용 : 인접 행렬은 연결 가능한 모든 경우의 수를 저장하기 때문에 상대적으로 메모리를 많이 차지함
  -- 예시 ▼
  

✔️ graph 용어

• 정점 : 노드라고도 하며 데이터가 저장되는 기본 원소
• 간선 : 정점 간의 관계를 나타냄
• 인점 정점 : 하나의 정점에서 간선에 의해 직접 연결된 정점
• 가중치 그래프 : 연결의 강도가 얼마나 되는지 적혀 있는 그래프
• 비 가중치 그래프 : 연결의 강도가 적혀있지 않은 그래프
• 무향(무방향) 그래프 : 서울에서 부산으로 갈 수 있듯 반대로 부산에서 서울로도 갈 수 있음. 하지만 단방향 그래프로 구현됟나면 서울에서 부산으로 갈 수 있지만 부산에서 서울은 불가. 만약 두 지점이 일방통행 도로로 이어져 있따면 단방향인 간선으로 표현 가능
• 진입차수/ 진출차수 : 한 정점에 진입하고 진출하는 간선이 몇 개 인지 나타냄
• 인접 : 두 정점 간의 간선이 직접 이어져 있는 경우
• 자기 루프 : 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다고 표현, 다른 정점 거치지 않음
• 사이클 : 한 정점에서 출발해 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현.

🎃 BFS와 DFS

✔️ BFS(Breathed-First Search)

• 너비 우선 탐색 : 두 정점 사이의 최단 경로를 찾을 때 사용
• 현재 있는 노드에서 가까운 곳부터 탐색하므로 경로를 탐색하는 도중 가장 먼저 발견한 해답이 최단거리라는 보장 가능

✔️ DFS(Depth-First Search)

• 깊이 우선 탐색 : 깊이를 먼저 탐색, 한 정점에서 시작해서 다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색할 때 사용
• 탐색 시간은 조금 오래 걸릴지라도 모든 노드를 완전히 탐색 가능
• 하나의 경로를 끝까지 탐색한 후, 미국(도착지) 도착이 아니라면 다음 경로로 넘어가 탐색
• 하나의 노선을 끝까지 들어가서 확인하고 다음으로 넘어가기 때문에, 운이 좋다면 단 몇 번 만에 경로를 찾을 수 있음.
• 또는 목적지로 가는 길이 아님을 미리 체크할 수 있다면 바로 그 다음 탐색으로 넘어감