[자료구조] 비선형 자료 구조

비선형 자료구조란?

비선형 자료구조는 데이터가 순차적으로 나열되지 않고, 요소 간의 관계가 복잡하고 계층적인 구조를 이루는 자료구조입니다. 대표적으로 트리(Tree)와 그래프(Graph)가 있습니다.

---

1. 그래프 (Graph)

• 정점(Vertex): 하나의 지점을 의미 (ex. 도시, 사람)
• 간선(Edge): 정점 간의 연결 (ex. 도로, 친구 관계)
• 방향성: 단방향 그래프, 양방향 그래프로 나뉨
• 가중치(Weight): 간선에 부여된 비용 또는 거리

---

2. 트리 (Tree)

트리는 그래프의 일종으로, 계층적 구조를 가진 비선형 자료구조입니다.

• 루트 노드: 최상위 노드
• 리프 노드: 자식이 없는 노드
• 내부 노드: 자식이 있는 노드
• 서브트리: 어떤 노드를 루트로 하는 부분 트리

주요 개념

• V(노드 수) - 1 = E(간선 수)
• 깊이(Depth): 루트에서 특정 노드까지의 거리
• 높이(Height): 루트에서 리프 노드까지의 최대 거리
• 레벨(Level): 노드의 깊이와 같음

 

2-1. 이진 트리 (Binary Tree)

모든 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리

• 정이진 트리: 자식 노드가 0개 또는 2개
• 완전 이진 트리: 마지막 레벨을 제외하고 왼쪽부터 채워짐
• 포화 이진 트리: 모든 레벨이 완전히 채워짐
• 변질 이진 트리: 자식이 하나뿐인 노드가 존재
• 균형 이진 트리: 좌우 서브트리의 높이 차이가 1 이하

 

2-2. 이진 탐색 트리 (BST)

왼쪽 하위 트리는 현재 노드보다 작은 값, 오른쪽 하위 트리는 큰 값 저장

• 탐색, 삽입, 삭제 평균 시간복잡도: O(log n)
• 최악의 경우(편향된 트리): O(n)

 

2-3. AVL 트리

• BST의 변형으로, 자동으로 균형을 유지하는 트리
• 좌우 서브트리의 높이 차이가 항상 1 이하
• 삽입/삭제 시 불균형 발생 시 회전(Rotation)을 통해 균형 복원

 

2-4. 레드 블랙 트리

• 균형 이진 탐색 트리의 대표적인 구현
• 노드는 빨간색 또는 검은색 중 하나의 색을 가짐
• 삽입/삭제 후에도 O(log n) 보장
• C++ STL의 map, set 내부 구현에 사용

 

---

3. 힙 (Heap)

• 완전 이진 트리 기반의 자료구조

종류

• 최대 힙(Max Heap): 부모 노드가 자식 노드보다 항상 큼
• 최소 힙(Min Heap): 부모 노드가 자식 노드보다 항상 작음

최대 힙 연산

• 삽입: 마지막에 삽입 후, 부모 노드와 비교하며 위로 올라감
• 삭제: 루트(최댓값)를 삭제 → 마지막 노드와 교체 후, 아래로 내려가며 정렬

---

4. 우선순위 큐 (Priority Queue)

• 우선순위가 높은 요소가 먼저 나가는 큐
• 보통 힙 자료구조로 구현됨
• 오름차순/내림차순 정렬에 사용

---

5. 맵 (Map)

• 키-값 쌍으로 데이터를 저장
• 중복 키는 허용하지 않음
• 내부적으로 레드 블랙 트리 기반으로 정렬됨

for (auto it = myMap.begin(); it != myMap.end(); ++it) {
    cout << it->first << ": " << it->second;
}

---

6. 셋 (Set)

• 중복을 허용하지 않는 유일한 값들의 집합
• 정렬된 상태로 유지 (레드 블랙 트리 기반)

---

7. 해시 테이블 (Hash Table)

• 키를 해시 함수로 변환하여 고정 크기의 배열에 저장
• 탐색, 삽입, 삭제 모두 평균적으로 O(1)
• 해시 충돌을 해결하기 위한 체이닝(Linked List) 또는 오픈 어드레싱 사용

---

마무리

비선형 자료구조는 데이터 간 관계 표현, 탐색 성능 최적화, 계층 구조 표현 등에 강력한 도구로 사용됩니다. 문제 유형에 따라 적절한 자료구조를 선택하는 것이 핵심입니다.