SECTION 5.3 비선형 자료 구조

비선형 자료 구조

비선형 자료 구조란 일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조를 말합니다.
일반적으로 트리나 그래프를 말합니다.

---

5.3.1 그래프

그래프는 정점(vertex) 과 간선(edge) 으로 이루어진 자료 구조입니다.

정점과 간선

"어떠한 곳에서 어떠한 곳으로 무언가를 통해 간다"

• 어떠한 곳 → 정점(vertex)
• 무언가(길) → 간선(edge)

개념	설명
단방향 간선	한쪽 방향으로만 갈 수 있음 (예: 짝사랑)
양방향 간선	양쪽 방향 모두 갈 수 있음 (예: 서로 좋아함)
outdegree	해당 정점에서 나가는 간선의 수
indegree	해당 정점으로 들어오는 간선의 수

보통 "U에서부터 V로 간다."라고 표현합니다.

가중치

간선과 정점 사이에 드는 비용을 뜻합니다.
예) 성남 → 네이버까지 택시비가 13,000원이라면, 해당 간선의 가중치는 13,000원

---

5.3.2 트리

트리는 그래프의 일종으로, 정점과 간선으로 이루어진 계층적 데이터의 집합입니다.
루트 노드, 내부 노드, 리프 노드 등으로 구성됩니다.

💡 트리로 이루어진 집합을 숲(forest) 이라고 합니다.

트리의 특징

1. 부모-자식 계층 구조를 가집니다.
   같은 경로상에서 위에 있으면 부모, 아래에 있으면 자식 노드
2. V - 1 = E : 간선 수 = 노드 수 - 1
3. 임의의 두 노드 사이의 경로는 유일하게 존재합니다.

트리의 구성

노드 종류	설명
루트 노드	가장 위에 있는 노드. 트리 탐색의 시작점
내부 노드	루트 노드와 리프 노드 사이에 있는 노드
리프 노드	자식 노드가 없는 노드 (끝 노드)

트리의 높이와 레벨

용어	설명
깊이	루트 노드부터 특정 노드까지의 최단 거리
높이	루트 노드부터 리프 노드까지 거리 중 가장 긴 거리
레벨	보통 깊이와 같은 의미 (문제마다 기준이 다를 수 있음)
서브트리	트리 내의 하위 집합 (부분집합)

---

이진 트리

자식 노드 수가 두 개 이하인 트리

종류	설명
정이진 트리 (full binary tree)	자식 노드가 0개 또는 2개
완전 이진 트리 (complete binary tree)	왼쪽부터 채워져 있으며, 마지막 레벨만 비어있을 수 있음
변질 이진 트리 (degenerate binary tree)	자식 노드가 하나밖에 없음
포화 이진 트리 (perfect binary tree)	모든 노드가 꽉 차 있음
균형 이진 트리 (balanced binary tree)	왼쪽/오른쪽 높이 차이가 최대 1 (예: 레드 블랙 트리)

---

이진 탐색 트리 (BST)

• 오른쪽 하위 트리: 노드 값보다 큰 값
• 왼쪽 하위 트리: 노드 값보다 작은 값

연산	평균	최악
탐색 / 삽입 / 삭제	O(log n)	O(n)

⚠️ 삽입 순서에 따라 선형(편향) 트리가 될 수 있어 최악 O(n)이 발생할 수 있습니다.

---

AVL 트리

AVL 트리(Adelson-Velsky and Landis tree)는 BST의 최악 케이스를 방지하기 위해 스스로 균형을 잡는 이진 탐색 트리입니다.

• 두 자식 서브트리의 높이 차이는 항상 최대 1
• 삽입/삭제 시 균형이 깨지면 트리를 회전시켜 균형을 복원

연산	시간 복잡도
탐색 / 삽입 / 삭제	O(log n)

---

레드 블랙 트리

균형 이진 탐색 트리로, C++ STL의 set, multiset, map, multimap이 이 구조로 구현되어 있습니다.

• 각 노드는 빨간색 또는 검은색 비트를 추가로 저장
• "모든 리프 노드와 루트 노드는 블랙, 레드 노드의 자식은 반드시 블랙" 등의 규칙으로 균형 유지

연산	시간 복잡도
탐색 / 삽입 / 삭제	O(log n)

---

5.3.3 힙

힙은 완전 이진 트리 기반의 자료 구조입니다.

종류	설명
최대힙	루트 노드가 항상 최댓값 (부모 ≥ 자식, 재귀적으로 적용)
최소힙	루트 노드가 항상 최솟값 (부모 ≤ 자식, 재귀적으로 적용)

최대힙의 삽입

1. 새 노드를 마지막 노드에 삽입
2. 부모 노드와 비교하며 위로 올라가며 스왑 → 힙 조건 만족

최대힙의 삭제

1. 루트 노드(최댓값) 삭제
2. 마지막 노드를 루트로 올린 후 아래로 내려가며 스왑 → 재구성

---

5.3.4 우선순위 큐

우선순위 큐는 우선순위가 높은 요소가 먼저 나오는 자료 구조입니다.
힙을 기반으로 구현됩니다.

#include <bits/stdc++.h>
using namespace std;

priority_queue<int, vector<int>, greater<int>> pq; // 오름차순 (최소힙)
// priority_queue<int, vector<int>, less<int>> pq; // 내림차순 (최대힙)

int main() {
    pq.push(5);
    pq.push(4);
    pq.push(3);
    pq.push(2);
    pq.push(1);
    cout << pq.top() << "\n";
    return 0;
}
/*
1
*/

greater → 오름차순(최소 우선), less → 내림차순(최대 우선)

---

5.3.5 맵

맵(map)은 키(key)와 값(value)의 쌍으로 이루어진 자료 구조입니다.
레드 블랙 트리 기반으로 구현되며, 삽입 시 자동 정렬됩니다.

종류	정렬 보장
map	✅ 정렬 보장
unordered_map	❌ 정렬 없음 (해시 기반, 더 빠름)

주요 함수: insert(), emplace(), [], find(), erase(), size(), clear()

#include <bits/stdc++.h>
using namespace std;

int main() {
    unordered_map<string, int> umap;

    umap.insert({"test1", 1});   // insert로 추가
    umap.emplace("test5", 5);    // emplace로 추가
    umap["test1"] = 4;           // 값 변경 (권장 방식)

    for (auto element : umap) {
        cout << element.first << " :: " << element.second << '\n';
    }

    auto search = umap.find("test4");
    if (search != umap.end()) {
        cout << "found: " << search->first << " " << (*search).second << '\n';
    } else {
        cout << "not found.." << '\n';
    }

    umap["test1"]++;
    cout << umap["test1"] << "\n";
    cout << umap.size() << "\n";

    umap.erase("test1");
    cout << umap.size() << "\n";
    return 0;
}
/*
test5 :: 5
test1 :: 4
not found..
5
2
1
*/

순회 시 element.first → 키, element.second → 값

---

5.3.6 셋

셋(set)은 고유한(unique) 값만 저장하는 컨테이너입니다.
중복 요소가 없으며, 특정 순서에 따라 요소를 저장합니다.

pair는 두 가지 형을 담을 수 있는 구조이며 first, second로 접근합니다.
나머지 사용법은 map과 유사합니다.

---

5.3.7 해시 테이블

해시 테이블은 무한에 가까운 데이터를 유한한 해시 값으로 매핑한 테이블입니다.
C++에서는 unordered_map으로 구현합니다.

연산	평균 시간 복잡도	최악 시간 복잡도
삽입 / 삭제 / 탐색	O(1)	O(n)

⚠️ 해시 충돌이 많이 발생하면 최악 O(n)까지 떨어질 수 있습니다.