024 | Data Structure - Tree, Graph

💙 Tree

🤍 개념

• 계층적 자료구조
• 대상 정보의 각 항목들을 계층적으로 연관되도록 구조화시키고자 할 때 사용하는 비선형 자료구조
• 단방향 그래프

깊이 (depth)

• 루트로부터 하위 계층의 특정 노드까지의 깊이(depth)를 표현

레벨(Level)

• 같은 깊이를 가지고 있는 노드의 묶음
• 형제 노드(Sibling Node): 같은 레벨에 나란히 있는 노드

높이(Height)

• 리프 노드를 기준으로 루트까지의 높이(height)를 표현
• 리프 노드와 직간접적으로 연결된 노드의 높이를 표현
  부모 노드는 자식 노드의 가장 높은 height 값에 +1한 값을 높이로 가짐
• 트리 구조의 높이를 표현할 때에는 각 리프 노드의 높이를 0으로 놓음

서브 트리(Sub tree)

• 트리 구조의 root에서 뻗어 나오는 큰 트리의 내부에, 트리 구조를 갖춘 작은 트리

🤍 자료구조의 용어

• 노드(Node): 트리 구조를 이루는 모든 개별 데이터
• 루트(Root): 트리 구조의 시작점이 되는 노드
• 부모 노드(Parent node): 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드
• 자식 노드(Child node): 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드
• 리프(Leaf): 트리 구조의 끝 지점, 자식 노드가 없는 노드

🤍 Tree 사용 예제

• 컴퓨터 디렉토리
• 모든 폴더는 하나의 폴더(루트 폴더, /)에서 시작되어, 가지를 뻗어나감
• 월드컵 토너먼트 대진표
• 가계도(족보)

💙 Graph

🤍 개념

• 한 쌍의 노드를 연결하는 노드의 유한 집합과 엣지 집합으로 구성된 비선형 데이터구조
• 연결되어있는 객체 간 관계를 표현할 수 있는 자료구조
• 직접적인 관계: 두 점 사이를 이어주는 선
• 간접적인 관계: 몇 개의 점과 선에 걸쳐 이어짐

🤍 그래프 관련 용어

• 정점(vertex)(= 노드(node)): 데이터가 저장되는 그래프의 기본 원소
• 간선(edge): 정점 간의 관계. 정점(= 노드) 연결 선
• 인접 정점(adjacent vertex): 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점
  • 인접(adjacency): 두 정점 간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 것
• 가중치 그래프(weighted Graph): 연결의 강도(추가적인 정보)가 얼마나 되는지 적혀져 있는 그래프
• 비가중치 그래프(unweighted Graph): 연결의 강도가 적혀져 있지 않는 그래프
• 무(방)향 그래프(undirected graph): 두 지점이 일방통행 도로로 이어져 있다면 단방향인 간선으로 표현
• 진입 차수(in-degree): 방향 그래프에서 외부에서 오는 간선의 수 (= 내차수)
• 진출 차수(out-degree): 방향 그래프에서 외부로 향하는 간선의 수 (= 외차수) 방향 그래프에 있는 정점의 진입 차수 또는 진출 차수의 합 = 방향 그래프의 간선의 수(내차수 + 외차수)
• 경로 길이(path length): 경로 구성에 사용된 간선의 수
• 단순 경로(simple path): 경로 중 반복되는 정점이 없는 경우
• 자기 루프(self loop): 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다 라고 표현함. 다른 정점을 거치지 않는다는 것이 특징
• 사이클(cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있는 것

🤍 Graph 표현방식

인접행렬(Adjacency Matrix)

• 두 정점을 바로 이어주는 간선
• 서로 다른 정점들이 인접한 상태인지를 표시한 행렬로, 2차원 배열의 형태로 나타냄
• 사용할 때
  • 두 정점 사이에 관계가 있는지, 없는지 확인
  • 가장 빠른 경로를 찾고자 할 때

인접리스트(Adjacency List)

• 각 정점이 어떤 정점과 인접하는지를 리스트의 형태로 표현
• 각 정점마다 하나의 리스트를 갖고 있으며, 이 리스트는 자신과 인접한 다른 정점을 담음
• 순서는 중요하지 않음
• 사용할 때
  • 메모리를 효율적으로 사용하고 싶을 때

인접행렬 / 인접리스트 선택 방법

• 인접 행렬: 그래프에 간선이 많은 밀집 그래프(Dense Graph)일 때
• 인접 리스트: 그래프 내 간선이 적은 숫자만을 가지는 희소 그래프(Sparse Graph)일 때

🤍 Tree vs Graph

✅ Ref.

[자료구조] 그래프(Graph)란 - Heee's Development Blog

💙 더 공부해볼 것

• 여러가지 트리구조