3장 탐색

순차 탐색

• 리스트 형태로 주어진 원소들을 처음부터 하나씩 차례대로 비교하면서 원하는 값을 가진 원소를 찾는 방법
• 성능 → O(n)
• 모든 리스트 형태의 입력에 적용 가능 → 특히 비정렬 데이터 탐색에 적합
• 데이터가 큰 경우에는 부적합

이진 탐색

정렬된 리스트 형태로 주어진 원소들을 절반씩 줄여가면서 원하는 값을 가진 원소를 찾는 방법 - 분할정복 방법 적용

• 탐색 연산 - O(logn)
• 초기화 연산 - O(nlogn)
• 삽입/삭제 연산 - O(n)

이진 탐색 트리

이진 트리

• 한 노드의 왼쪽 서브트리에 있는 모든 키 값은 그 노드의 키값보다 작다. 
• 한 노드의 오른쪽 서브트리에 있는 모든 키 값은 그 노드의 키값보다 크다. 

• 루트 노드에서부터 시작해서 값의 크기 관계에 따라 트리의 경로를 따라 내려가면서 탐색 진행

• 삽입할 원소를 탐색한 후, 탐색이 실패하면 해당 위치에 자식 노드로서 새 노드를 추가 

---

균형 탐색 트리

2-3-4트리

• 2노드 - 1개의 키와 2개의 자식을 갖는 노드
• 3노드 - 2개의 키와 3개의 자식을 갖는 노드
• 4노드 - 3개의 키와 4개의 자식을 갖는 노드 
• 각 노드의 한 키의 왼쪽 서브트리에 있는 모든 키값은 그 키값보다 작다.
• 각 노드의 한 키의 오른쪽 서브트리에 있는 모든 키값은 그 키값보다 크다.
• 모든 리프 노드의 레벨은 동일

• 탐색 과정에서 4노드를 만나면 항상 노드 분할을 우선 수행

예

• 균형 탐색 트리의 최대 높이는 logn
• 삽입/삭제가 일어나도 경사 트리가 되지 않음 
• 루트노드가 분할되는 경우에 한해서 모든 노드의 레벨이 동일하게 1씩 증가
• 단점은 노드 구조가 너무 복잡함 
• 이진 탐색 트리보다 더 느려질 가능성이 많음

레드 블랙 트리

• 모든 노드는 검정이거나 빨강이다. 
• 루트 노드와 리프 노드는 검정이다.
  • 모든 리프 노드는 NULL 노드이다.
• 빨강 노드의 보무 노드는 항상 검정이다.
  • 빨강 노드가 연달아 나타날 수 없다.
• 임의의 노드로부터 리프 노드까지의 경로상에는 동일한 개수의 검정 노드가 존재한다. 
• 각 노드의 한 키의 왼쪽 서브트리에 있는 모든 키값은 그 키값보다 작다.
• 각 노드의 한 키의 오른쪽 서브트리에 있는 모든 키값은 그 키값보다 크다.

• 탐색

• 어떤 두 리프 노드의 레벨 차이가 2배를 넘지 않는 균형 탐색 트리 
• O(logn)

B - 트리

• 루트 노드는 1개 이상 2t개 미만의 오름차순으로 정렬된 키를 가짐
• 루트 노드가 아닌 모든 노드는 (t-1)개 이상 2t개 미만의 오름차순으로 정렬된 키를 가짐
• 내부 노드는 자신이 가진 키의 개수보다 하나 더 많은 자식 노드를 가짐
• 모든 리프 노드의 레벨은 동일 함
• 각 노드의 한 키의 왼쪽 서브트리에 있는 모든 키값은 그 키값보다 작다.
• 각 노드의 한 키의 오른쪽 서브트리에 있는 모든 키값은 그 키값보다 크다.

해시 테이블

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

해싱의 개념

해시 함수

키값을 해시 테이블의 주소로 변환하는 함수 

종류

• 제산 잔여법, 비닝, 중간 제곱법, 문자열을 위한 함수(비닝, 단순 합, 가중 합) 등 

바람직한 해시 함수

• 계산이 용이해야 함
• 적은 충돌 발생 - 각 키를 테이블의 각 슬롯에 균등하게 사상시킬 수 있어야 함
• 제산 잔여법

• 비닝 

• 중간 제곱법

• 문자열을 위한 비닝

충돌 해결 방법

• 개방해싱
• 폐쇄해싱 

개방 해싱(Open Hashing)과 폐쇄 해싱(Closed Hashing)의 상세 설명해싱은 데이터를 효율적으로 저장하고 검색하기 위한 자료 구조 기법으로, 해시 함수(Hash Function)를 사용해 데이터를 특정 위치(해시 테이블의 슬롯)에 매핑합니다. 그러나 해시 충돌(Collision)이 발생할 경우 이를 해결하기 위해 개방 해싱과 폐쇄 해싱이라는 두 가지 주요 방법이 사용됩니다.

1. 개방 해싱 (Open Hashing)

개방 해싱은 체이닝(Chaining) 기법이라고도 불리며, 충돌이 발생했을 때 해시 테이블 외부의 추가적인 공간을 활용해 문제를 해결합니다.

특징

• 충돌이 발생한 경우, 동일한 해시 주소에 해당하는 데이터를 연결 리스트(Linked List) 형태로 저장.
• 하나의 슬롯에 여러 데이터가 저장될 수 있음.

장점

• 해시 테이블의 크기와 무관하게 데이터를 저장할 수 있어 확장성이 높음.
• 삭제 작업이 간단하며, 데이터를 삭제해도 다른 데이터에 영향을 미치지 않음.

단점

• 추가적인 메모리 공간(연결 리스트)을 사용해야 하므로 메모리 효율이 떨어질 수 있음.
• 충돌이 많이 발생하면 연결 리스트가 길어져 검색 속도가 느려질 수 있음 (O(n)O(n)까지 증가 가능).

예시

• Python의 dict나 Java의 HashMap에서 기본적으로 체이닝 방식이 사용됨.

2. 폐쇄 해싱 (Closed Hashing)

폐쇄 해싱은 **오픈 주소법(Open Addressing)**이라고도 하며, 충돌이 발생했을 때 해시 테이블 내에서 빈 슬롯을 찾아 데이터를 저장합니다.

충돌 해결 방식

1. 선형 탐사(Linear Probing): 충돌 발생 시, 한 칸씩 순차적으로 이동하며 빈 슬롯을 찾음.
2. 제곱 탐사(Quadratic Probing): 이동 간격을 제곱수로 증가시키며 빈 슬롯을 찾음.
3. 이중 해싱(Double Hashing): 두 개의 서로 다른 해시 함수를 사용해 새로운 슬롯을 계산.
4. 랜덤 탐사(Random Probing): 임의의 규칙에 따라 빈 슬롯을 탐색.

특징

• 모든 데이터는 반드시 해시 테이블 내부에 저장되며, 외부 메모리를 사용하지 않음.
• 삭제 시에는 "삭제된 자리임"을 표시하는 특별한 마커를 남겨야 함(deleted 상태).

장점

• 추가적인 메모리 공간 없이 해시 테이블 내에서만 충돌을 해결하므로 메모리 효율이 높음.
• 데이터가 적재된 위치를 바로 알 수 있어 검색 속도가 일정하게 유지됨 (O(1)O(1)).

단점

• 충돌이 많아질수록 빈 슬롯 탐색 시간이 길어질 수 있음.
• 탐사 과정에서 클러스터링(Clustering) 현상이 발생할 가능성이 있음(특히 선형 탐사).

https://hyunah-home.tistory.com/entry/%ED%95%B4%EC%8B%B1-%EC%98%A4%EB%B2%84%ED%94%8C%EB%A1%9C%EC%9A%B0-%ED%95%B4%EA%B2%B0-%EA%B0%9C%EB%B0%A9%EC%A3%BC%EC%86%8C%EB%B2%95open-addressing%EA%B3%BC-%EC%9E%AC%ED%95%B4%EC%8B%B1

해싱 오버플로우 해결법; 개방주소법과 재해싱, 체이닝

https://heung-bae-lee.github.io/2020/04/30/data_structure_05/

내가 정리하는 자료구조 04 - 해쉬 테이블

https://ttl-blog.tistory.com/716