Home Study | 자료구조 트리와 그래프
Post
Cancel

Study | 자료구조 트리와 그래프

자료구조 트리와 그래프

목차

  1. 그래프
  2. 트리
    2-1. 이진트리
    2-2. 완전 이진트리


1. 그래프

: 노드와 그 노드를 연결하는 간선(edge)들로 구성된 자료구조

  • 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조 Ex. 지하철 노선도, 도로, 검색엔진
  • 네트워크 모델
  • 노드들 사이에 방향/무방향 경로를 가질 수 있음
  • 순환 혹은 비순환
  • 방향 그래프와 비방향 그래프
  1. 그래프의 용어

    용어
    • 정점(vertext) : 위치라는 개념
    • 간선(edge) : 정점을 연결하는 선
    • 인접 정점(adjacent vertex) : 간선에 직접 연결된 정점
    • 차수(degree) : 한 정점에 연결된 간선의 수 (주로 무방향 그래프에서 사용)
    • 입력 차수(in-degree) : 한 정점으로 들어오는 간선의 수 (주로 방향그래프에서 사용)
    • 출력 차수(out-degree) : 한 정점에서 나가는 간선의 수(주로 방향그래프에서 사용)
    • 사이클(cycle) : 한 정점에서 출발하여 시작했던 정점으로 돌아오는 경로
    • 가중치 그래프 : 간선마다 가중치 값이 매겨져있는 그래프


  2. 그래프의 종류

    • 무방향 그래프(Undirected Graph)

      • 간선을 통해 양방향으로 갈 수 있다.
      • 정점 A와 정점 B를 연결하는 간선은 (A,B), (B,A)

        이미지

        무방향

    • 방향 그래프(Directed Graph)

      • 간선에 방향성이 존재하는 그래프
      • A -> B로 갈 수 있는 간선은 (A, B)로 표시

        이미지

        무방향

    • 가중치 그래프(Weighted Graph)

      • 간선을 이동하는데 비용이나 가중치가 할당된 그래프
      • 네트워크라고도 함

        이미지

        무방향


  3. 그래프의 구현방법

    • 인접 리스트
    • 인접 행렬

2. 트리

: 노드(node)와 브랜치(branch)를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조 Ex. 회사의 전체 조직도, 족보

  • 계층 모델
  • 비순환 그래프
  • 노드가 N개인 트리는 항상 N-1개의 간선을 가짐
  • 루트 노드가 존재하고, 루트노드를 시작으로 부모와 자식관계가 형성
  • 자식노드는 반드시 한개의 부모노드만을 가짐(두 정점 사이에는 반드시 한개의 경로)
  1. 트리의 용어

    용어

    트리

    • 루트 노드(root node) : 부모가 없는 노드, 트리는 하나의 루트 노드 만을 가짐
    • 단말 노드(leaf node) : 자식이 없는 노드
    • 내부(internal) 노드 : 단말 노드가 아닌 노드
    • 간선(edge) : 노드를 연결하는 선
    • 형제(sibling) : 같은 부모를 가지는 노드
    • 조상 노드(ancestors node) : 임의의 노드에서 루트 노드에 이르는 경로상에 있는 노드들 (D의 조상은 B, A이다)
    • 노드의 크기(size) : 자신을 포함한 모든 자손 노드의 개수
    • 노드의 깊이(depth) : 루트에서 어떤 노드에 도달하기 위해 커쳐야하는 간선 수
    • 노드의 레벨(level) : 트리의 특정 깊이를 가지는 노드의 집합
    • 노드의 차수(degree) : 각 노드에서 뻗어나온 가지의 수 (D의 차수는 2이다.)
    • 트리의 차수(degree of tree) : 트리에서 가장 큰 차수
    • 트리의 높이(height) : 가장 깊숙히 있는 노드의 깊이 (3)


  2. 트리의 종류 : 이진트리, 이진 탐색 트리, 균형 트리, 이진 힙

2-1. 이진트리

: 자식을 최대 2개만 가지고 있는 트리(모든 노드의 차수가 2 이하인 트리)

  1. 이진트리와 이진 탐색 트리
    • 이진트리 : 루트 노드의 최대 브랜치가 2개인 트리이며, 사이클을 이루지 않도록 구성한 데이터 구조
    • 이진 탐색 트리 : 이진 트리 + 추가 조건 (왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가지고 있음) Ex. 데이터 검색

2-2. 완전 이진트리(+ 불완전 이진트리)


완전 이진트리

이미지 출처 : https://www.techiedelight.com/ko/check-given-binary-tree-complete-binary-tree-not/


완전 이진트리 : 부모노드에서 시작해, 좌측에서부터 채워져 있는 구조


그래프와 트리 비교

 그래프트리
정의노드와 노드를 연결하는 간선으로 표현되는 자료 구조그래프의 한 종류, 방향성이 있는 비순환 그래프
핵심 표현개체간의 ‘관계’ 표현개체를 ‘계층’ 그조로 표현
방향성방향 그래프, 무방향 그래프 둘 다 존재함방향 그래프만 존재함
사이클사이클 가능함, 순환 및 비순환 그래프 모두 존재함비순환 그래프로 사이클이 존재하지 않음
루트 노드루트 노드 존재하지 않음루트 노드 존재함
부모/자식 관계부모 자식 개념이 존재하지 않음부모 자식 관계가 존재함






출처

트리와 그래프
트리
트리와 그래프 비교
트리와 그래프 디테일한 설명
완전이진트리

This post is licensed under CC BY 4.0 by the author.