TIL 6 | 자료구조 - 그래프, 트리, 힙, 트라이

grighth12·2021년 8월 10일
2

TIL

목록 보기
6/15
post-thumbnail

비선형 자료구조는 다 그래프의 일종이므로 한 번에 정리해보자.

그래프

  • 정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조이다.
  • 인물 관계도, 지하철 노선도, 페이지 랭크(검색 알고리즘)에 활용될 수 있다.
  • 그래프는 사이클이 발생할 수 있으므로 탐색 시에 무한 루프에 빠지지 않도록 사이클을 찾아야 할 필요가 있다.

간선의 방향성에 따른 분류

1. 무방향 그래프

  • 간선의 방향이 존재하지 않는다.
  • 하나의 간선으로 양방향으로 이동이 가능하다.

2. 방향 그래프

  • 간선에 방향성이 존재한다.
  • 양방향으로 이동할 수 있더라도 a-b와 b-a는 다른 간선으로 취급된다.
  • 일방통행이 가능하다.

연결 상태에 따른 분류

1. 연결 그래프

  • 모든 정점이 서로 이동 가능한 상태인 그래프

    모두 연결되어 있는 것이 아니라, 하나의 정점에서 모든 정점으로 타고타고 이동할 수 있으면 연결 그래프라고 한다.

2. 비연결 그래프

  • 특정 정점 쌍 사이에 간선이 존재하지 않는 그래프

3. 완전 그래프

  • 모든 정점이 연결된 상태인 그래프

사이클

  • 그래프의 정점과 간선의 부분 집합에서 순환이 되는 부분

구현 방법

1. 인접 행렬(2차원 배열)

const graph = Array.from(Array(5), () => Array(5).fill(false));
  • graph[a][b] === true이면, ab는 연결되어 있다는 의미이다.
  • 방향 그래프에서는 graph[a][b]graph[b][a]를 구분한다.
  • 무방향 그래프에서는 모든 값을 대칭으로 넣어주면 된다.

2. 인접 리스트(연결 리스트)

const graph = Array.from(Array(5), () => []);
//graph[a].push(b) a --> b
  • graph[a].push(b)ab가 연결되어 있다는 의미이다.

트리


  • 트리는 몇 가지 제약이 있는 방향 그래프의 일종이다.
    • 루트 정점을 제외한 모든 정점은 반드시 하나의 부모 정점을 가진다.
    • 정점이 N개인 트리는 반드시 N-1개의 간선을 가진다.
    • 하나의 부모 정점을 가지기 때문에, 루트에서 특정 정점으로 가는 경로는 반드시 하나만 존재한다.
  • 트리의 용어
    • root: 가장 상위의 정점
    • leaf node : 더 이상 자식이 없는 정점
    • level : 루트로부터 몇 번째 깊이인지 표현
    • degree : 한 정점에서 뻗어나가는 정점의 수

이진 트리

  • 각 정점이 최대 2개 자식을 갖는 트리이다.
  • 탐색을 위한 알고리즘에 많이 쓰인다.
  • 정점이 n개인 이진 트리는 최악의 경우 높이가 n이 될 수 있다. (편향 트리)
  • 정점이 n개인 포화 또는 완전 이진 트리의 높이는 log n이다.
  • 높이가 h인 포화 이진 트리는 2^h - 1 개의 정점을 가진다.
  • 일반적인 이진 트리를 사용하는 경우는 많지 않고, 응용을 자주한다.
    • 이진 탐색 트리, 힙, AVL 트리, 레드 블랙 트리 등을 구현하기 위해 사용된다.

1. 완전 이진 트리

  • 마지막 레벨을 제외하고 모든 정점이 채워져 있는 트리

    순서대로 들어가야만 완전 이진 트리라고 할 수 있다. 만약 아래 그림에서 FC의 left에 연결 되어있다면 완전 이진 트리라고 할 수 없다.

2. 포화 이진 트리

  • 마지막 레벨도 모두 채워져 있는 트리

3. 편향 트리

  • 한 방향으로만 정점이 이어지는 트리

구현 방법

트리는 그래프의 한 종류이므로 그래프와 마찬가지로 인접행렬, 인접 리스트 두가지 방식으로 트리를 표현할 수 있다. 일반적인 트리는 그래프와 구현하는 것이 크게 다르지 않다.

이진 트리의 경우 배열 혹은 링크가 두 개 존재하는 연결리스트로 구현할 수 있다. 배열로 구현할 경우에는 인덱스 값을 2로 나누거나 곱해서 간단히 자식, 부모 노드의 인덱스를 구할 수 있다.

  • 현재 나의 인덱스를 index라 하면,
    부모의 인덱스는 Math.floor(index/2)
    left 자식의 인덱스는 index*2
    right 자식의 인덱스는 index * 2 + 1

  • 힙은 우선순위 큐를 구현하기에 적합한 자료구조이다.
  • 이진 트리 형태로 우선 순위가 높은 요소를 루트에 두기 위해 요소가 삽입, 삭제 될 때 바로 정렬된다.
  • 최대 힙과 최소 힙이 있다.

    우선순위 큐
    우선순위 큐는 자료구조가 아니라 우선 순위가 높은 요소가 더 먼저 나간다는 개념이다. 만약, 매번 배열을 우선순위에 따라 정렬한다면 그것또한 우선순위 큐라고 할 수있다. 효율을 생각했을 때 우선순위 큐를 구현하기에 자료구조인 힙이 가장 적합한 것이다. 힙과 우선순위 큐를 같은 말이라고 착각하지 말자!

동작

요소 추가

  • 추가할 요소를 트리의 가장 마지막 정점에 위치한다.
  • 부모의 우선 순위보다 추가된 요소의 우선 순위가 낮을 때까지, 부모와 비교하여 우선순위가 높다면 부모 정점과 위치를 바꾼다.
  • 요소는 항상 트리의 가장 마지막 정점에 들어가기 때문에 힙은 항상 이진 트리가 된다.
    그렇기 때문에, 트리의 높이는 log n이 되고, 요소 추가 알고리즘은 최악의 구조에도 log n이라는 짧은 시간안에 가능하다.

요소 제거

  • 루트 정점만 제거가 가능하다.
  • 루트 정점을 제거한 후, 가장 마지막 정점을 루트에 위치시킨다.
  • 추가와 반대로, 자식 요소보다 우선순위가 높아질 때 까지, 현재 위치의 두 자식 정점 중 더 우선 순위가 높은 정점과 비교하여 위치를 바꿔 나간다.
  • 추가와 똑같이 log n 시간이 걸린다.

트라이

  • 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조이다.
  • 간선은 이전 정점으로부터 새롭게 추가되는 문자 정보를 가지고, 정점은 이전 정점으로 부터 더해진 문자열 정보를 가지고 있다.
  • 자동 완성, 사전 찾기에 응용될 수 있다.
  • 보통 문자열을 탐색할 때, 저장되어 있는 문자열의 개수 * 탐색할 문자열의 길이 만큼 시간복잡도가 걸리지만, 트라이를 사용하면 문자열의 길이만큼만 시간 복잡도가 걸린다. O(L)
  • 대신 각 정점이 자식에 대한 링크를 전부 가지고 있기 때문에, 저장 공간을 더 많이 사용한다.
  • 트라이의 노드는 자신의 value와 간선의 값과 연결된 노드 정보를 가지고 있는 해시 테이블을 변수로 가지고 있다.

트라이를 트리로 표현하면 아래와 같다.

실제 자료구조로 생각하면 다음과 같다. Nodechidren은 해시 테이블이다. key 값은 이전 노드의 value에 추가될 값(간선의 값)으로 하고, value는 생성된(이전 문자열 + 간선의 값을 value로 하는) Node로 설정한다.

참고 자료 및 강의

프로그래머스 프론트엔드 데브코스 Day3 & 4 [강의] 그래프, 트리, 힙, 트라이
profile
데굴데굴 굴러가고 있습니다

0개의 댓글