트리와 그래프의 공통점

트리와 그래프는 여러 개의 노드(Node)와 간선(Edge) 으로 이루어져 있는 자료구조로 데이터를 연결하여 표현하는 데 사용된다.

1. 기본 구성 요소

  • 노드(Node, 정점): 데이터를 저장하는 기본 단위
  • 간선(Edge, 엣지): 노드 간의 관계(연결)를 나타냄 → 예: A → B (A에서 B로 이동 가능)

2. 네트워크 및 관계를 표현하는 데 사용

  • 모두 객체 간의 관계나 연결을 표현하는 데 적합하다.
  • 예
    • 네트워크 라우팅(컴퓨터 간 연결)
    • 조직도, 폴더 구조 등

3. 탐색 방법이 동일하다

트리와 그래프 모두 DFS(깊이 우선 탐색) 및 BFS(너비 우선 탐색) 을 사용할 수 있다.

  • DFS(Depth-First Search, 깊이 우선 탐색)

    → 한 방향으로 끝까지 탐색한 후 되돌아가는 방식

    → 예: 미로 찾기, 백트래킹 문제

  • BFS(Breadth-First Search, 너비 우선 탐색)

    → 가까운 노드부터 탐색하며, 계층적으로 방문하는 방식

    → 예: 최단 경로 찾기 (네비게이션, 지하철 노선 탐색)

4. 방향 개념 적용 가능

  • 트리와 그래프 모두 방향성(Directed)과 무방향성(Undirected) 을 가질 수 있다.
    • 방향: 부모 → 자식으로만 이동 가능
    • 무방향: 양방향 이동 가능

차이점

  • 트리는 그래프의 한 종류지만 순환이 없는 방향 그래프이다.
  • 그래프는 순서 없이 노드 간의 관계가 자유롭다.
  • 트리는 모든 노드가 연결되어 있지만, 그래프는 연결되지 않은 노드가 있을 수 있다.

트리(Tree)

  • 계층적 구조로, 부모-자식 관계로 연결된 노드들의 집합이다.
  • 하나의 루트 노드와 0개 이상의 하위 트리로 구성되어 있다.
  • 트리의 각 노드는 하나의 데이터와 자식 노드에 대한 포인터를 가진다.
  • 순환하지 않는 무방향 그래프 구조다.

용어

  1. 노드(Node): 데이터를 저장하는 기본 단위.
  2. 루트(Root): 트리의 최상단 노드.
  3. 자식 노드(Child): 특정 노드가 가리키는 다음 단계의 노드.
  4. 부모 노드(Parent): 특정 노드를 가리키는 상위 노드.
  5. 리프 노드(Leaf): 자식이 없는 끝 노드.
  6. 서브트리(Subtree): 특정 노드를 루트로 하는 트리 구조.

종류

  • 이진 트리: 각 노드가 두 개의 자식 노드를 가질 수 있는 트리.
  • 이진 탐색 트리(BST): 왼쪽 서브트리는 부모보다 작은 값, 오른쪽 서브트리는 부모보다 큰 값을 가지는 이진 트리.
  • AVL 트리: 자가 균형 이진 탐색 트리. 높이 차이를 1로 유지.
  • 힙(Heap): 완전 이진 트리

활용

  • 트리는 계층적 데이터 표현
    • 파일 및 폴더
  • 검색
    • 삽입, 삭제 및 검색에 효율적
    • 데이터 베이스 인덱스

트리의 탐색

전위, 중위, 후위

[이진 트리] (https://github.com/Hi-Tech-Study/CS-Study/blob/main/Data%20Structure/ds_binary_tree.md)

트리의 한계

  1. 노드 간 다대다(M:N) 관계를 표현할 수 없다.
    • 트리는 기본적으로 부모-자식 관계(1:N)만을 표현할 수 있다.
    • 현실에서는 하나의 노드가 여러 부모(혹은 상위 개체)와 연결되는 경우도 있다.
      • 한 학생이 여러 개의 수업을 듣는 경우 (수업-학생)
  2. 순환(Loop) 구조를 표현할 수 없다.
    • 트리는 사이클(순환)이 없는 구조여야 한다.
    • 현실에서는 순환이 필요한 경우
      • 네트워크에서 백업 경로를 설정할 때 (라우팅)
      • 교통 경로에서 순환 노선이 존재할 때 (지하철 노선)
  3. 특정 노드 간의 직접적인 연결이 어렵다.
    • 트리는 부모-자식 관계를 따라가야 하므로, 멀리 떨어진 노드 간 연결이 어렵다.

그래프(Graph)

그래프는 노드와 노드 간의 관계로 이루어져 있다. 트리는 계층적 관계를 표현하는 데 유리하지만, 다대다 관계나 순환이 필요한 경우 확장이 어렵다. 따라서 그래프를 활용하면 더 유연한 구조를 만들 수 있다.

  1. 더 복잡한 관계 모델링 가능
  2. 유연한 데이터 탐색 및 경로 최적화 가능
    • 트리는 특정 노드까지 도달하는 경로가 한 가지뿐이지만, 그래프에서는 여러 경로를 비교하고 최적의 경로를 찾을 수 있다.
    • 네트워크 라우팅
      • 트리: 한 노드가 장애가 나면 그 아래 모든 노드가 영향을 받음.
      • 그래프: 여러 경로가 존재하면 장애 발생 시 다른 경로로 우회 가능.
  3. 순환 및 상호 연결이 필요한 시스템을 모델링 가능
    • 트리는 한 번 설정되면 변경하기 어렵지만, 그래프는 동적으로 관계를 추가하거나 변경할 수 있다.
    • 사용자 간의 관계, 커뮤니티 구조 등

그래프의 종류

  • 방향 그래프(Directed Graph, Digraph)
    • 간선에 방향이 있는 그래프.
    • 한쪽 방향으로만 이동할 수 있다.
  • 무방향 그래프(Undirected Graph)
    • 간선에 방향이 없는 그래프.
    • 양쪽 방향으로 이동할 수 있다.
  • 가중치 그래프(Weighted Graph)
    • 간선에 가중치가 부여된 그래프.
    • 거리, 비용, 우선순위 등을 나타내는데 사용한다.
  • 순환 그래프(Cyclic Graph)
    • 모든 정점이 서로 연결된 그래프.
    • 경로를 따라가면 다시 자기 자신으로 돌아온다.
항목 트리(Tree) 그래프(Graph)
구조 계층적 구조 네트워크 형태
방향성 보통 방향성 있음 방향, 무방향 모두 가능
사이클 없음(비순환) 있을 수도 있음
연결성 모든 노드가 연결됨 연결되지 않은 노드 가능
탐색 DFS, BFS DFS, BFS, 다익스트라 등 다양한 탐색

https://yoongrammer.tistory.com/68

https://velog.io/@kwontae1313/트리와-그래프에-대해-알아보자

https://yozm.wishket.com/magazine/detail/2411/