[TIL]200907 Graph, Tree, BST

Chaegyeom·2020년 9월 8일
0

TIL

목록 보기
28/77
post-thumbnail

그래프(Graph)

그래프(Graph)는 연결되어 있는 객체간의 관계를 표현하는 자료구조로 다양한 모델에 적용할 수 있는 유연성 있는 자료구조이다.

그래프는 노드(정점(vertex)라고도 함)와 노드와 노드를 연결하는 간선으로 구성된다.
그래프는 무방향(undircted)일 수 있는데, 이것은 간선에 의해 연결된 2개의 노드가 대칭일 수 있다는 의미이다.
다른 한편으로는 방향성(dircted)을 가질 수도 있는데, 이것은 비대칭 관계를 의미한다.

그래프 용어

그래프는 (V, E)로 표시될 수 있다.

  • V(vertices) : 정점(vertex)들의 집합
  • E(edge) : 간선(edge)들의 집합

인접(adjacency)

  • 두 정점이 하나의 간선으로 연결 되어 있는 경우
  • 아래 그림에서는 A와B, B와C, B와E, E와D는 인접이다.

경로(path) :

  • 두 정점을 연결하는 변들의 연결
  • 열결된 점점의 나열로 표기한다.
  • 아래 그림에서 A와D사이의 경로는 ABED이다.

정점(vertex)

  • 위치 (node 라고도 부름)

간선(edge)

  • 위치를 잇는 다리. 즉, 노드를 연결하는 선

인접 정점(adjacent vertex)

  • 간선에 의해 직접 연결된 정점

정점의 차수(degree)

  • 무방향 그래프에서 정점에 연결된 다른 정점의 개수
  • 무방향 그래프에 존재하는 정점의 모든 차수의 합 = 그래프의 간선 수의 2배

진입 차수(in-degree)

  • 방향 그래프에서 외부에서 오는 간선의 수 (내차수 라고도 부름)

진출 차수(out-degree)

  • 방향 그래프에서 외부로 향하는 간선의 수 (외차수 라고도 부름)
  • 방향 그래프에 있는 정점의 진입 차수 또는 진출 차수의 합 = 방향 그래프의 간선의 수(내차수 + 외차수)

경로 길이(path length)

  • 경로를 구성하는 데 사용된 간선의 수

단순 경로(simple path)

  • 경로 중에서 반복되는 정점이 없는 경우

사이클(cycle)

  • 단순 경로의 시작 정점과 종료 정점이 동일한 경우

그래프의 종류

무방향 그래프(undirected graph)

  • 간선에 방향이 없다.(양방향으로 갈 수 있다)
  • 정점의 쌍으로 표현한다
    (A, B) = (B, A)

방향성 그래프(directed graph)

  • 간선이 방향을 가지고 있다.
  • 방향성이 존재하는 간선으로 한쪽 방향으로만 갈 수 있음을 표시한다.
    <A, B>로 표시한다. <A, B> ≠ <B, A>

가중치 그래프(weighted graph)

  • 간선에 가중치가 할당된 그래프

트리(Tree)

트리는 노드로 구성된 계층적 자료구조이다. 최상위 노드(루트)를 만들고, 루트 노드의 child를 추가하고, 그 child에 또 child를 추가하는 방식으로 트리 구조를 구현할 수 있다

트리 용어

노드(node)

  • A, B, C, D 등 트리의 구성요소

루트(root)

  • 위 그림의 A처럼, 트리 구조에서 최상위에 존재하는 노드

깊이(depth)

  • 루트를 기준으로, 다른 노드로의 접근하기 위한 거리

형제(sibling)

  • 같은 부모를 가지면서 같은 depth에 존재하는 노드들을 sibling관계에 있다고 한다.

부모(parent)

  • 그림에서 B와 C의 부모는 A이다.

자식(child)

  • 그림에서 B와 C는 A의 자식이다.

간선(edge)

  • 노드와 노드를 잇는 선

잎(leaf)

  • 자식이 없는 노드

이진탐색트리(Binary Search Tree)

이진 탐색 트리는 최대 2개의 자식만 갖는 트리이다. 트리 구조는 재귀적이므로, 자식 노드 역시 최대 2개의 자식을 갖는다. 이진 탐색 트리에서는 노드의 값이 정렬 방법에 따라 순서가 존재하는데, 노드의 왼쪽 서브트리에는 노드의 값보다 작은 값이, 오른쪽 서브트리에는 노드의 값보다 같거나 큰 값이 존재한다. 이진 탐색 트리를 순회하는 방법은 크게 깊이 우선 탐색 (DFS, Depth-First Search)와 너비 우선 탐색 (BFS, Breadth-First Search) 알고리즘이 존재한다.

탐색방법

  • 전위 순회(Preorder Traversal): 루트 -> 왼쪽자식 -> 오른쪽자식 순서로 탐색한다.
    - 0 -> 1 -> 3 -> 7 -> 8 -> 4 -> 9 -> 2 -> 5 -> 10 -> 6
  • 중위 순회(Inorder Traversal): 왼쪽자식 -> 루트 -> 오른쪽자식 순서로 탐색한다.
    - 7 -> 3 -> 8 -> 1 -> 9 -> 4 -> 0 -> 10 -> 5 -> 2 -> 6
  • 후위 순회(Postorder Traversal): 왼쪽자식 -> 오른쪽자식 -> 루트 순서로 탐색한다.
    - 7 -> 8 -> 3 -> 9 -> 4 -> 1 -> 10 -> 5 -> 6 -> 2 -> 0
  • 층별 순회(level order traverse): 루트부터 아래방향으로 차례대로 탐색한다.
    - 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10

이진트리의 종류

전 이진 트리(Full Binary Tree)

  • 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리.

완전 이진 트리(Complete Binary Tree)

  • 트리를 구성하고 있는 임의의 두 단말 노드의 레벨 차이가 1이하이고, 마지막 레벨을 제외한 모든 레벨에 존재할 수 있는 모든 노드를 갖고 있으며, 왼쪽에서 오른쪽으로 채워지는 이진트리

포화 이진 트리(Perfect Binary Tree)

  • 이진트리가 보유할 수 있는 최대의 노드를 가지고 있는 형태 전 이진 트리이면서 완전 이진 트리인 경우
profile
주니어 개발자가 되고싶은

0개의 댓글