[3주차] 비선형 자료구조

※ 이전에 선형 자료구조는 해당 링크

https://ysh0129.tistory.com/104

[1주차] 자료구조

 

비선형 자료구조?

▶ 한 줄로 선으로 이루어지지 않고, 데이터가 계층적/네트워크적, 여러 갈래로 복잡하게 연결된 구조 

 

1. 트리

    1-(1) 트리의 종류
    1-(2) 이진 트리 순회

• 전위 순회
• 중위 순회
• 후위 순회

2. 그래프

    2-(1) 그래프의 개념과 표현 방식
    2-(2) 그래프 탐색 

• 깊이 우선 탐색 (DFS)
• 너비 우선 탐색 (BFS)
• BFS 최단 거리

3. 트리와 그래프의 관계

 

 

 

---

 

1. 트리

 

▶ 노드들이 나무 가지처럼 연결된 계층적 자료구조

 

• 노드(Node) : 자료 항목을 가지고 있는 트리를 구성하는 기본 요소(이미지에서 A~J를 의미)
• 근 노드(Root node) : 트리에서 가장 맨 위에 위치하는 노드 (A에 해당)
• 차수(Degree) : 트리에서 각 뻗어진 가지 수(A=2, F=1)
• 잎사귀 노드(Leaf node) : 차수가 없는 노드 (E,G,H,I,J가 해당)
• 트리의 깊이(Depth / Level) : 트리에서의 최대 깊이(H 노드는 3레벨, 루트인 A 노드는 0레벨)
• 트리의 차수 : 전체의 트리에서 가장 많은 차수, 전체가 아닌 가장 가지수가 많은 부분(=2)
• 자식 노드 : 노드에 연결된 서브트리의 루트노드들(D)
• 부모 노드 : 노드에 연결된 한단계 상위 레벨 노드(D 기준으로 B)
• 형제 노드(Sibling node) : 부모가 같은 노드(D,E 와 F,G)

 

1-(1) 트리의 종류

• 정 이진트리(Full binary tree)
  각 내부 노드가 두 개의 자식 노드를 갖는 순서화된 트리
  ( 홀수 개의 자식 노드를 가질 수 없다. 2¹, 2², 2³, ... ,2ⁿ 구조 )
• 완전 이진 트리(Complete binary tree)
  부모, 왼쪽 자식, 오른쪽 자식 순으로 채워지는 트리를 말한다.
  (마지막 레벨을 제외하고 모든 노드가 가득 차 있는트리 단, 마지막 레벨은 왼쪽부터 채워져야 한다.)
• 포화 이진 트리(Perfect binary tree)
  정 이진 트리이면서 완전 이진 트리인 경우를 말한다.
  (마지막 레벨을 제외하고 Leaf node가 없다.)
• 균형 이진 트리 (Balanced binary tree)
  모든 노드의 좌우 서브 트리 Level이 1이상 차이나지 않는 트리
  (예로 좌는 Level 1, 우는 Level 3인 경우 균형 이진 트리에 해당하지 않는다.)
• 변질 이진 트리(Degenerate binary tree)
  각 부모 노드가 오직 한 개의 연관 자식 노드를 갖는 트리
  (성능 면에서 트리가 연결 리스트 데이터 구조처럼 동작)

 

1-(2) 이진 트리 순회

• 전위 순회
   [루트 - 왼쪽 자식 - 오른쪽 자식] 순으로 순회 (루트 노드부터 시작 자식 왼쪽 노트로)
• 중위 순회
  [왼쪽 자식 - 루트 - 오른쪽 자식] 순으로 순회 (최고 레벨 왼쪽 노드에서 시작 후 부모 노드로)
  
• 후위 순회
  [왼쪽 자식 - 오른쪽 자식 - 루트] 순으로 순회 (최고 레벨 왼쪽 노드에서 시작 후 형제 노드로)
  

---

 

2. 그래프

 

2-(1) 그래프의 개념과 표현 방식

 

그래프?

▶ 정점(vertex = node) 와 연결하는 간선(edge)의 집합으로 이루어진 자료구조

 

그래프의 종류

 

 

그래프의 구현 방법

	인접 행렬 (Adjacency Matrix)	인접 리스트 (Adjacency List)
정의	정점(노드)의 개수가 V개인 그래프를 V×V 크기의 2차원 배열로 나타내는 방법	정점 i에 대해 배열의 i번째 요소에 i와 연결된 모든 정점들의 리스트를 저장합니다. (예: list[i] = {j, k, ...})
장점	간선 존재 여부확인이 빠름 구현이 단순함	메모리 효율성 좋음 인접 정점 탐색 속도 빠름
단점	메모리 낭비 인접 정점 탐색 속도 느림	간선 존재 여부 확인 속도가 느림 구현이 복잡함

 

정점(vertax)에 따라서 수가 적으면 인접행렬을 사용하고 대부분 인접리스트 사용

 

2-(2) 그래프의 탐색

DFS / BFS / BFS 최단거리

 

	깊이 우선 탐색 (DFS)	너비 우선 탐색 (BFS)	BFS 최단 거리
방식	가능한 한 깊이(Depth) 내려간 후, 더 이상 갈 곳이 없으면 백트래킹 후 다른 경로를 탐색하는 방식	시작 노드에서 가까운 노드들을 먼저 탐색하고, 그다음으로 가까운 노드들을 탐색하는 방식,  수평적으로 탐색	가중치 없는 그래프에서 시작 노드로부터의 최단 경로를 찾는 데 가장 효율적이고 정확한 알고리즘
자료구조	탐색할 노드를 저장하는 데 스택 또는 재귀 함수를 사용	탐색할 노드를 저장하는데 큐를 사용
주요 분야	경로 찾기, 사이클 감지, 위상 정렬	미로 찾기, 네트워크 탐색

 

 

---

 

3. 트리와 그래프의 관계

트리는 그래프의 한종류이다. ( 트리⊆그래프 )

 

구분	그래프	트리
정의	정점과 간선의 집합	사이클이 없는 연결 그래프
사이클	있을 수도 있음	없음
연결성	연결/비연결 가능	항상 연결됨
간선 수	제한 없음	정점 수 - 1
방향성	방향/무방향 모두 가능	주로 방향 있음 (루트→자식)
예시	도로망, SNS 친구 관계	조직도, 폴더 구조, DOM 구조

 

 

마치며

개념 정리를 하면서 어떤 구조인지는 이해가 가지만

코테로 어떻게 적용하고 접근할지가 관건이다.