5-3. 비선형 자료 구조 - 그래프, 트리, 힙, 우선순위 큐, 맵, 셋, 해시 테이블

1. 그래프 (Graph)

그래프는 객체 간의 복잡한 연결 관계를 정점과 간선으로 표현하는 비선형 자료 구조이다.

 

- 정점 : 연결 관계를 가지는 객체 자체

- 간선 : 정점들을 연결하는 선, 정점 사이의 관계

- 가중치 : 간선에 부여된 값, 정점 사이의 비용, 거리, 중요도 등을 표현

 

 

 

2. 트리 (Tree)

트리는 그래프의 한 종류로, 사이클이 없는 비순환적 연결 구조이다. 부모-자식과 같은 계층적 관계를 표현하는 데 적합하다. 트리의 각 노드는 깊이(레벨)를 가지며, 루트 노드부터 특정 노드까지 최단 거리로 갔을 때의 거리를 말한다. 트리의 높이는 루트 노드부터 리프 노드까지의 가장 긴 거리를 말한다. 트리 내에는 서브 트리라고 하는 부분 집합도 존재할 수 있다.

 

- 루트 노드 : 트리 구조에서 가장 최상위에 있는 노드

- 내부 노드 : 루트 노드와 리프 노드 사이에 있는 자식 노드를 가진 노드

- 리프 노드 : 자식 노드가 없는 가장 말단에 있는 노드

 

1) 이진 트리

이진 트리는 모든 노드가 최대 2개의 자식 노드를 가진 트리이다.

 

- 정이진 트리 : 자식 노드가 0 또는 두개인 이진 트리

- 완전 이진 트리 : 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있으며, 왼쪽부터 채워지는 이진 트리

- 변질 이진 트리 : 자식 노드가 하나 뿐인 이진 트리

- 포화 이진 트리 : 모든 노드가 꽉 차있는 이진 트리

- 균형 이진 트리 : 왼쪽과 오른쪽 노드의 높이 차이가 1 이하인 이진 트리

 

2) 이진 탐색 트리

이진 트리의 일종이다. 특정 노드의 왼쪽 서브 트리에는 작은 값이, 오른쪽 노드에는 큰 값이 있는 트리이다.

 

3) AVL 트리

두 자식 서브트리의 높이는 항상 최대 1만큼 차이 나는 이진 탐색 트리이다. 삽입 및 삭제 시, 노드의 균형 인수를 계산하여 균형이 깨지면 회전 연산을 통해 스스로 균형을 잡는 트리이다.

 

4) 레드 블랙 트리

AVL 트리와 마찬가지로 스스로 균형을 잡는 이진 탐색 트리이다. 노드에 '레드' 또는 '블랙' 색을 부여하고, 몇 가지 규칙을 통해 트리의 높이를 제한한다. AVL 트리보다 균형 조건이 덜 엄격하며, 삽입/삭제 시 회전 횟수가 적다.

 

 

 

3. 힙 (Heap)

완전 이진 트리 형태를 유지하면서, 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크거나 작도록 정렬하는 자료 구조이다.

 

- 최대 힙 : 부모 노드의 값 >= 자식 노드의 값

- 최소 힙 : 부모 노드의 값 <= 자식 노드의 값

 

 

 

4. 우선순위 큐 (Priority Queue)

들어온 순서(FIFO)가 아닌 우선순위가 높은 데이터가 먼저 나가는 추상 자료형이다. 일반적으로 힙 자료 구조를 이용하여 구현되며, 운영체제의 작업 스케줄링 혹은 네트워크 트래픽 제어 시에 사용된다.

 

 

 

5. 맵 (Map)

키와 값의 쌍으로 데이터를 저장하는 자료 구조이다. 키는 고유해야 하며, 이 키를 통해 값에 접근한다. 레드 블랙 트리 자료 구조를 기반으로 형성되고, 데이터를 삽입하면 자동으로 정렬된다. 파이썬에서는 딕셔너리와 동일하다.

 

 

 

6. 셋 (Set)

고유한 원소들의 집합을 저장하는 자료 구조이다. 중복된 원소를 허용하지 않으며, 주로 원소의 존재 여부를 확인할 때 사용된다. 

 

 

 

7. 해시 테이블 (Hash Table)

키를 해시 함수를 사용하여 계산된 주소에 저장하는 자료 구조이다. 서로 다른 키가 동일한 주소로 계산될 때 충돌이 발생할 수 있으며, 이를 해결하기 위해선 체이닝, 개방 주소법 등이 사용된다. 맵(Map)과 셋(Set)의 내부 구현에 해시 테이블이 사용된다.