데이터 입출력 구현 6

검색(Search, 탐색)

06. 이진 트리 검색(Binary Tree Search)

1) 이진 트리 검색

• 검색 대상의 자료를 이진 트리로 변경한 뒤 검색하는 방법
• 처음의 자료는 근노드가 되고, 두 번째 자료는 근노드와 비교해서 작으면 왼쪽으로 크면 오른쪽으로 연결함
• 모두 연결된 이진 트리를 근노드에 있는 값과 비교하여 찾고자 하는 값에 따라 왼쪽 또는 오른쪽을 다시 비교함

2) 이진 트리 검색 알고리즘

• 검색 대상의 자료가 10개, 찾고자 하는 자료가 11인 경우
• 이진 트리 검색의 시간 복잡도는 O(log₂n)
  • O(log₂10) = O(3.32..)이므로 대략 3번에서 4번 만에 찾게 됨

1	2	3	4	5	6	7	8	9	10
5	8	3	7	9	1	11	2	4	21

1. 1번째 자료가 5이므로 근노드가 되고, 2번째 자료 8은 5보자 크므로 오른쪽에, 3번째 자료 3은 5보다 작으므로 왼쪽에 연결
2. 4번째 자료 7은 8보다 작으므로 8의 왼쪽에, 5번째 자료 9는 8보다 크므로 8의 오른쪽에 연결
3. 6번째 자료 1은 3보다 작으므로 3의 왼쪽에, 7번째 자료 11은 9보다 크므로 9의 오른쪽에 연결
4. 8번째, 9번째, 10번째 자료도 같은 방법으로 연결
5. 찾고자 하는 자료 11은 4번째 만에 찾게 됨

3) AVL 트리(Adelson, Velskii, Landis, 균형 이진 트리)

• 이진 트리 검색의 효율을 높이기 위해 구성
• AVL 트리는 왼쪽 서브 트리와 오른쪽 서브 트리가 균형이 맞지 않으면 검색 속도가 늦어질 수 있으므로 트리의 균형이 맞도록 균형 인수를 ±1이나 0으로 맞추는 트리를 말함
• 노드가 삽입되거나 삭제될 때 트리의 모양이 변함

4) 2-3 트리

• AVL 트리에서는 삽입과 삭제 시 전체 트리를 재구성해야 하는 부담이 발생함
• 2-3 트리는 AVL 트리의 재구성 부담을 최대한 줄이는 방식
• 2-3 트리는 이진 트리 구조는 아님
• AVL 트리는 균형 트리를 지향하지만 2-3 트리는 완전 균형 트리를 지향함

5) 레드-블랙(Red-Black) 트리

• 이진 트리를 구성할 때 조건을 부여하고 AVL 트리로 구성하는 방법

1. 레드-블랙 트리의 조건

• 모든 노드는 레드(Red) 노드나 블랙(Black) 노드이어야 함
• 루트 노드는 반드시 블랙 노드
• 삽입되는 노드는 반드시 레드 노드로 삽입
• 레드 노드의 자식은 반드시 블랙 노드
• 리프 노드는 반드시 블랙 노드
• 레드 노드를 연속으로 하위 노드로 연결할 수 없음
• 블랙 노드는 연속으로 하위 노드로 연결할 수 있음
• 리프 노드에서 루트 노드까지 가는 경로에서 만나는 블랙 노드의 개수는 같음
• 단노드가 레드 노드이면 리프 노드는 블랙 노드

---

07. 해싱 검색(Hashing Search)

1) 해싱 검색

• 자료를 찾는 특별한 규칙으로 검색 대상의 자료를 저장하여 자료를 찾음
• 특별한 규칙이란 해싱 함수를 말하며 해싱 함수의 결과로 자료들의 저장 위치(주소)가 결정됨
• 해싱 함수로 계산된 저장 위치가 중복될 때에는 충돌이라고 하며 충돌에 대비한 조치가 필요함
• 서로 다른 탐색키가 해싱 함수를 통해 동일한 해시 주소로 사상될 수 있음
• 충돌이 발생하지 않는 해싱 함수를 사용한다면 해싱 검색의 시간 복잡도는 O(n)

2) 해싱 함수

해싱 함수 종류	사용 방법
제산법(Division)	레코드 키 값을 소수나 전체 자료수로 나누어 그 나머지 값으로 저장할 위치를 정하는 방법
폴딩법(Folding)	레코드 키 값을 여러 부분으로 나누고, 나눈 부분의 각 숫자를 더하거나 XOR한 값을 홈 주소로 사용하는 방법
제곱법(Square)	레코드 키 값을 제곱한 결과 값의 일부를 선택하여 저장할 위치는 정하는 방법
중간 제곱법(Mid-Square)	레코드 키 값을 제곱하고, 이 값의 중간 부분을 취하여 홈 주소로 취하는 해싱 방법
숫자 분석법(Digit Analysis)	레코드 키 값을 이루는 숫자들의 분포를 파악해서 분포가 고른 부분을 선택해 저장할 위치를 정하는 방법
기수 변환법(Radix Transformation)	레코드 키 값을 숫자의 진수를 다른 진수로 변환시켜 주소 크기를 초과한 높은 자릿수는 절단하고, 이를 다시 버킷의 개수 범위에 맞게 조정하는 방법
의사 무작위법(Pseudo-random)	난수를 발생시킨 후 그 난수를 이용하여 저장할 홈 주소의 위치를 정하는 방법

3) 해싱 용어 정리

1. 해시 테이블(Hash Table)
   • 해싱 함수 값에 해당되는 위치에 각 레코드를 기억시킨 테이블로 레코드를 한 개 이상 보관할 수 있는 버킷들로 구성된 기억 장소
2. 버킷(Bucket) 주소
   • 해싱 함수에 의해서 결정된 홈 주소로 해싱 주소라고도 함
   • 버킷은 자료가 저장될 공간을 말하며 하나의 버킷에는 여러 개의 자료를 기억할 슬롯(Slot)이 존재함
3. 슬롯(Slot)
   • 한 개의 자료를 저장할 수 있는 공간으로 n개의 슬롯이 모여 하나의 버킷을 형성
   • n개의 슬롯을 연결하는 방법에는 선형 방법, 연결 체인법, 무작위법 등이 있음
4. 동거자(Synonym, 동의어)
   • 서로 다른 키 값이지만 해싱 함수에 의해 같은 버킷에 저장되는 키 값들
5. 충돌(Collision)
   • 해싱 함수에 의해서 서로 다른 키가 같은 홈 주소를 갖게 되는 현상
   • 해싱 검색의 문제점은 서로 다른 키 값이 해싱 함수에 의하여 계산될 때 항상 유일한 주소가 생성되는 것이 아니고 중복될 때가 있다는 점으로 이때 두 레코드가 같은 기억 공간을 점유하려는 현상
6. 오버플로우(Overflow)
   • 버킷에 할당된 슬롯 수보다 많이 발생하게 되면 버킷에 더 이상 항목을 저장할 수 없는 경우에 발생
7. 프로빙(Probing)
   • 충돌이 발생하여 더 이상 같은 홈 주소를 갖는 버킷을 사용할 수 없을 때 사용하지 않는 다른 버킷을 찾아 저장하는 방법으로 1차 조사법, 2차 조사법 등이 있음
8. 체인법(Chaining)
   • 해싱에서 오버플로우 발생 시 이를 해결하기 위한 방법으로 연결 리스트를 사용하며 버킷의 크기에 제한을 두지 않는 기법
   • 해시 테이블의 구조를 변경하여 각 버킷에 하나 이상의 키 값을 저장할 수 있도록 하는 방법
   • 최악의 경우, 즉 모든 레코드의 키가 같을 경우 연결 리스트에 연결된 레코드를 검색해야 하는 부담이 있음

4) 해싱 함수의 조건

1. 충돌이 적아야 함
   • 충돌이 많이 발생한다는 것은 같은 버킷을 사용하는 키 값이 많다는 것
   • 비어 있는 버킷이 많은 경우에도 오버플로우가 발생하면 좋은 해싱 함수가 될 수 없음
   • 해싱 테이블에서 하나의 탐색키에 여러 개의 공간을 할당할 수 있어야 함
2. 계산이 복잡하지 않고 쉬워야 함
   • 키 값의 비교 연산이 너무 복잡하지 않고 쉽고 빠르게 처리될 수 있어야 함

---

08. 그래프 탐색(Traversal)

1) 그래프 탐색

• 그래프의 모든 정점을 방문하는 것을 그래프 탐색이라고 함
• 그래프 구조의 자료를 검색하고, 저장하고, 연산하는데 필요한 기본 알고리즘을 제공
• 그래프 탐색에는 깊이 우선 탐색과 너비 우선 탐색이 있음

2) 너비 우선 탐색(BFS : Breadth First Search)

• 너비 우선 탐색은 큐(Queue) 구조를 이용하여 운용
• 시작 노드(A)에서 인접한 노드를 모두 알파벳순으로 큐에 삽입

3) 깊이 우선 탐색(DFS : Depth First Search)

• 깊이 우선 탐색은 스택(Stack) 구조를 이용하여 운용
• 시작 노드(A)에서 인접한 노드 중 하나를 알파벳순으로 스택에 삽입

---

09. B-트리

1) B-트리

• 대용량 파일을 효율적으로 검색하고 수정하기 위해서 사용되는 트리

2) B-트리의 특징

• 일반적으로 데이터베이스와 파일 시스템에서 사용되는 자료 구조
• 하나의 노드는 인덱스 영역과 데이터 영역으로 구성
• 루트 노드는 리프 노드가 아닌 이상 적어도 2개의 자식 노드를 가져야 함
• 하나의 노드는 2개 이상의 인덱스를 기억할 공간이 있어야 함
• 이진 트리는 원소가 삽입될 때 하향식이지만 B-트리는 상향으로 삽입되기도 함
• 삽입/삭제 시에는 자동으로 합병이나 분할됨
• 한 노드 안에 있는 키 값은 오름차순으로 정렬되어 있어야 함
• 루트 노드와 리프 노드를 제외한 모든 노드는 최소한 m/2개에서 m개의 자식 노드를 가져야 함
• k개의 자식을 가지고 있는 노드(리프 노드 제외)는 k-1개의 키를 가짐

3) B-트리 삽입 방법

• 모든 삽입은 리프 노드에서부터 시작함
• 새 원소(키 값)를 삽입하기 위해서는 해당 원소가 삽입되어야 하는 리프 노드를 찾은 다음 삽입을 진행함
• 노드의 빈자리가 있으면 원소 순서에 맞게 원소를 삽입
• 노드가 꽉 차 있으면 노드를 2개로 분할

4) B-트리의 변형

• B^* 트리 : B-트리의 변형으로 빈번한 노드의 분열을 줄이고자 개발된 트리 구조
• B⁺ 트리 : B-트리의 변형으로 레코드의 효율적인 삽입, 검색과 삭제를 위해 개발된 트리 구조