[알고리즘] 트리, 그래프

트리

• 단방향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태입니다.
• 하나의 방향으로만 연결된 계층적 자료구조입니다.
• 하나의 데이터 아래에 여러 개의 데이터가 존재하는 비선형 구조입니다.
• 루트(Root)라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터(Node)를 간선(edge)으로 연결합니다.

 

출처 : 코드스테이츠 [자료구조/알고리즘] 기초 학습자료 

트리 용어

• 노드 종류
  1. 루트노드 : 트리의 최상위에 있는 노드
  2. 리프노드 : 트리가 더 뻗어 나갈 수 없는 가장 마지막에 있는 노드
  3. 부모노드 : 자식노드를 갖고 있는 상대적으로 루트노드에 가까운 상위노드
  4. 자식노드 : 부모ㄷ노드에 달려 있는 상대적으로 루트노드에서 먼 하위노드
• 서브트리 : 트리 안에 있는 특정 노드를 루트노드로 하는 트리
• 깊이 : 루트로부터 하위 계층의 특정 노드까지의 깊이(depth)
• 높이 : 리프 노드를 기준으로 루트까지의 높이(height)

 

---

 

이진 탐색 트리(Binary Search Tree)

이진 탐색 트리란 이진 탐색의 속성이 이진트리에 적용된 형태의 이진트리입니다.

 

이진트리

자식 노드가 최대 두 개인 노드로 구성된 트리입니다. 이진트리는 자료의 삽입, 삭제 방법에 따라 정 이진트리, 완전 이진트리, 포화 이진트리로 나뉩니다.

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

 

이진 탐색

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

1. 배열의 중간값이 내가 찾고자 하는 값인지 확인합니다.
2. 중간값이 원하는 값이 아닌 경우
   • 원하는 값이 중간값보다 큰 경우, 중간값의 다음 값부터 탐색 범위 마지막까지를 범위로 잡고 탐색을 반복 수행합니다.
   • 원하는 값이 중간값보다 작은 경우, 탐색 범위 처음부터 중간값의 이전 값까지를 범위로 잡고, 탐색을 반복 수행합니다.
3. 중간값이 원하는 값일 경우 탐색을 종료합니다.

 

이진 탐색 트리(Binary Search Tree)

 

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

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

 

---

 

트리 순회

특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것을 트리 순회라고 합니다.

 

순회 종류

1. 전위 순회
   • 가장 먼저 루트 노드를 방문합니다.
   • 루트에서 시작해 왼쪽의 노드들을 순차적으로 둘러본 후, 왼쪽의 노드 탐색이 끝나면 오른쪽 노드를 탐색합니다.
   • 10(root) > 7 > 5 >3 > 6 > 9 > 12 > 11 > 14 > 15 (중간>왼쪽>오른쪽)
   • 전위 순회는 주로 트리를 복사할 때 사용합니다.
2. 중위 순회
   • 가장 먼저 제일 왼쪽 끝에 있는 노드를 방문합니다.
   • 제일 왼쪽 끝에 있는 노드에서 시작해 루트를 기준으로 왼쪽에 있는 노드의 순회가 끝나면 루트를 거쳐 오른쪽에 있는 노드로 이동하여 마저 탐색합니다.
   • 3 > 5 > 6 > 7 > 9 > 10(root) > 11 > 12 > 14 > 15 (왼쪽 >중간>오른쪽)
   • 중위 순회는 오름차순으로 값을 가져올 때 사용합니다.
3. 후위 순회
   • 가장 먼저 제일 왼쪽 끝에 있는 노드를 방문합니다.
   • 제일 왼쪽 끝에 있는 노드에서 시작해 루트를 거치지 않고, 오른쪽으로 이동해 순회한 뒤, 제일 마지막에 루트를 방문합니다.
   • 3 > 6 > 5 > 9 > 7 > 11 > 14 > 15 > 12  > 10(root) (왼쪽>오른쪽>중간)
   • 후위 순회는 트리를 삭제할 때 사용합니다.
4. 레벨 순회
   • 트리의 레벨 기준으로 노드들을 방문하는 순회 방법입니다.
   • 루드 노드를 시작으로 아래로 뻗어나가며 노드들을 방문합니다.
   • 동일한 레벨에 여러 노드가 존재할 경우 왼쪽에서 오른쪽 순서로 노드를 방문합니다,
   • 10(root) > 7 > 12 > 5 > 9 > 11 > 15 > 3 > 6 > 14

 

---

 

그래프

 

그래프의 구조

• 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있습니다.
• 하나의 점을 그래프에서는 정점(vertes)이라고 표현하고, 하나의 선은 간선(edge)라고 합니다.

 

그래프의 표현 방식

1. 인접 행렬
   • 두 정점을 바로 이어주는 간선이 있다면 두 정점은 인접하다고 표현합니다.
   • 인접 행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 행렬로  2차원 배열의 형태로 나타냅니다.
   • 두 정점이 이어져 있다면 1(true), 이어져 있지 않다면 0(false)로 표시한 표입니다.
   • 최단 경로를 찾고자 할 때 주로 사용됩니다.
2. 인접 리스트
   • 각 정점이 어떤 정점과 인접하는지를 리스트의 형태로 표현합니다.
   • 각 정점마다 하나의 리스트를 가지고 있으며, 이 리스트는 자신과 인접한 다른 정점을 담고 있습니다.
   • 메모리를 효율적으로 사용하고 싶을 때 사용합니다.

 

인접 행렬

 

인접 리스트

 

그래프 탐색

https://comhwang.tistory.com/19

[알고리즘] DFS/BFS