탐색&해싱

탐색이란

여러개의 원소로 구성된 데이터에서 원하는 값을 갖는 원소를 찾는 과정 

 

순차탐색

리스트의 처음부터 끝까지 하나씩 차례로 원소를 확인하면서 원하는 값을 찾는 방식

성능과 특징

• 탐색 (Search)
  원하는 원소를 찾기 위해 리스트의 앞에서부터 하나씩 비교
  → 최악의 경우 O(n)
• 삽입 (Insert)
  리스트의 끝에 추가할 경우는 O(1)
  (단, 특정 위치에 삽입하면 O(n))
• 삭제 (Delete)
  특정 원소를 삭제한 뒤 뒤 원소들을 앞으로 당겨야 하므로 O(n)
• 정렬되지 않고 크기가 작은 데이터에 적합, 데이터가 큰경우 부적합 

이진탐색 

정렬된 리스트에서 원하는 값을 찾기 위해, 매번 탐색 범위를 절반으로 줄여나가는 방식
대표적인 분할 정복(Divide and Conquer) 전략 기반 알고리즘

탐색방법

 

1. 리스트의 중간값을 확인한다.
2. 중간값과 찾는 값을 비교한다.
   • 같으면 탐색 종료
   • 작으면 오른쪽 반쪽에서 다시 탐색
   • 크면 왼쪽 반쪽에서 다시 탐색
3. 범위를 줄여가며 반복한다.

주요 연산 설명

초기화 연산

• 정렬되지 않은 리스트에 대해 이진 탐색을 사용하려면 먼저 정렬이 필요
• 일반적인 정렬 알고리즘 (예: 병합 정렬, 퀵 정렬) 사용 시 O(n log n)의 시간 소요

삽입 연산

• 이진 탐색은 정렬된 상태 유지가 전제이므로, 새로운 값을 삽입하려면:
  • 적절한 위치를 찾고 (O(log n))
  • 해당 위치 이후 모든 원소를 뒤로 밀어야 함 (O(n))
  • 결과적으로 삽입은 O(n)

삭제 연산

• 삭제하려는 값을 먼저 탐색 (O(log n)), 삭제 후 뒤 원소를 앞으로 당김 (O(n))
• 결과적으로 삭제도 O(n)

 

성능과 특징

• 탐색 연산: O(logn)
• 초기화 연산: O(nlogn)
• 삽입/삭제 연산: O(n) 
• 정렬된 리스트에 대해서만 적용가능
• 삽입과 삭제가 빈번한 경우에는 부적합 - 연산 후 리스트의 정렬 상태를 유지하기 위해서 O(n)의 데이터 이동이 필요 

이진탐색트리 

이진 탐색 트리(BST)는 이진 트리의 일종으로, 다음과 같은 조건을 만족하는 트리 구조

• 한 노드의 왼쪽 서브트리에 있는 모든 키 값 < 그 노드의 키 값
• 한 노드의 오른쪽 서브트리에 있는 모든 키 값 > 그 노드의 키 값

탐색 연산

1. 루트 노드에서 시작
2. 찾고자 하는 값이 현재 노드보다 작으면 왼쪽 서브트리로 이동
3. 크면 오른쪽 서브트리로 이동
4. 값을 찾거나 리프 노드에 도달할 때까지 반복

삽입 연산

1. 삽입할 값을 트리에서 탐색한다
2. 탐색 중 존재하지 않는 값을 발견하면 그 자리에 새 노드 생성
3. 트리의 정렬 상태는 유지

삭제 연산

• 삭제되는 노드의 자식 노드의 개수에 따라 구분해서 처리 
  • 자식 노드가 없는 경우: 노드 그냥 삭제 
  • 자식 노드가 하나인 경우: 자식 노드와 부모 노드를 직접 연결
  • 자식 노드가 2개인 경우: 후계 노드 또는 전임 노드 찾아서 교체. 일반적으로 오른쪽 서브트리에서 가장 작은 값을 후계자로 사용 

성능과 특징

• 탐색, 삽입, 삭제: 이진 트리의 높이 h O(h) (키값을 비교하는 횟수에 비례)
• 모든 노드의 차수가 2인 포화이진트리: 평균 수행시간 O(logn) 
• 모든 노드의 차수가 1인 경우 경사이진트리(skewed tree): 최악수행시간 O(n) 
• 삽입/삭제 연산 시 기존 노드의 이동이 거의 발생하지 않음 
• 원소의 삽입/삭제에 따라 경사 트리 형태가 될 수 있음 -> 균형 트리 유지해서 O(logn) 보장 (균형 탐색 트리 )

2-3-4- 트리

균형 탐색 트리의 한 종류로 트리의 높이를 최소화해 탐색 성능을 안정적으로 유지하는데에 목적이 있음 

트리의 규칙 

노드 유형	키 개수	자식 수
2-노드	1개	2개
3-노드	2개	3개
4-노드	3개	4개

• 한 노드 내에서 키 값들은 정렬된 상태를 유지
• 각 키의 왼쪽 서브트리는 해당 키보다 작은 값만 포함
• 각 키의 오른쪽 서브트리는 해당 키보다 큰 값만 포함
• 모든 리프 노드의 레벨은 동일 → 항상 균형 상태 유지

탐색 연산

 

• 루트부터 시작하여 현재 노드에서 적절한 키 비교를 통해 하위 자식 노드로 이동
• 이진 탐색보다 복잡하지만, 트리의 높이가 낮아 빠른 탐색 가능

 

삽입 연산

 

• 루트부터 삽입 위치를 탐색하면서 내려감
• 탐색 도중 4-노드를 만나면 무조건 먼저 분할(split) 수행
  • 4-노드를 2-노드 두 개로 나누고 중간 키를 부모로 올림
  • 분할은 트리 내려가기 전에 수행해야 트리 구조가 깨지지 않음
• 적절한 위치에 삽입

삭제 연산

삭제 시에도 트리를 다시 균형 상태로 유지하기 위해

• 형제 노드에서 값을 빌려오거나
• 병합(merge) 과정을 수행함

 

성능과 특징

• 탐색, 삽입, 삭제: O(logn)
• 삽입/삭제가 일어나도 경사 트리가 되지 않음
• 루트 노드가 분할되는 경우에 한해서 모든 노드의 레벨이 동일하게 1씩 증가 
• 2-3-4 트리는 노드 구조가 복잡해 이진 탐색 트리보다 연산 하나하나는 느릴 수 있음 > 이를 이진 트리 형태로 변형한 레드-블랙 트리를 사용함

레드-블랙 트리

이진 탐색 트리의 일종으로, 트리의 균형을 유지하기 위해 색상 속성과 회전 연산을 활용하는 균형 이진 탐색 트리

트리의 규칙 

• 모든 노드는 검정 이거나 빨강
• 루트 노드와 리프 노드는 검정
• 빨강 노드의 부모 노드는 항상 검정
• 어떤 노드에서 리프 노드까지 모든 경로에는 동일한 수의 검정 노드 존재

탐색 연산 

• 이진트리와 동일 

삽입 연산 

이진 탐색 트리와 유사하나, 삽입 후 트리의 균형 속성을 유지하기 위한 보정 작업이 필요

삽입 후 보정 규칙 

• 빨강 노드가 연달아 나타나는 경우에 적용하는 규칙
• 규칙 1: 부모 노드의 형제 노드가 빨강인 경우 
  • 부모, 형제를 검정으로
  • 조부모를 빨강으로 
  • 조부모 기준으로 다시 검사(재귀적) 
• 규칙2: 부모 노드의 형제 노드가 검정, 현재 노드가 부모와 조부모 키값의 사이인 경우  
  • 현재 노드와 부모를 회전
• 규칙 3: 부모 노드의 형제 노드가 검정, 현재 노드보다 부모와 조부모 키값이 큰(또는 작은) 경우  
  • 부모와 조부모를 회전시키고 색깔을 변경

삽입 시 최악의 경우에도 O(log n)번 회전만 수행되므로 효율적

성능과 특징

• 어떤 두 리프 노드의 레벨 차이가 2배를 넘지 않는 균형 탐색 트리
• 탐색, 삽입, 삭제 연산의 시간 복잡도: O(logn)
• 이진 탐색 트리 기반으로 동작
• 빨강/검정 노드와 회전 연산을 이용해 균형 유지
• 삽입/삭제 시에도 트리 구조가 심하게 무너지지 않음
• 이진 탐색 트리보다 복잡하지만, 성능이 안정적으로 유지됨

B-트리

균형 탐색 트리의 한 종류로 디스크 접근 비용을 최소화하기 위해 고안된 외부 저장장치 친화적 자료구조 

기본성질(차수 t인 경우)

t 는 최소 차수로, 트리의 가지 수를 결정하는 상수 

속성	설명
1. 루트 노드	최소 1개, 최대 2t - 1개의 키를 가짐
2. 루트 외 모든 노드	최소 t - 1개, 최대 2t - 1개의 키를 가짐
3. 자식 노드 수	k개의 키를 가진 노드는 k + 1개의 자식 노드를 가짐
4. 키 정렬	각 노드의 키는 오름차순으로 정렬됨
5. 트리 구조	모든 리프 노드의 깊이는 동일
6. 서브트리 규칙	키의 왼쪽 자식들은 작은 키들, 오른쪽은 큰 키들

 

탐색 연산 

 

1. 루트부터 시작해서 현재 노드 내 키들과 비교
2. 찾고자 하는 값이 현재 노드에 없으면, 적절한 자식 노드로 이동
3. 리프 노드까지 탐색하면서 검색 수행

 

삽입 연산

• 루트 노드에서부터 탐색을 수행해 리프 노드에도 존재하지 않으면 해당 노드에 추가 
• 노드에 빈 공간이 있다면 그대로 삽입
• 노드가 꽉 찬 경우 (2t - 1개의 키) 노드를 분할하고 키를 하나 부모로 올림

노드 분할 예시 

t=3 최대 키 개수 = 2t - 1 = 5 

[10, 20, 30, 40, 50]   ← 2t - 1개의 키 (꽉 참)

25 라는 키 삽입시 노드 분할이 일어남

1. 중간 키를 찾음 > 30이 중간 키
2. 30을 부모노드로 올림
3. 나머지 키들을 기준으로 두 개의 노드로 나눔

        [30]
       /    \
[10, 20]   [40, 50]

성능과 특징

• 탐색, 삽입, 삭제 연산 시간 복잡도: O(logn)
• 각 노드 안에서 키를 찾는 시간은 O(t) 따라서 전체 시간은 O(t × h) = O(t × logₜ n)
• 트리의 높이가 낮고 각 노드에 많은 키 저장 가능
• 삽입/삭제 시에도 트리 균형이 깨지지 않음
• B-트리의 각 노드를 레드-블랙 트리 등으로 구현 가능 → 내부 탐색 속도 개선

해싱(Hashing) 

키 값을 기반으로 데이터의 저장 위치를 직접 계산함으로써 상수 시간내에 데이터를 저장, 삭제, 탐색할 수 있는 방법

해시 함수 

• 키값을 해시 테이블의 주소로 변환하는 함수 
• 계산이 용이하고 적은 충돌이 발생해야함 

주요 해시 함수 설계 방법

제산 잔여법(Division Method)

• h(k) = K mod M (k:키값, M:해시 테이블의 크기) 
• M은 소수로 설정하는 것이 좋음 
• M = 2^r이면 하위 r비트만 사용하게 되어 분포가 불균형해질 수 있음

비닝(Binning)

• 키 값의 전체 범위 U를 단순히 M등분하여 슬롯으로 배정
• 키 값의 범위 U: 0~999 해시테이블 크기 M : 10 
• 상위 비트의 분포가 고르지 못하면 몇개의 슬롯에 몰림 

중간 제곱법 

• h(k) = ((k^2) / 2^m) mod 2^r
  m: 키값을 제곱한 결과에서 사용하지 않을 하위 비트의 크기, r: 해시 주소로 취할 비트의 크기 
• 키를 제곱하고, 중앙의 비트를 해시 주소로 사용
• 키의 상위·하위 자리에 치우치지 않고 고르게 분포하는 장점

문자열 해시 

문자열 비닝

• 문자열의 앞쪽 일부를 해시 결과로 사용 
• 입력 문자열의 앞쪽의 분포가 고르지 못하면 결과가 슬롯에 고르게 분포되지 못함 

단순합

• 각 문자의 ASCII 코드값을 합한후 제산잔여법 적용
• M<sum일때 유용 
• 문자 순서 반영 안됨 (가중합으로 해결) 

가중합

• 각 문자의 코드값이 자리에 따른 가중치를 곱한값을 합한후 제산 잔여법 적용 
• 예: "abc"와 "cab"은 서로 다른 해시값

충돌(collision)

서로 다른 키값 x, y에 대해 h(x) = h(y) 인 경우 

충돌 해결 방법

1. 개방 해싱 (Open Hashing, Chaning)

• 해시 테이블의 각 슬롯을 연결 리스트의 헤더로 사용 
• 충돌이 발생하면 해당 슬롯의 연결 리스트에 노드를 추가하여 저장

2. 폐쇄 해싱(Closed Hashing, Open Addressing) 

 

• 데이터를 해시 테이블 내부에만 저장
• 충돌 발생 시, 빈 슬롯을 찾아가며 저장 (탐사 = probing)

2-1. 선형 탐사 

• 충돌 발생 시, 다음 슬롯으로 순차적으로 이동하며 빈 공간 탐색
• 홈 위치가 사용중이라면 빈 슬롯을 찾을때까지 테이블의 다음 슬롯으로 순차적으로 이동 
• 단점: 1차 클러스터링 
  • 연속된 충돌이 하나의 긴 “덩어리”를 만들어 다음 삽입도 이 범위에 몰리게 되고  성능 저하로 이어짐 
• 예시 

해시 함수: h(k) = k mod 5
테이블 크기: 5
키 삽입 순서: 1, 6, 11

 

• 1 → 1 mod 5 = 1 → 슬롯 1 저장
• 6 → 6 mod 5 = 1 → 슬롯 1 충돌 → 슬롯 2로 이동
• 11 → 11 mod 5 = 1 → 슬롯 1 → 2 → 슬롯 3 저장

2-2.이차 탐사

• 충돌 시, 탐사 간격을 제곱으로 늘림
• 서로 다른 홈 위치를 갖는 두 키는 서로 다른 탐사 순서를 가짐 
• 모든 슬롯이 탐사 순서에 사용되지 않음 
• 단점: 2차 클러스터링 
  • 같은 해시값을 갖는 키끼리는 같은 탐사 순서를 가짐 → 이들끼리 또 클러스터링을 유발

2-3. 이중 해싱 

• 충돌 시 다른 해시 함수를 이용해 탐사 간격을 계산

p(k, i) = (h₁(k) + i × h₂(k)) mod M

• h₁(k): 기본 해시 함수
• h₂(k): 보조 해시 함수 (탐사 간격용)
• M과 h₂(k)는 서로소여야 테이블 전체를 탐사 가능
• 탐사 경로가 다양해서 1/2차 클러스터링 문제 해결 
• h₂(k)는 0이 되면 안 되고, 테이블 크기 M과 서로소여야 모든 슬롯 탐색 가능

삭제 연산과 비석(Tombstone)

• 단순히 해당 슬롯을 비워두면, 탐색 중 조기 종료 문제 발생
• 비석(Tombstone) 표시를 남겨야 함
• 삭제된 자리를 탐색할 땐 무시하지 않고, 삽입할 땐 빈 슬롯처럼 사용해야함 

비석

• 삭제된 데이터의 위치에 특별한 표시
• 탐색시 비석을 만나면 계속 탐색
• 삽입시 비석이 표시된 위치를 빈 위치로 간주하여 새 데이터 삽입 
• 비석이 증가할수록 평균 탐색 거리가 증가 > 주기적으로 리해싱 필요