한재원

한재원

🛠️ 저는 커서 백엔드 개발자가 될래요!

[자료구조] 비선형 자료구조

Updated: Categories:

그래프와 트리 등 비선형 자료구조에 대해 알아보자

Graph

  • 정점(node, vertex)과 간선(edge)로 이루어진 자료구조
    • 간선은 가중치(weight)를 가질 수 있음
  • 방향 그래프와 무방향 그래프로 나누어짐
    • 무방향 그래프 종류
      • 연결 그래프 : 모든 정점간 경로가 존재할 때
      • 비연결 그래프 : 모든 정점간 경로가 존재하지 않을 때
  • 주요 용어
    • 차수(degree) : 무방향 그래프에서 한 정점에 인접한 정점 수(간선 수)
    • 진입 차수(in-degree) : 방향 그래프에서 내부로 향하는 간선 수
    • 진출 차수(out-degree) : 방향 그래프에서 외부로 향하는 간선 수
    • 사이클(cycle) : 경로의 시작 정점과 종료 정점이 동일한 것
  • 그래프는 인접리스트와 인접행렬로 구현됨


Binary Tree

  • 각 노드가 최대 두개의 자식을 가지는 트리

image

전 이진트리 (Full Binary Tree)

  • 모든 노드가 자식을 0개 or 2개 가지는 트리

완전 이진트리 (Complete Binary Tree)

  • 노드가 꽉 차있으며, 마지막 레벨에서는 왼쪽으로 차 있는 트리
    • 왼쪽 노드부터 순서대로 채운 트리
    • 루트노드부터 시작해서 왼쪽 자식 노드 -> 오른쪽 자식 노드 순으로 추가함
  • 배열을 통해 표현 가능

포화 이진트리 (Perfect Binary Tree)

  • 전 이진트리 + 완전 이진트리
  • 모든 레벨에서 노드가 가득 차 있는 트리


정렬 이진 트리

이진 탐색 트리 (Binary Search Tree)

  • 좌-우 노드가 부모를 기준으로 정렬된 트리
    • 왼쪽노드는 부모보다 작고, 오른쪽 노드는 부모보다 크다
    • 트리에서 가장 왼쪽에 위치한 노드가 가장 작은값을 가진다
  • 중복 키값을 허용하지 않음
  • 탐색시 성능
    • 평균 : O(logN) == 높이
    • 최악(불균형일 경우) : O(N)

힙 (Heap)

최소 힙 기준

  • 부모-자식간 정렬된 이진 트리
    • 부모는 자식보다 작다
    • 루트노드는 가장 작은 값을 가진다
  • 완전 이진트리로 구성된다
    • 배열로 표현이 가능하다
  • 노드 추가/삭제/변경시 heapify라는 재정렬이 일어난다.
    • 노드간 위치를 바꾸며 정렬하는 작업
    • 상향식/하향식으로 구현가능
    • O(logN) 시간 소요
  • 우선순위큐에서 사용됨


자가균형 이진탐색 트리

  • 시간복잡도 : O(logN)
  • 높이 균형을 스스로 유지하는 트리
    • 불균형 이진탐색트리에서 최악 탐색시간 O(N)을 방지하기 위함

AVL Tree

image

  • 모든 레벨에서 좌우 노드의 아래부터의 높이가 동일해야 한다.
    • 아래부터 위로 -> 상향식으로 계산한다.
  • 삽입/삭제/수정시 회전을 통해 불균형 문제를 해결한다

Red Black Tree

image

  • 4가지 조건을 만족해야 한다
    • 루트노드의 색깔은 검정이다
    • 모든 NIL 리프 노드의 색은 검정이다
    • 빨강 노드의 자식 노드 색은 검정이다
    • 모든 루트 노드 -> 리프 노드의 경로에서 만나는 블랙 노드의 수는 같다
  • 삽입되는 노드의 색은 무조건 빨간색이다
    • 따라서 삽입시 삼촌 노드 색에 따라 재정렬이 일어난다
      • 삼촌 노드가 검정색일때 : Restructuring
      • 삼촌 노드가 빨강색일때 : Recoloring
      • 자세한 내용은 https://zeddios.tistory.com/237


기타 트리

B Tree

  • 시간복잡도 : O(logN)
  • 자식 노드가 2개 이상인 트리
  • 하나의 노드에 여러개의 데이터를 저장가능
    • 노드의 최대 데이터 수가 n이면 n차 B-tree 이다
    • 중복 데이터는 허용하지 않는다
    • 노드의 데이터는 정렬되어 있다
  • 각 노드별로 이진 탐색트리와 유사하게 동작한다.

Trie

image

  • radix tree, prefix tree, retrieval tree
  • 시간복잡도 : O(탐색할 문자열 길이 == L)
  • 문자열 저장 및 탐색에 적합한 트리
    • 만약 문자열을 일반 이진탐색트리로 저장한다면?
      • 탐색시간은 O(logN) + 탐색하면서 문자열 비교시간 O(L) = O(L*logN)
  • 적절한 사용 : 검색어 자동완성, 사전에서의 검색, 문자열 검사