[자료구조] 비선형 자료 구조 개념 정리 | 그래프, 트리, 힙, 우선순위 큐, 셋, 맵, 해시 테이블

이 포스팅은 주홍철 저 '면접을 위한 CS 전공지식 노트' 5.3장을 토대로 작성되었습니다.

 

 

비선형 자료 구조란,

일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조를 말합니다.

---

📌 그래프(Graph)

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

• 정점(vertex/node)
  • 항목 자체를 나타내며, 데이터를 담고 있는 원소
• 간선(edge)
  • 정점들을 연결하는 선으로, 정점 간의 관계를 표현
  • 단방향일 수도, 양방향일 수도 있음

 

 

• 차수(degree): 정점에 연결된 간선의 개수
• 경로(path): 한 정점에서 다른 정점으로 이동할 수 있는 간선들의 순서
• 사이클(cycle): 시작 정점과 끝 정점이 동일한 경로
• 무방향 그래프(Undirected Graph): 간선이 양방향으로 이동 가능한 그래프
• 방향 그래프(Directed Graph/Digraph): 간선에 방향이 있어 한쪽으로만 이동 가능한 그래프
• 가중치 그래프(Weighted Graph): 간선에 비용이나 거리 등의 가중치가 할당된 그래프, 최단 경로 문제 등에서 활용

---

📌 트리(Tree)

트리는 그래프처럼 정점과 간선으로 구성된 구조로,

정점들이 나뭇가지처럼 연결된 계층적 데이터의 집합입니다.

 

트리에서는 각 정점을 보통 노드라고 부릅니다.

• 루트 노드: 트리의 최상위 노드로, 부모가 없는 유일한 노드
• 리프 노드: 자식이 없는 노드
• 내부 노드: 루트 노드도, 리프 노드도 아닌 자식이 있는 노드
• 차수(degree): 어떤 노드가 가진 자식의 개수
• 높이(height): 특정 노드에서부터 리프 노드까지의 가장 긴 경로의 간선 수
  • 트리의 높이 = 루트 노드의 높이
• 깊이(depth): 루트 노드로부터 특정 노드까지 간선 수
  • 루트 노드의 깊이는 0
• 레벨(level): 보통 깊이와 같은 의미, 루트는 레벨 1부터 시작
  • 깊이 0 = 레벨 1
• 서브 트리: 트리 내의 하위 집합(부분 집합)

 

📌 이진 트리(Binary Tree)

트리 중에서 각 노드의 차수(자식의 수)가 최대 2개인 트리를 이진 트리라고 합니다.

• 정이진 트리(Full Binary Tree)
  • 각 내부 노드가 두 개의 자식 노드를 가지는 트리
  • 홀수 개의 자식 노드를 가질 수 없음(자식이 0개 또는 2개)
• 완전 이진 트리(Complete Binary Tree)
  
  • 부모, 왼쪽 자식, 오른쪽 자식 순으로 채워지는 트리
  • 마지막 레벨을 제외하고 모든 노드가 가득 차있어야 하며, 마지막 레벨의 노드는 전부 차있지 않아도 되지만 왼쪽부터 채워져 있어야 함
• 변질 이진 트리(Degenerate Binary Tree)
  
  • 각 부모 노드가 오직 1개의 자식 노드만 가지는 트리
  • 실질적으로 리스트(List) 구조처럼 동작함
• 포화 이진 트리(Perfect Binary Tree)
  • 정이진 트리이면서 완전 이진 트리인 모든 노드가 꽉 차 있는 이진 트리
• 균형 이진 트리(Balanced Binary Tree)
  
  • 왼쪽 노드와 오른쪽 노드의 높이 차이가 1 이하인, 한쪽으로 지나치게 치우치지 않고 균형을 이루고 있는 트리
  • 트리가 한 쪽으로 치우친 경우, 시간 복잡도가 악화되므로 고안된 구조

📌 이진 트리의 순회

• 전위 순회(Preorder Traversal)
  • 자신 → 왼쪽 자식 → 오른쪽 자식 순서로 순회
  • 0 → 1 → 3 → 7 → 8 → 4 → 9 → 10 → 2 → 5 → 11 → 5 → 6
• 중위 순회(Inorder Traversal)
  • 왼쪽 자식 → 자신 → 오른쪽 자식 순서로 순회
  • 7 → 3 → 8 → 1 → 4 → 9 → 10 → 0 → 11 →  5 →  2→ 6
• 후위 순회(Postorder Traversal)
  • 왼쪽 자식 → 오른쪽 자식 → 자신 순서로 순회
  • 7 → 8 → 3 → 9 → 10 → 4 → 1 → 11 → 5  → 6 → 2 → 0 

📌 이진 탐색 트리(Binary Search Tree, BST)

이진 탐색 트리는 특정 규칙에 따라 데이터를 저장하여

데이터의 검색 성능을 높인 이진 트리입니다.

• 노드의 왼쪽 서브 트리에는 노드의 값보다 작은 값만 저장
• 노드의 오른쪽 서브 트리에는 노드의 값보다 큰 값만 저장
• 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리

이 구조에서 10을 찾으려고 한다면, 루트 노드인 25보다 작으므로 왼쪽 노드들만 확인하면 된다는 걸 알 수 있습니다.

이처럼 평균적으로 O(logN)의 시간 복잡도로 탐색, 삽입, 삭제가 가능합니다.

 

단 트리가 한쪽으로 지나치게 치우치는 편향 트리가 되면 최악의 경우 O(N)의 시간이 필요할 수도 있습니다.

그래서 이진 탐색 트리의 균형을 유지하여 최악의 성능을 방지하는 자료 구조로

AVL 트리나 레드-블랙 트리(Red-Black 트리)가 있습니다.

 

📌 AVL 트리(Adelson-Velsky and Landis Tree)

최강의 경우 선형적인 트리가 되는 것을 방지하기 위해 스스로 균형을 잡는, 

균형 잡힌 이진 탐색 트리입니다.

 

• 항상 모든 노드에서 왼쪽 서브 트리의 높이와 오른쪽 서브 트리의 높이 차이가 최대 1을 넘지 않도록 균형을 조절
• 데이터를 삽입/삭제할 때마다 균형이 깨지 회전(Rotation) 연산을 통해 트리를 재구성
• 회전 연산에 대한 자세한 설명이 필요하다면 이 블로그를 추천합니다: https://lifeandit.tistory.com/101
• 탐색, 삽입, 삭제 모두 시간 복잡도가 O(lonN) 소요

 

📌 레드-블랙 트리(Red-Black Tree) 

각 노드를 빨간색 또는 검은색으로 색칠하여 삽입 및 삭제 중에 트리가 균형을 유지하도록 하는

또다른 균형 이진 탐색 트리입니다.

레드-블랙 트리에서도 노드 탐색, 삽입, 삭제의 시간 복잡도는 O(logN)입니다.

• 모든 노드는 Red 또는 Black으로 색칠
• 루트 노드는 Black으로 색칠
• 모든 리프 노드(NIL)는 Black으로 색칠
• Red의 노드의 자식은 항상 Black으로 색칠 (Red 노드가 연속될 수 없음)
• 어떤 노드에서부터 리프 노드에 이르는 모든 경로에서 Black 노드의 수(Black height)는 같음

 

AVL 트리는 모든 노드가 왼쪽 서브 트리와 오른쪽 서브 트리의 높이 차이가 최대 1이 되어야 한다는 엄격한 규칙이었지만,

레드-블랙 트리에서는 높이 차이를 직접적으로 제한하는 대신, Black Height라는 개념을 추가하여 한쪽 서브 트리가 다른 쪽 서브 트리보다 최대 2배까지 길어지는 것을 허용합니다.

이처럼 완벽한 균형보다는 합리적인 균형을 추구하는 레드-블랙 트리가 AVL 트리에 비해 덜 엄격하고 유연하여

삽입과 삭제가 조금 더 빠르고 탐색은 조금 느립니다. 같은 O(logN)이어도 상수 계수의 크기가 차이나는 겁니다.

 

레드-블랙 트리 삽입/삭제 과정이 궁금하다면 다음 블로그를 추천합니다: https://code-lab1.tistory.com/62

---

📌 힙(Heap)

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

항상 최대값 또는 최소값을 빠르게 찾아내기 위해 설계된 구조입니다.

 

힙은 루트 노드에 항상 극단적인 값(최대값 또는 최소값)을 저장합니다.

• 최대 힙(Max Heap)
  • 부모 노드의 값이 자식 노드의 값보다 항상 크거나 같음
  • 루트 노드에는 가장 큰 값이 저장됨
• 최소 힙(Min Heap)
  • 부모 노드의 값이 자식 노드의 값보다 항상 작거나 같음
  • 루트 노드에는 가장 작은 값이 저장됨

힙 구조에서는 데이터를 삽입할 때 맨 끝에 새로운 노드를 추가한 후, 

규칙을 만족하도록 새로운 노드를 부모 노드들과 비교하며 적절한 위치로 옮깁니다.

 

이처럼 트리가 완전 이진 트리 형태로 유지되기 위해

삽입, 삭제에서는 O(logN)의 시간이 필요합니다.

 

힙은 최대값, 최소값을 빠르게 확인하기 위한 구조로 루트 노드만 확인하므로 최대/최소값 검색 시간은 O(1)입니다.

 

---

📌 우선순위 큐(Priority Queue)

데이터가 들어온 순서대로 처리되는 일반적인 큐와 달리,

우선순위가 높은 요소가 먼저 추출(대기열에서 꺼내짐/삭제)됩니다.

 

가장 우선순위가 높은 요소를 O(1)에 확인하고,

삽입 및 추출을 O(logN)에 수행하기 위해 고안된 구조입니다.

 

우선순위 큐는 일반적으로 힙을 기반으로 구현됩니다.

힙 속성에 따라 루트 노드가 항상 최우선 순위로 처리됩니다.

Java에서는 `java.util.PriorityQueue` 클래스가 최소 힙을 기반으로 구현된 우선순위 큐입니다.

 

우선순위 큐는 여러 요소 중 가장 중요한 요소를 반복적으로 선택해야 하는 경우에 사용됩니다.

예를 들어, 최단 경로 알고리즘인 다익스트라 알고리즘에서는 다음으로 방문할 노드 중 비용이 가장 낮은 노드를 선택합니다.

값이 작은 요소가 최우선 순위인 최소 힙 기반 우선순위 큐를 사용하면 됩니다.

---

📌 맵(Map)

키(key)와 값(value)의 쌍으로 이루어진 데이터를 저장하는 자료 구조입니다.

키는 각 값을 고유하게 식별하는 데 사용되며, 덕분에 O(1)에 가까운 속도로 매우 빠르게 탐색이 가능합니다.

• 모든 키는 고유함. 중복된 키로 값을 삽입하면 기존의 값이 덮어씌워짐
• 값은 중복되어도 상관없음

---

📌 셋(Set)

중복되는 요소가 없다는 걸 보장하는 자료 구조입니다.

• 셋에 저장되는 요소들은 모두 고유하며, 여러 번 추가하려 해도 오직 하나만 저장
• HashSet이 흔하며, 순서는 보장하지 않는 특징이 있음

삽입, 삭제, 존재 확인 시 평균 O(1)의 시간 복잡도를 가집니다.

 

---

📌 해시 테이블(Hash Table)

키(key)를 해시 함수(Hash Function)를 통해 배열의 인덱스(Hash Code)로 변환하여

데이터를 저장하고 검색하는 자료 구조입니다.

 

삽입, 삭제, 탐색 시 평균적으로 O(1)이라는 매우 빠른 시간 복잡도를 가집니다.

데이터 탐색의 과정은 다음과 같습니다.

• 저장하려는 데이터의 고유 식별자, 키가 있습니다.
• 키를 입력 받으면 해시 함수에 따라 어떠한 인덱스로 변환합니다.
  • 좋은 해시 함수는 키를 최대한 고르게 분포시켜 인덱스가 겹치지 않도록 충돌을 최소화해야 합니다.
• 해시 함수를 통해 계산된 인덱스에 해당하는 버킷(데이터를 실제로 저장한 창고)을 확인하여 원하는 데이터를 찾습니다.

\

예를 들어 Sam Doe의 전화번호를 찾고 싶다면 키에 Sam Doe를 넣습니다.

해시 함수가 Sam Doe를 254라는 인덱스로 변환합니다.

이 인덱스가 가리키는 버킷을 살펴보니 Sam Doe: 521-5030이라는 데이터를 찾을 수 있었습니다.

 

키가 매우 긴 문자열처럼 큰 데이터인 경우에도 제한된 개수의 버킷 인덱스로 변환할 수 있습니다.

이처럼 해시 함수는 무한에 가까운 키 공간을 유한한 크기의 배열 인덱스로 압축하여 매핑하고

덕분에 대용량의 데이터를 관리하더라고 데이터의 주소를 찾는 공간(버킷 배열) 자체는 작게 유지될 수 있어 메모리 측면에서 효율적입니다.

---

추가 참고자료

• 그래프(자료구조) 위키
• [Data Structure] 이진 트리(Binary Tree)의 세 가지 종류와 특징
• 힙 (최소 힙, 최대 힙)
• [자료구조] 해시테이블(HashTable)이란?