[ 자료 구조 ] Tree / Graph

Tree 알아보기

• 그래프의 여러 구조 중 단방향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮았다고 해서 트리 구조라고 부른다.
• 트리는 계층적 자료구조 / 비선형 구조이다.
• 트리는 사이클(cycle)이 없는 하나의 연결 그래프 (Connected Graph)라고 한다.
  • 사이클이란 시작 노드에서 출발해 다른 노드를 거쳐 시작 노드로 돌아올 수 있다면 사이클이 존재한다고 표현한다.

Tree의 구조와 특징

• 트리 구조는 루트(Root)라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선(edge)으로 연결한다.
• 각 데이터는 노드(Node)라고 한다.
  • 두개의 노드가 상하계층으로 연결되면 부모 / 자식 관계를 맺는다.
  • 자식이 없는 노드는 리프 노드(Leaf Node)라고 부른다.
• Tree는 깊이와 높이, 레벨 등을 측정할 수 있음

트리 구조의 레벨과 서브 트리

용어 정리

• 노드(Node) : 트리 구조를 이루는 모든 개별 데이터
• 루트(Root) : 트리 구조의 시작점이 되는 노드
• 부모 노드(Parent node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드
• 자식 노드(Child node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드
• 리프(Leaf) : 트리 구조의 끝 지점이고, 자식 노드가 없는 노드
• 깊이 (depth) : 루트로부터 하위 계층의 특정 노드까지의 깊이를 표현
• 레벨(Level) : 같은 깊이를 가지고 있는 노드를 묶어서 레벨로 표현
  • 같은 레벨에 나란히 있는 노드를 형제 노드(Sibling Node)라고 함
• 높이(Height) : 리프 노드를 기준으로 루트까지의 높이(height)를 표현
• 서브 트리(Sub tree) : 트리 구조를 갖춘 작은 트리를 서브 트리라고 부름

 

Tree 사용 예제

• 컴퓨터의 디렉토리 구조
• 월드컵 토너먼트 대진표
• 가계도(족보)
• 조직도

---

Graph 알아보기

• 그래프는 여러 개의 점이 서로 복잡하게 연결된 관계를 표현한 자료구조이다.
• 자료구조의 그래프는 마치 거미줄처럼 여러 개의 점이 선으로 이어져 있는 복잡한 네트워크망과 같은 모습이다.

컴퓨터 공학 그래프

Graph의 구조

• 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있다.
• 간접적인 관계라면 몇 개의 점과 선에 걸쳐 이어짐
• 하나의 점 : 정점(vertex) / 하나의 선 : 간선(edge)이라고 함

정점과 간선이 뭔지 알아보자.

예시)

서울에 사는 A는 부산에 사는 B와 오랜 친구 사이입니다.
이번 주말에 부산에서 열리는 B의 결혼식에 참석하기 위해 A는 차를 몰고 부산으로 가려고 합니다.
대전에 살고 있는 친구 C도 B의 결혼식에 참석한다고 하여,
A는 서울에서 출발하여 대전에서 C를 태워 부산으로 이동하려고 합니다.

• 정점 :  3개 각각의 도시(서울,부산,대전)
  • 정점은 서로 이어지는 간선을 가지고 있고 서로  이어지는 간선은 관계가 있다고 표현한다.
  • 만약 제주도라는 도시가 새로운 정점으로 추가된다고 하더라도 위 예시에 맞는 이어지는 간선이 아니기 때문에 관계가 없는 비연결 그래프라고 한다.

• 간선 : 서울—대전, 대전—부산, 부산—서울
  • 간선은 특정 도시가 이어져 있다는 사실만 알려줄 뿐, 추가적인 정보,가중치가 없는 그래프를 비 가중치 그래프라고 한다.
  • 가중치 그래프의 경우 : 
    • 정점: 서울, 대전, 부산
    • 간선: 서울—140km—대전, 대전—200km—부산, 부산—325km—서울

 

Graph의 표현 방식

1. 인접 행렬
   • 서로 다른 정점들이 인접한 상태인지를 표시한 행렬로 2차원 배열의 형태로 나타냄
   • 연결 가능한 모든 경우의 수를 저장하기 때문에 메모리를 많이 차지함
2. 인접 리스트
   • 각 정점이 어떤 정점과 인접하는지를 리스트의 형태로 표현함
   • 인접 리스트로 구현할 때, 정점별로 살펴봐야 할 우선순위를 고려해 구현할 수 있다.
     • 리스트에 담긴 정점들을 우선 순위별로 정렬 
       • 우선순위를 다뤄야 한다면 더 적합한 자료구조(ex. queue, heap)를 사용하는 것이 합리적이긴 하다.
     • 우선순위가 없다면, 연결된 정점들을 단순하게 나열한 리스트가 된다.
3. 인접 행렬 & 인접 리스트 사용 예시
   1. 인접 행렬
      • 두 정점 사이에 관계 있는지 없는지 확인시
      • 가장 빠른 경로 찾을 때
   2. 인접 리스트
      • 메모리를 효율적으로 사용할 때

 

Graph 사용 예제

• 포털 사이트의 검색 엔진, SNS에서 사람들과의 관계, 내비게이션 (길 찾기)등