Section4 / Unit1 : Tree, Graph

트리(Tree)

계층적 자료구조, 단방향 그래프

아래로만 뻗어나가기 때문에 사이클(cycle)이 없다
→ 트리는 사이클이 없는 하나의 연결 그래프(Connected Graph)

트리 관련 용어

• 노드(node) : 각 데이터
• 간선(edge) : 각 데이터를 간선으로 연결
• 루트 노드(root) : 부모가 없는 최상위 노드
• 단말 노드(leaf node) : 자식이 없는 노드
• 크기(size) : 트리에 포함된 모든 노드의 개수
• 깊이(depth) : 루트 노드부터의 거리
• 높이(height) : 깊이 중 최댓값
• 레벨(level) : 같은 깊이를 가지고 있는 노드 묶음
• 차수(degree) : 각 노드의(자식방향) 간선 개수
• 서브 트리(sub tree) : 트리 구조를 갖춘 작은 트리
• 기본적으로 트리의 크기가 N일 때, 전체 간선의 개수는 N-1개

예제

• 컴퓨터의 디렉토리 구조(파일 구조)

 

이진트리(Binary tree)

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

자료의 삽입, 삭제 방법에 따라

이진트리의 종류

이진트리 특징

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

이진 탐색 트리(Binary Search Tree)

이진 탐색의 속성이 이진트리에 적용된 특별한 형태의 이진트리

 

이진 탐색

이진 탐색 알고리즘이란 정렬된 데이터 중에서 특정한 값을 찾기 위한 탐색 알고리즘 중 하나

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

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

루트노드는 이진 탐색에서 리스트의 중간값
→ 루트노드 왼편 : 루트노드의 값보다 작은 값
→ 루트노트 오른편 : 루트노드의 값보다 큰 값

이진 탐색 트리 특징

• 각 노드에 중복되지 않는 키(key)가 있다
• 루트노드의 왼쪽 서브 트리는 해당 노드의 키보다 작은 키를 갖는 노드들로 구성
• 루트노드의 오른쪽 서브 트리는 해당 노드의 키보다 큰 키를 갖는 노드들로 구성
• 좌우 서브 트리도 모두 이진 탐색 트리여야 함
• 기존 이진트리보다 탐색이 빠르다
  • 트리의 높이가 h(height) 라면 o(h)의 복잡도를 가진다

 

트리 순회(Tree Traversal)

트리 자료구조에 포함된 노드를 특정한 방법으로 한 번씩 방분하는 방법

대표적인 트리 순회 방법

• 전위 순회(pre-order traverse) : 루트를 먼저 방문
• 중위 순회(in-order traverse) : 왼쪽 자식을 방문한 뒤에 루트를 방문
• 후위 순회(post-order traverse) : 오른쪽 자식을 방문한 뒤에 루트를 방문

---

그래프(Graph)

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

Graph의 구조

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

Graph의 표현 방식

그래프 예시

• 인접 행렬
  • 두 정점을 바로 이어주는 간선이 있다면 이 두 정점은 인접하다고 한다
  • 인접 행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 행렬, 2차원 배열의 형태
  • 해당 정점이 이어져 있다면 1(true), 이어져 있지 않다면 0(false)으로 표시한 일종의 표
  • 만약 가중치 그래프라면 1 대신 관계에서 의미 있는 값을 저장
  • 예시
    • A의 진출차수는 1개입니다: A —> C                  // [0][2] === 1
    • B의 진출차수는 2개입니다: B —> A, B —> C   // [1][2] === 1, [1][2] === 1
    • C의 진출차수는 1개입니다: C —> A                  // [2][0] === 1
• 인접 리스트
  • 각 정점이 어떤 정점과 인접하는지를 리스트의 형태로 표현
  • 각 정점마다 하나의 리스트를 가지고 있으며,
    이 리스트는 자신과 인접한 다른 정점을 담고 있다.
  • 예시
    • A→C→Null
    • B→A→C→Null
    • C→A→Null
    • 순서는 중요하지 않다
      우선순위를 다뤄야 한다면 더 적합한 자료구조(ex. queue, heap)를 사용하는 것이 합리적

Graph 용어

• 정점(vertex) : 노드(node)라고도 하며 데이터가 저장되는 그래프의 기본 원소
• 간선(edge) : 정점 간의 관계를 나타냄 (정점을 이어주는 선)
• 인접 정점(adjacent vertex) : 하나의 정점에서 간선에 의해 직접 연결된 정점을 의미
• 가중치 그래프(weighted Graph) : 연결의 강도가 얼마나 되는지 적혀 있는 그래프
• 비 가중치 그래프(unweighted Graph) : 연결의 강도가 적혀 있지 않는 그래프
• 무향(무방향) 그래프(undirected graph) : 단방향 그래프
• 진입차수(in-degree) / 진출차수(out-degree) :들어오는 간선, 나가는 간선
• 인접(adjacency) : 두 정점 간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점이다
• 자기 루프(self loop) : 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우(다른 점정을 거치지 않음)
• 사이클(cycle) : 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다

Graph 예제

• 포털사이트의 검색 엔진
• SNS에서 사람들과의 관계
• 내비게이션

---

BFS(Breadth-First Search)

너비 우선 탐색

최단 경로를 찾을 때 사용

 

DFS(Depth-First Search)

깊이 우선 탐색

모든 노드를 완전히 탐색할 수 있음