알고리즘 7강 (탐색)

 학습개요

1. 탐색 알고리즘에 대한 지난 강의에 이어서 이번 시간에는 균형 탐색 트리로서 레드-블랙 트리와 B-트리를 이용하는 탐색 방법에 대해서 학습한다. 또한 삽입, 삭제, 탐색 연산을 기본적으로 상수 시간에 수행할 수 있는 해싱 기법에 대해서 살펴본다.

 학습목표

1. 레드-블랙 트리의 개념, 동작 그리고 성능과 특징을 이해하고 설명할 수 있다.
2. B-트리의 개념, 동작, 그리고 성능과 특징을 이해하고 설명할 수 있다.
3. 해싱의 개념, 그리고 해시 함수 및 충돌 해결 방법의 종류와 특징을 이해하고 설명할 수 있다.

 주요용어

1. 레드-블랙 트리(red-black tree)
   - 2-3-4 트리를 이진 탐색 트리 형태로 구현한 것으로서, 검정 노드와 빨강 노드로 구성된 균형 탐색 트리
2. B-트리
   - 각 노드에 최대 2t개 미만의 키와 키의 개수보다 하나 더 많은 자식을 가질 수 있는 균형 탐색 트리
3. 노드 분할(node split)
   - B-트리에서 삽입을 위한 탐색 과정에서 (2t-1)개의 키를 갖는 노드를 만나면 이 노드를 (t-1)개의 키를 갖는 두 개의 노드와 t번째의 1개의 키로 구성된 하나의 노드로 분할하고, t번째 키를 부모 노드로 이동시키는 연산
4. 해시 테이블(hash table)
   - 각 위치마다 주소가 부여된 저장공간으로, 보통 배열 형태로 표현
5. 해싱(hashing)
   - 탐색 키값을 기반으로 데이터의 저장위치를 직접 계산함으로써 기본적으로 상수 시간 내에 데이터를 저장, 삭제, 탐색하는 방법
6. 해시 함수(hash function)
   - 주어진 키값을 해시 테이블의 주소를 변환하는 함수
   - 제산 잔여법, 중간 제곱법 등 매우 다양한 함수가 존재
7. 충돌(collision)
   - 서로 다른 키값이 같은 해시 테이블 주소로 사상되는 현상
   - 충돌 해결 방법으로는 개방 해싱과 폐쇄 해싱(버킷 해싱, 선형 탐사, 이차 탐사, 이중 해싱)이 있음

정리하기

1. 레드-블랙 트리
    ⦁ 이진 탐색 트리로서 다음의 성질을 추가로 만족하는 균형 탐색 트리
    ① 모든 노드는 검정이거나 빨강
    ② 루트 노드와 리프 노드는 검정(단, 모든 리프 노드는 NULL 노드)
    ③ 빨강 노드의 부모 노드는 항상 검정 → 빨강 노드가 연달아 나타나지 않음
    ④ 임의의 노드로부터 리프 노드까지의 경로상에는 동일한 개수의 검정 노드가 존재
    ⦁ 탐색 연산 → 이진 탐색 트리의 탐색 방법과 동일
    ⦁ 삽입 연산 → 탐색이 실패한 NULL 노드에 빨강 노드로 추가하고 두 자식 노드를 NULL 노드로 만듦
    - 이때 빨강 노드가 연달아 나타나면 레드-블랙 트리의 성질을 만족하도록 루트 노드쪽으로 올라가면서 노드의 구조와 색깔을 조정하는 추가 연산이 필요 → 이를 위해 3가지 경우로 구분하여 규칙이 적용됨
    ⦁ 성능 → O(logn)
    ⦁ 레드-블랙 트리는 2-3-4 트리를 이진 탐색 트리로 표현한 것
2. B-트리
    ⦁ 균형 탐색 트리
    ① 루트 노드는 1 ~ (2t-1)개의 오름차순으로 정렬된 키를 가짐
    ② 루트 노드가 아닌 모든 노드는 (t-1) ~ (2t-1)개의 오름차순으로 정렬된 키를 가짐
    ③ 내부 노드는 자신이 가진 키의 개수보다 하나 더 많은 자식 노드를 가짐
    ④ 각 노드의 한 키의 왼쪽 서브트리에 있는 모든 키값은 그 키값보다 작고, 오른쪽 서브트리에 있는 모든 키값은 그 키값보다 큼
    ⑤ 모든 리프 노드의 레벨은 동일
    ⦁ 탐색 연산 → 이진 탐색 트리와 유사한 방법으로 진행
    ⦁ 삽입 연산 → 루트 노드에서부터 탐색을 수행하여 리프 노드에도 존재하지 않으면 해당 노드에 추가
    - 노드 분할 → 삽입을 위한 탐색 과정에서 (2t-1)개의 키를 갖는 노드를 만나면 이 노드에서 t번째 키는 부모 노도로 이동시키고 나머지는 키들은 (t-1)개의 키를 갖는 2개의 노드로 분할
    ⦁ 성능 → O(logn)
    ⦁ 내부 탐색과 외부 탐색에 모두 활용
3. 해시 테이블
    ⦁ 해싱 → 탐색 키값을 이용하여 데이터가 저장된 테이블의 주소를 직접적으로 계산하여 상수 시간 내에 접근할 수 있는 탐색 방법
    ⦁ 해시 함수 → 키값을 해시 테이블 주소로 변환하는 함수
    - 종류 → 제산 잔여법, 비닝, 중간 제곱법, 문자열을 위한 해시 함수(비닝, 단순 합, 가중 합) 등 매우 다양
    ⦁ 충돌 → 서로 다른 키값 x, y에 대하여 h(x)=h(y)인 경우
    ⦁ 충돌 해결 방법 → 개방 해싱, 폐쇄 해싱
    ⦁ 개방 해싱(“연쇄법”) → 충돌된 데이터를 해시 테이블 밖의 별도의 장소에 저장 → 동일한 주소로 해시되는 모든 원소를 연결 리스트 형태로 구성하여 관리하는 방법
    ⦁ 폐쇄 해싱(“개방 주소법”) → 테이블 내의 다른 슬롯에 충돌된 데이터를 저장·관리하기 위해 정해진 방법에 따라 테이블의 다른 위치를 탐사하는 방법
    - 종류 → 버킷 해싱, 선형 탐사(→ 1차 클러스터링 문제), 이차 탐사(→ 2차 클러스터링 문제), 이중 해싱
    ⦁ 데이터 삭제 → 삭제된 위치에 ‘비석’이라는 특별한 표시를 함
    - 탐색 → 탐색하는 동안 비석을 만나면 탐색을 계속 진행
    - 삽입 → 비석이 표시된 위치를 빈 위치로 간주하여 새 데이터를 삽입