[자료구조] 트리와 그래프

트리 (Tree)

• 하나의 뿌리로부터 가지가 사방으로 뻗은 형태
• 단방향 그래프, 계층적 자료구조
• 아래로만 뻗어나가기 때문에 사이클이 없다.
  -> 사이클이 없는 하나의 연결 그래프이다.
  사이클: 시작 노드에서 출발해서 다른 노드를 거쳐 다시 시작 노드로 돌아오는 것
• 깊이, 높이, 레벨 등을 측정할 수 있다.

e.g. 컴퓨터 디렉토리 구조, 가계도, 조직도

이진 트리 (Binary Tree)

• 자식 노드가 0개~2개인 노드들로 구성된 트리
• 왼쪽 자식 노드와 오른쪽 자식 노드로 나눈다.

이진 트리 특징

• 정 이진 트리(Full binary tree): 각 노드개 0개 또는 2개의 자식 노드를 갖는다.
• 포화 이진 트리(Perfect binary tree): 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리
• 완전 이진 트리(Complete binary tree): 마지막 레벨을 제외한 모든 노드가 가득 차 있, 마지막 레벨의 노드는 왼쪽 자식 노드가 있어야 한다.

이진 탐색 트리 (Binary Search Tree)

이진 탐색 + 연결 리스트

각 노드에 중복되지 않는 key가 있다.

좌우 서브 트리들도 모두 이진 탐색 트리여야 한다.

모든 왼쪽 자식의 값이 루트나 부모보다 작다.
모든 오른쪽 자식의 값이 루트나 부모보다 크다.
=> 삽입과 삭제마다 트리의 구조 재조정이 필요할 수 있음.

이진 탐색 트리 특징

• 기존 이진 트리보다 탐색이 빠르다.
• 트리의 높이 = h, o(h)의 복잡도를 가진다.
  1. 루트 노드의 키와 찾고자 하는 값을 비교한다.
  2-1. 값이 루트 노드의 키보다 작으면 왼쪽 서브 트리 탐색
  2-2. 값이 루트 노드의 키보다 크면 오른쪽 서브 트리 탐색
  위의 과정을 반복하면 최대 h번의 연산 및 탐색이 진행된다.

---

트리 순회 (Tree Traversal)

특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것
항상 왼쪽부터 오른쪽으로 순회한다.

전위 순회 (preorder traverse)

• 루트에서 시작
• 왼쪽 노드들을 순차적으로 방문
• 왼쪽 노드 탐색이 끝나면 오른쪽 노드 탐색
• 부모 노드가 먼저 생성되어야 하는 트리를 복사할 때 사용한다.

중위 순회 (inorder traverse)

• 루트 기준으로 제일 왼쪽 끝의 노드부터 시작
  왼쪽 자식 노드 -> 루트 -> 오른쪽 자식 노드 ...
• 부모 노드가 서브 트리의 방문 중간에 방문된다.
• 이진 탐색 트리의 오름차순으로 값을 가져올 때 쓰인다.

후위 순회 (postorder traverse)

• 루트 기준으로 제일 왼쪽 끝의 노드부터 시작
  왼쪽 자식 노드 -> 오른쪽 자식노드
• 마지막 레벨부터 순회한다.
• 루트를 가장 마지막에 방문
• 트리를 삭제할 때 사용한다.

---

그래프 (Graph)

여러 개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료 구조
정점(vertex)과 간선(edge)로 이루어진다.

인접 행렬

서로 다른 정점들이 인접한 상태인지 1(true)또는 0(false)로 표시한 행렬
2차원 배열로 나타낸다.

인접하다: 두 정점이 하나의 간선으로 바로 이어져 있다

두 정점 사이에 관계가 있는지 여부를 확인하기에 용이하다.
연결 가능한 모든 경우의 수를 저장한다.
가장 빠른 경로를 찾고자 할 때 주로 사용된다.

인접 리스트

각 정점이 어떤 정점과 인접하는지 나타낸 리스트
각 정점마다 하나의 리스트를 가진다.

메모리를 효율적으로 사용하고 싶을 때 인접 리스트를 사용한다.

---

BFS와 DFS

그래프의 모든 정점을 탐색하는 대표적인 방법
모든 정점을 한 번만 방문한다.

BFS (Breadth-First Search)

너비 우선 탐색
두 정점 사이의 최단 경로를 찾을 때 사용한다.

DFS (Depth-First Search)

깊이 우선 탐색
한 정점에서 시작해서 하나의 경로를 끝까지 탐색한 후, 다음 경로로 넘어가서 탐색한다.