[Python] 자료구조(Data Structure) / 6. 트리 (Tree) / 7. 그래프 (Graph)

비선형구조

---

6. 트리 (Tree)

트리(Tree)는 노드(Node)들로 구성된

계층적(hierarchical) 구조를 가진 자료구조입니다.

---

 

✅ 트리 기본 용어

용어	설명
노드(Node)	트리의 원소 (값을 가짐)
루트(Root)	트리의 최상단 노드 (부모가 없음)
부모(Parent)	다른 노드를 가리키는 노드
자식(Child)	다른 노드에 의해 가리켜지는 노드
리프(Leaf)	자식이 없는 노드 (끝 노드)
서브트리(Subtree)	특정 노드를 루트로 하는 하위 트리
높이(Height)	루트에서 가장 깊은 리프까지의 거리
깊이(Depth)	루트로부터 노드까지의 거리

 

✅ 트리 특징

• 루트는 1개
• 모든 노드는 부모가 1개 (루트 제외)
• 노드 수 = 간선 수 + 1
• 사이클 없는 연결 그래프

사이클(순환)이 있으면 트리가 아니다. (그래서 "트리 = 사이클 없는 연결 그래프"라고도 한다.)

 

✅ 트리 종류

종류	설명
이진 트리(Binary Tree)	노드당 최대 2개의 자식만 가질 수 있는 트리
완전 이진 트리(Complete Binary Tree)	마지막 레벨을 제외하고 꽉 차 있으며, 마지막 레벨은 왼쪽부터 차 있는 트리
포화 이진 트리(Full Binary Tree)	모든 노드가 0개 또는 2개의 자식
균형 이진 트리(Balanced Binary Tree)	왼쪽과 오른쪽 서브트리 높이 차이가 1 이하인 트리
이진 탐색 트리(BST, Binary Search Tree)	왼쪽 < 부모 < 오른쪽 (정렬된 트리) 규칙을 만족하는 이진 트리
힙(Heap)	부모 > 자식 (최대 힙), 부모 < 자식 (최소 힙)

 

✅ 트리 순회

트리 구조를 탐색하는 방법

• 전위 순회 (Preorder): 루트 → 왼쪽 → 오른쪽
• 중위 순회 (Inorder): 왼쪽 → 루트 → 오른쪽
• 후위 순회 (Postorder): 왼쪽 → 오른쪽 → 루트
• 레벨 순회 (Level-order): 층별 탐색 (BFS)

 

✅ 트리가 사용되는 대표적인 예

예시	설명
폴더 구조	폴더 안에 폴더 구조
데이터베이스 인덱스	B-트리, B+트리
이진 탐색 트리 (BST)	빠른 탐색, 삽입, 삭제 (O(log n))
힙 정렬	힙(Heap)을 사용한 정렬
AI 게임 트리	체스, 바둑 등의 수를 탐색하는 트리

 

✅ 트리를 배워야 하는 이유

• 탐색과 정렬의 기본이 된다 (이진 탐색 트리, 힙 등)
• 자료구조의 기초: 힙, 세그먼트 트리, 이진 탐색 트리, 트라이(Trie) 등 트리를 변형한 구조가 많다.
• 계층적 구조를 효과적으로 표현할 수 있다.
• 효율적인 검색, 정렬, 저장에 필수적인 구조이다.
• 알고리즘 문제 풀이(특히 DFS, BFS, DP on tree 문제)에 필수

 

 

---

7. 그래프 (Graph)

그래프(Graph)는 정점(Vertex)과 간선(Edge)으로 구성된 자료구조이다.

현실 세계의 복잡한 관계(네트워크, 경로, 연결 구조)를 표현할 때 사용한다.

---

✅ 그래프 기본 용어

용어	설명
정점(Vertex)	노드 (데이터를 가지는 점)
간선(Edge)	노드와 노드를 연결하는 선
인접(Adjacent)	직접 연결되어 있는 노드
차수(Degree)	연결된 간선의 개수
경로(Path)	두 노드 간 이동 경로
사이클(Cycle)	시작과 끝이 같은 경로

 

✅ 그래프 종류

종류	설명
방향 그래프(Directed)	간선에 방향이 있음
무방향 그래프(Undirected)	간선에 방향이 없음
가중치 그래프(Weighted)	간선에 가중치(비용)가 있음
연결 그래프(Connected)	모든 노드가 연결되어 있음
비연결 그래프(Disconnected)	떨어진 부분이 존재

 

✅ 주요 연산

연산	설명
DFS(깊이 우선 탐색)	깊게 파고듦
BFS(너비 우선 탐색)	가까운 곳부터 탐색
최단 경로 알고리즘	다익스트라, 벨만포드, 플로이드
최소 신장 트리(MST)	크루스칼, 프림 알고리즘

 

✅ 그래프 사용 예시

예시	설명
소셜 네트워크	친구 관계, 팔로우 관계
지하철 노선도	역 간 연결
지도 탐색	최단 거리 경로 찾기
인터넷 네트워크	서버와 클라이언트 연결
전자회로 설계	회로 내 연결

 

✅ 그래프를 배워야 하는 이유

• 복잡한 현실 문제를 추상화해서 해결할 수 있다.
• BFS, DFS, 다익스트라, 크루스칼 같은 기본 알고리즘이 모두 그래프 기반이다.

 

 

---

✅ 트리(Tree) / 그래프(Graph) 정리

구분	트리(Tree)	그래프(Graph)
구조	계층적 구조	네트워크 구조
순환	없음 (사이클X)	있음 가능 (사이클O)
관계	부모-자식	일반적인 연결
사용 예	폴더 구조, 이진 탐색 트리	소셜 네트워크, 지도 탐색
탐색	DFS, BFS	DFS, BFS

 

 

 

 

---

📌 아직 배우는 중이라 부족한 부분이 있을 수 있습니다.
혹시 잘못된 내용이나 더 나은 방법이 있다면 알려주세요 🙏
감사합니다! 😄