4.3 비선형 자료구조

비선형 자료구조 : 하나의 데이터 뒤에 N개의 데이터가 이어질 수 있는 1:N , N:N 구조로 데이터가 나열되는 자료구조 

 

4.3.1 그래프

데이터를 포함하는 정점(vertex)(=노드)과 정점을 잇는 간선(edge)으로 구성된 자료 구조

• 인접(adjacent): 두 정점이 간선으로 연결되어 있으면 인접하다고 표현
• 차수(degree): 정점에 연결된 간선의 수
• 진입 차수(in-degree): 해당 점점으로 향하는 간선의 수
• 진출 차수(out-degree): 해당 점점에서 나가는 간선의 수
• 경로(path): 한 정점에서 다른 정점으로 이어지는 정점들의 리스트 
• 경로 길이(path length): 경로를 구성하는 간선의 수
• 단순 경로(simple path): 모두 다른 정점으로 구성된 경로
• 사이클(cycle): 한 정점에서 시작해 같은 정점으로 돌아올 수 있는 경로

 

그래프의 종류

1. 무방향 그래프
   • 간선에 방향성이 없는 그래프
   • 정점의 개수가 n일 때 최대 간선의 개수 = n x (n-1) / 2 
2. 방향 그래프
   • 간선에 방향성이 있는 그래프
   • A에서 B로 향하는 간선 표기 : <A,B>
   • 점의 개수가 n일 때 최대 간선의 개수 = n x (n-1) 
3. 부분 그래프 : 기존 그래프에서 일부 정점 또는 간선을 제외한 그래프
4. 가중치 그래프 : 간선에 비용이나 가중치가 할당된 그래프
5. 완전 그래프 : 간선을 최대로 가진 그래프로 연결 그래프라고도 한다. 무방향 그래프의 간선 수가 n x (n-1) / 2 일 때, 방향 그래프의 간선의 수가 n x (n-1)  일 때 완전 그래프라고 함.
6. 유향 비순환 그래프 : 방향 그래프이면서 사이클이 없는 그래프

 

경로 탐색

1. 너비 우선 탐색(BFS, Breadth-First Search)

탐색을 시작하는 정점에서 가까운 정점을 먼저 탐색하는 방식, 먼저 발견한 정점과 인접한 정점들을 탐색하면서 큐에 삽입한다. 

너비 우선 탐색을 하면 비가중치 그래프에서 시작 정점부터 특정 정점까지의 최단 거리를 알 수 있다.

 

2. 깊이 우선 탐색(DFS, Depth-First Search)

시작 정점에서 탐색 가능한 최대 깊이의 정점까지 탐색하는 방식, 최대 깊이인 정점에 도달했다면 방문한 정점들을 역순으로 재방문하면서 탐색 가능한 정점이 있는지 확인한다. 탐색 가능한 정점이 있다면 해당 정점부터 다시 최대 깊이 정점까지 탐색을 진행한다. 

재귀 호출 또는 스택으로 구현할 수 있다. 

 

 

4.3.2 트리

그래프의 한 종류로 사이클이 없어서 계층적 관계를 표현할 수 있다.

 

• 루트 노드: 부모 노드가 없는 노드로, 트리에는 하나의 루트 노드가 존재한다.
• 부모 노드: 루트 노드 방향으로 연결된 노드 
• 자식 노드: 루트 노드의 반대 방향으로 연결된 노드
• 단말 노드: 자식 노드가 없는 노드
• 형제 노드: 부모 노드가 같은 노드
• 레벨: 루트 노드로부터 노드의 상대적 위치, 루트 노드의 노드 레벨은 0.
• 높이: 트리의 최대 레벨 +1 을 의미
• 차수: 자식 노드의 개수

 

이진트리 : 자식 노드가 최대 2개인 노드 

1. 완전 이진 트리 : 마지막 레벨을 제외한 모든 레벨에 노드가 채워져 있으며, 마지막 레벨은 왼쪽에서부터 오른쪽으로 노드가 채워져 있는 이진 트리다.

2. 포화 이진 트리: 마지막 레벨까지 노드가 모두 채워져 있는 이진 트리. 포화 이진 트리는 완전 이진 트리임

3. 이진 탐색 트리: 왼쪽 서브 트리는 해당 노드의 값보다 작은 값을 가진 노드로 구성되고, 오른쪽 서브 트리는 해당 노드의 값보다 큰 값을 가진 노드로 구성된 트리. 균형 잡힌 이진 탐색 트리에서는 루트 노드와 가까운 노드일수록 검색해야하는 노드 개수가 절반으로 줄어든다. 

완전 이진 트리로 이진 탐색 트리를 구성하려면 균형 이진 탐색 트리가 필요하다. 

 

*이진 탐색 트리에서 데이터 추가 & 삭제 연산 방식

추가: 루트 노드부터 차례대로 값을 비교해 나가면서 삽입할 자리를 찾는다. 왼쪽에 작은값을 가져야함

삭제: 자식 노드가 없는 경우 해당 노드만 삭제하고, 자식 노드가 1개인 경우는 자식 노드를 삭제한 노드 위치로 옮기면 되고, 자식 노드가 2개인 경우는 오른쪽 서브 트리에서 가장 작은 값을 삭제한 노드 위치로 옮기면 된다.

 

* 균형 이진 탐색 트리: 삽입이나 삭제 연산을 수행해도 트리의 균형을 유지하는 트리

ex) 1. 레드-블랙 트리 : 노드가 검은색 또는 빨간색인 트리로 정해진 규칙을 만족하면서 균형을 유지하는 트리

ex) 2. AVL트리: 잦가 균형 이진 탐색 트리로, 왼쪽 서브 트리와 오른쪽 서브 트리의 높이 차이를 유지해 균형을 잡는 트리

         높이차이를 알려면 왼쪽 서브 트리의 높이에서 오른쪽 서브 트리의 높이를 뺀 값인 BF(Balance Factor)를 사용한다. 

 

 

4.3.3 우선순위 큐

우선순위가 높은 데이터가 먼저 나오는 자료구조

큐와 동일하게 데이터 삽입과 삭제 연산을 지원한다. 데이터 삭제 연산을 수행하면 우선순위가 가장 높은 데이터를 얻을 수 있다.

우선순위 큐를 구현하는 방식은 배열, 연결 리스트, 완전 이진트리인 힙이 있다. 

일반적으로 가장 효율적인 방식인 힙을 사용한다. 

 

구현 방법	삽입	삭제
배열(unsorted array)	O(1)	O(n)
연결 리스트(unsorted linked list)	O(1)	O(n)
배열(sorted array)	O(n)	O(1)
연결 리스트(sorted linked list)	O(n)	O(1)
힙(heap)	O(log n)	O(log n)

 

 

4.3.4 힙

완전 이진 트리로, 최댓값 또는 최솟값을 빠르게 찾을 수 있는 자료구조다.

• 최대 힙(max heap): 부모 노드의 값이 자식 노드의 값보다 크거나 같은 완전 이진 트리
• 최소 힙(min heap): 부모 노드의 값이 자식 노드의 값보다 작거나 같은 완전 이진 트리

1. 삽입 연산
   • 힙의 맨 끝에서 이루어지며, 부모 노드와 우선순위를 비교해 부모 노드보다 우선 순위가 높으면 위치를 바꾸면서 루트 노드까지 비교한다. 
2. 삭제 연산
   • 우선순위가 가장 높은 노드를 삭제하는 연산으로, 로트 노드를 삭제하게 된다. 
   • 삭제 후에는 루트 노드 자리에 힙의 마지막 노드(마지막 레벨 가장 오른쪽 노드)를 옮긴 후 힙을 재정렬한다. 

 

4.3.5 해시 테이블

하나의 키에 대해 하나의 값을 저장하는 형태의 자료구조 

키는 해시 함수를 사용해 해시를 얻을 수 있다. (해시: 값이 저장되어 있는 해시 테이블의 인덱스를 찾을 수 있는 값)

해시 함수에 키를 넣으면 해시 테이블에서 매칭되는 결과 값에 한 번에 접근 가능함. O(1)의 시간복잡도를 갖는다. 

 

단점: 해시 충돌 (서로 다른 키에 대해 같은 해시가 도출되는 것)

해시 충돌 해결 방안

1. 체이닝(chaining) : 해시 충돌이 발생하면 같은 해시가 나오는 키의 값을 연결 리스트에 저장하는 방식. 저장 공간에 대한 제약이 적다는 장점이 있지만, 하나의 해시에 노드가 몰릴 수 있다는 단점이 있다.
2. 개방 주소법(open addressing) : 해시 충돌이 발생했을 때 해당 해시가 아닌 비어있는 공간에 값을 저장하는 방식
   • 선형 조사법(빈 공간 찾는법) / 이차 조사법(빈 공간 찾는법)  / 이중 해싱(다른 해시 함수 한 번 더 적용)