[TIL] 자료구조 : 트리, 그래프, 이진탐색트리

🙌🏻  트리 Tree

  - 데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연겨된 계층적 자료구조

  - 그래프 중 단방향 그래프로 하나의 뿌리로부터 가지가 사방으로 뻗은 형태

  - 계층적, 비선형구조

  - ex) 파일 탐색기, 가계도, 조직도, 축구 대진표 등

  ▪️ 루트 Root

   - 하나의 꼭지점 데이터로 루트를 시작으로 여러 개의 데이터를 간선(edge)로 연결

  ▪️ 노드 Node

   - 각 데이터를 노드로 하며 두 노드가 상하로 연결되면 부모-자식 관계를 가짐

  ▪️ 리프 Leaf

   - 트리 구조의 끝 지점으로 자식 노드가 없음

---

📍 트리 메서드 

① addChildNode(value)

  - 입력받은 value를 계층적으로 추가 

② removeChildNode(node)

  - 입력받은 노드를 삭제

③ getChildrenNode()

  - 현재 트리에 존재하는 children 리턴

④ contains(value)

  - 트리에 포함된 데이터 찾기

 

---

🙌🏻  그래프 Graph

  - 여러 개의 점들이 서로 복잡하게 연결되어 있는 관계

  - ex) 포털사이트 검색엔진, SNS 속 인간관계, 내비게이션 등

  - 간선은 특정 정점이 이어져있다는 사실만 알려줄 뿐 그 외 정보는 파악할 수 없음 ( = 비가중치 그래프 )

  - 비가중치 그래프에 더 자세한 정보를 담아 간선에 연결 정도를 표현한 그래프 ( = 가중치 그래프 )

  - 무방향 그래프 ? 내비게이션 처럼 양방향으로 간선을 표현 ( 일반통행과 같은 경운은 단방향 )

  ▪️  정점 Vertex

   - 데이터가 저장되는 그래프의 기본 원소이자 노드

  ▪️ 간선 edge

   - 정점을 이어주며 정점 간 관계를 나타냄

  ▪️ 인접 정점 adjacent vertex

   - 하나의 정점에서 간선에 직접 연결된 정점

  ▪️ 진입 차수 / 진출 차수 in-degree / out-degree

   - 한 정점에 진입 / 진출하는 간선이 몇 개인지 나타냄

  ▪️ 자기 루프 self loop

   - 다른 정점을 거치지 않고 간선이 자기 자신에게 진입할 때 씀

  ▪️ 사이클 cycle

   - 한 정점에서 출발하여 다시 그 정점으로 돌아갈 수 있는 경우

---

📍 그래프의 표현방식

  ▪️ 인접 행렬

   - 서로 다른 정점들이 인접한 상태인지 표시한 2차원 행렬

   - 두 정점 사이에 관계가 있는지 없는지 확인하기 위해 사용

   - 가장 빠른 경로를 찾고자 할 때 주로 사용

 

  ▪️ 인접 리스트

   - 각 정점마다 정점이 어떤 정점과 인접하는지 리스트로 표현

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

   - 연결 가능한 모든 경우의 수를 저장하여 상대적으로 메모리 많이 차지

---

📍 그래프 메서드

① setGraph(size)

  - 그래프에 사이즈만큼 정점을 추가해야 함

② getGraph()

  - 인접 행렬 정보가 담긴 배열 반환

③ addEdge(from, to) 

  - from정점과 to정점 사이에 간선을 추가

④ hasEdge(from, to)

  - from정점과 to정점 사이에 간선의 존재 여부를 true/false로 반환

⑤ removeEdge(from, to)

  - from정점과 to정점 사이의 간선 삭제

---

🙌🏻  이진탐색트리 Binary Search Tree

📍 이진 트리

 - 자식 노드가 최대 두 개인 노드들로 구성된 트리

---

📍 이진 탐색 트리

 - 모든 왼쪽 자식의 값이 루트나 부모보다 작고 오른쪽 자식 값은 루트나 부모보다 큰 값을 가짐

---

📍 이진 탐색 트리 메서드

① insert(value)

  - 입력받은 값을 계층적으로 추가

② contains(value)

  - 트리에 포함된 값 찾기

③ preorder(root, depth, list)

  - 전위 순회를 통해 트리의 모든 요소를 정렬하여 ArrayList 타입으로 반환

④ inorder(root, depth, list)

  -중위 순회를 통해 트리의 모든 요소를 정렬하여 ArrayList 타입으로 반환

⑤ postorder(root, depth, list)

 - 후위 순회를 통해 트리의 모든 요소를 정렬하여 ArrayList 타입으로 반환

---

💡전위 순회 

---

💡중위 순회

---

💡후위 순회 

---

📍그래프의 모든 정점 탐색 방법

① 너비 우선 탐색 : BFS(Breathed First Search)

  - 너비를 가장 우선적으로 탐색하는 방법

  - 최단 거리를 알아내는 것과 유사

    (1) 루트와 가장 가까운 정점부터 탐색

    (2) 더 이상 탐색할 정점이 없을 때, 그 다음 떨어져있는 정점을 순서대로 방문

 * 장점
 (1) 너비를 우선으로 탐색하여 답이 되는 경로가 여러 개인 경우에도 최단 경로임을 보장
 (2) 최단 경로가 존재한다면 어느 한 경로가 무한히 깊어도 최단 경로를 찾을 수 있음
 (3) 노드 수가 적고 깊이가 얕은 해가 존재할 때 유리

 * 단점
 (1) 큐를 이용하여 탐색할 노드를 저장하기 때문에 노드가 많을 수록 더 큰 저장 공간 필요
 (2) 노드 수가 늘어나면 탐색할 노드가 많아저 비효율적

---

② 깊이 우선 탐색 : DFS(Depth First Search)

   - 깊이를 우선적으로 탐색

   - 한 정점에서 시작하여 다음 경로로 넘어가기 전 해당 경로를 완벽하게 탐색

   - BFS 보다 탐색 시간은 걸리지만 모든 노드를 완전히 탐색 가능

      (1) 하나의 경로를 처음부터 끝까지 탐색

      (2) 다음 경로로 넘어가 처음부터 끝까지 탐색을 반복

 * 장점
 (1) BFS에 비해 저장공간이 필요성이 적음
 (2) 찾아야 하는 노드가 깊은 단계에 있을 수록, 좌측에 있을수록 BFS보다 유리
 
 * 단점
 (1) 답이 아닌 경로가 매우 깊다면 그 경로에 깊이 빠질 우려가 있음
 (2) 찾은 해가 최단 경로라는 보장이 없음