[방송대 알고리즘]탐색 알고리즘

탐색의 개념

여러 데이터 중에서 원하는 값을 가진 데이터를 찾는 것

데이터 형태 → 리스트, 트리, 그래프 등

순차탐색

리스트 형태로 주어진 원소들을 처음부터 하나씩 차례대로 비교하면서 원하는 값을 가진 원소를 찾는 방법

배열의 연산

삽입 연산

n번째 인덱스에 내가 삽입하고 싶은 원소를 추가하고 배열의 크기를 1 증가시킴

삭제 연산

n번째 인덱스의 원소를 삭제하고, 마지막 원소를 삭제한 인덱스에 대입한 후 배열의 크기를 1 감소시킴

연결리스트의 연산

삽입 연산

원하는 데이터를 추가하고 포인터를 연결함

삭제 연산

원하는 데이터를 삭제하고 삭제된 앞 노드와 뒤 노드의 포인터를 연결함

성능분석

탐색 실패의 경우 → 항상 n번 비교

탐색 성공의 경우 → 최소 1번 ~ 최대 n번 비교

→ 탐색의 성능은 O(n)

삽입: O(1)

삭제: O(n) → 삭제할 데이터에 대한 탐색이 필요

특징

모든 리스트에 적용 가능

→ 원소가 무순서로 연속해서 저장된 비정렬 데이터 탐색에 적합

데이터가 큰 경우에는 부적합

→ 탐색과 삭제에 O(n)

이진 탐색

정렬된 배열 형태로 주어진 원소들을 절반씩 줄여가면서 원하는 값을 가진 원소를 찾는 방법

→ 분할정복 방법

탐색방법

• 배열의 가운데 원소와 탐색키 x를 비교
• 같다면 탐색 성공
• 다르다면 왼쪽이나 오른쪽 원소들을 대상으로 탐색 반복
• 연결 리스트 구조에서는 이진 탐색 자체가 불가능

초기화 알고리즘

이진탐색을 위해 배열은 정렬되어 있어야됨

정렬되지 않은 경우 정렬 수행

→ O(nlogn)

삽입 알고리즘

삽입할 위치를 찾는 방법

• 탐색이 실패한 지점(Left가 가리키는 부분)에 원소를 삽입
• 삽입될 위치부어 모든 배열의 인덱스를 한칸씩 뒤로 미룸
• 배열의 크기를 1 증가
• O(n)

삭제 알고리즘

• 삭제할 위치를 찾고 삭제한 뒤 인덱스들을 앞으로 한칸씩 당겨옴
• O(n)

성능 분석

• 탐색: O(logn)
• 초기화: O(nlogn)
• 삽입, 삭제: O(n)

특징

• 정렬된 배열에 대해서만 적용 가능
• 삽입과 삭제가 빈번한 경우에는 부적합

이진 탐색 트리

• 삽깁과 삭제를 더욱 효율적으로 하기 위핸 탐색 트리
• 입력을 트리 형태로 유지함
• 이진 트리
• 각 노드의 왼쪽 서브트리에 있는 모든 키값은 그 노드의 키값보다 작다
• 각 노드의 오른쪽 서브트리에 있는 모든 키값은 그 노드의 키값보다 크다
• 이진 탐색트리는 2개의 포인터를 가진 node struct를 통해서 구현

탐색 알고리즘

• 루트 노드부터 탐색
• 현재 키 값이 목표값과 같으면 성공
• 목표값이 현재 키 값보다 크면 오른쪽 서브트리 탐색
• 목표값이 현재 키 값보다 작으면 왼쪽 서브트리 탐색
• 리프노드까지 탐색하지 못하면 탐색 실패

삽입 알고리즘

• 한 이진 탐색 트리에 같은 값이 두개 있지 못함
• 현재 이진 탐색 트리에 삽입할 값이 있는지 탐색
• 없는경우 노드를 새로 생성하고 탐색에 실패한 지점에 삽입

삭제 연산

후속자 노드: 어떤 노드의 바로 다음 키값을 갖는 노드

1. 자식이 없는 경우

• 삭제할 노드를 탐색 후 삭제

2. 자식이 1개인 경우

• 자식 노드를 삭제되는 노드의 위치로 올리면서 서브트리 전체도 따라 올린다.

3. 자식이 2개인 경우

• 삭제되는 노드의 후속자 노드를 삭제되는 노드의 위치로 올리고
• 후속자 노드를 삭제되는 노드로 취급하여 자식노드의 개수에 따라 다시 처리

성능 분석

탐색, 삽입, 삭제의 시간 복잡도

키값을 비교하는 횟수에 비례 → 이진 트리의 높이가 h라면 O(h)

• 최소 높이: log n, 리프 노드를 제외하고 모든 노드의 차수가 2인 경우
• 최대 높이: n, 리프 노드를 제외하고 모든 노드의 차수가 1인 경우(경사 이진 트리)

특징

삽입,삭제 연산 시 기존 노드의 이동이 거의 발생하지 않음

원소의 삽입, 삭제에 따라 경사 트리 형태가 될 수 있음

→ 균형트리: 흑적 트리, B-트리

흑적트리

• 이진 탐색 트리, 균형 탐색 트리

1. 모든 노드는 흑색이거나 적색이다
2. 루트 노드와 리프 노드는 흑색이다.

• 모든 리프 노드는 Null 노드이다.

1. 적색 노드의 부모는 흑색이다.

• 적색 노드가 연달아 나타날 수 없다

1. 임의의 노드로부터 리프 노드까지의 경로 상에는 동일한 개수의 흑색 노드가 존재한다.

• 루트부터 리프까지의 경로에는 흑색 노드의 갯수가 더 많음
• 루트부터 어떤 리프까지의 흑색 노드의 개수는 같음

→ 루트에서 리프까지의 경로의 길이는 2배 이상 차이가 생길 수 없음

노드의 구조

• left
• color
• key
• right
• parent
• sibling

탐색 연산

• 이진 탐색 트리에서의 탐색 방법과 동일

삽입 연산

• 탐색이 실패한 Null 노드에 적색 노드를 추가, 두 자식 노드를 Null로 만듦
• 삽입 시 흑적트리의 조건에 맞게 규칙을 적용해야함

삽입 연산의 적용 규칙

1. 부모 노드의 형제 노드가 적색인 경우 → 부모 노드, 부모 노드의 형제 노드, 부모 노드의 부모 노드의 색깔을 모두 변경
2. 부모 노드의 형제 노드가 흑색이고, 현재 노드의 키값이 부모 노드와 부모 노드의 부모 노드의 키값의 사이인 경우 → 현재 노드와 부모 노드를 회전시킴
3. 부모 노드의 형제 노드가 흑색이고, 현재 노드의 키값보다 부모 노드와 부모 노드의 부모 노드의 키값이 큰(또는 작은) 경우 → 부모 노드와 부모 노드의 부모 노드를 회전시키고 색깔을 변경

성능 분석

• 탐색 시간: O(logn)
• 삽입,삭제 시간: O(logn)

특징

• 사실상 이진 탐색 트리
• 탐색 연산은 이진 탐색 트리와 동일
• 삽입 연산은 회전, 색깔 변경과 같은 추가 연산이 필요

2-3-4 트리를 이진 탐색 트리로 표현한 것

B-트리

• 균형 탐색 트리

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

노드 구조

• num
• leaf
• child[n+1], key[n]
• parent

탐색 연산

• 루트 노드부터 시작하여 키 값을 비교
• 이진 탐색 트리와 유사

삽입 연산

• 루트 노드에서부터 탐색을 수행하여 리프 노드에도 존재하지 않으며 해당 노드에 추가

노드 분할

트리의 높이를 맞추기 위하여 노드 분할을 수행

• 삽입을 위한 탐색 과정에서 (2t-1)개의 키를 갖는 노드를 만나면, 이 노드를 (t-1)개의 키를 갖는 두 개의 노드로 분할
• 삽입으로 인해 노드의 키의 개수가 2t개가 되는 것을 방지

t번째 키를 부모 노드로 이동, t를 기준으로 왼쪽, 오른쪽 키들이 각각 노드로 분할됨

루트 노드인 경우 트리의 높이가 증가함

삽입 과정중에 만나는 모든 노드에 분할 과정을 수행

성능 분석

트리의 높이 h, 각 노드에서의 키의 위치를 찾는 시간O(t) → O(th)

트리의 높이 → O(log_t n)

각 노드에서의 키 관리에 흑적 트리를 이용하면 O(t) → O(logt)

결론: O(logt * log_t n) → O(logn)

특징

• 내부 탐색과 외부 탐색에 모두 활용
• 내부 탐색의 경우 → t=2 또는 3으로 지정 → t = 2 이면 2-3-4 트리
• 외부 탐색의 경우 → t를 충분히 크게 지정 → 한 노드의 크기가 디스크의 한 블록에 저 장되도록

해싱

탐색 키 값을 기반으로 데이터의 저장 위치를 직접 계산

→ 상수 시간 내에 데이터의 탐색, 삽입, 삭제 가능

• 해시 함수를 통해 키값을 테이블의 주소로 변형시킴
• 상대적으로 키의 집합이 해시 테이블의 크기보다 큼 → 충돌은 어차피 발생함, 이를 해결하는 방법이 중요
• 가능하면 충돌이 적게 발생하는 해시 함수를 이용하는 것이 좋음

해시 함수

• 키값을 해시 테이블 주소로 변환하는 함수
• 제산 잔여법, 비닝, 중간 제곱법, 문자열을 위한 함수 등

제산 잔여법

K: 키값, M: 테이블의 크기

h(K) = K mod M

M의 선택에 주의해야 함

M=2^r이면 h(K)는 하위 r비트의 값이 됨

→ 키값을 전체 비트를 주소 계산에 활용하지 못함

M은 2의 멱수와 상당한 차이가 있는 소수로 선택

비닝

U: 키 값의 범위

• U를 단순히 M등분하여 각 등분을 각 슬롯으로 해시
• 상위 비트의 분포가 고르지 못하면 몇 개의 슬롯에 집중되는 문제

중간 제곱법

h(K) = (K^2/2^m) mod 2^r

• 대부분의 비트가 결과 생성에 기여
• 상위, 하위 자리의 분포에 의해 지배적인 영향을 받지 않음

문자열을 위한 해시 함수

각 아스키 코드를 각 더해서 사용할 수도 있음

• M << sum일 때 유용
• 짧은 문자열에 대해서는 비효과적
• 문자열에서 문자의 출현 순서에 무관

각 자리수에 가중치를 곱해줄 수도 있음

충돌 해결 방법

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

개방 해싱(연쇄법)

• 충돌된 데이터를 테이블 밖의 별도의 장소에 저장-관리

폐쇄 해싱(개방 주소법)

• 테이블 내의 다른 슬롯에 충돌된 데이터를 저장-관리
• 버킷 해싱, 선형 탐사, 이차 탐사, 이중 해싱

개방 해싱

• 테이블의 각 슬롯을 연결 리스트의 헤더로 사용
• 충돌 발생시 해당 연결 리스트에 노드 추가
• 해시 테이블과 연결 리스트가 주기억장치 내에 유지될 때 적합한 방법

버킷 해싱

• 폐쇠 해싱의 종류
• 슬롯을 버킷 단위로 관리
• 버킷이 꽉 찬 경우 오버플로 버킷을 사용
• 디스크에 저장된 해시 테이블을 구현하는 데 적합

선형 탐사

탐사 순서

• 어떤 키 K에 대하서 탐사되는 슬롯의 순서열
• p(k,i) → i번 충돌이 발생했을 때 찾아가는 슬롯
• 이 탐사 순서를 계산하는 방법에 따라 성능의 차이가 발생
• 선형 탐사, 이차 탐사, 이중 해싱

선형 탐사

• p(k, i) = (h(K)+i) mod M
• 빈 슬롯을 찾을 때까지 테이블의 바로 다음 슬롯으로 순차적으로 이동
• 가장 간단하지만 최악의 방법
• 모든 슬롯이 새로운 데이터를 삽입할 후보가 됨
• 1차 클러스터링 발생
• 데이터들이 연속된 위치를 점유하여 클러스터를 형성하고 이것이 점점 커지는 현상

이차 탐사

• p(k,i) = (h(k) + ci^2 + ci + c) mod M
• 서로 다른 홈 위치를 갖는 두 키는 서로 다른 탐사 순서를 가짐
• 모든 슬롯이 탐사 순서에 사용되지 않음 ex: p(k,0) = 2 라면 슬롯 1,2,3,6,7,8만 탐사 가능
• 탐사 함수의와 테이블 크기가 적절히 조합되면 많은 슬롯의 방 문이 가능
• 2차 클러스터링 발생
• 해시 함수가 특정 홈 위치에 대한 클러스터를 만드는 현상
• 서로 다른 두 키의 홈 위치가 동일하면 전체 탐사 순서가 동일

이중 해싱

• p(k,i) = (h(k_1) + ih(k_2)) mod M
• 탐사 순서를 원래의 키값을 이용하여 계산
• 1차, 2차 클러스터링 문제 해결
• 서로 다른 두 키의 홈 위치가 동일해도 서로 다른 탐사 순서를 가짐

좋은 이중 해싱

• 탐사 순서의 모든 상수가 테이블 크기 M과 서로소가 되어야 함

삭제 연산

데이터 삭제가 차후의 탐색을 방해하지 않아야 한다

• 단순히 빈 슬롯으로 두면 탐색이 해상 슬롯에서 종료 → 그 이후의 레코드는 고립됨

삭제로 인해서 해시 테이블의 위치에서 사용할 수 없는 곳을 만들지 않아야 한다

비석

삭제된 데이터의 위치에 ‘비석’이라는 특별한 표시를 하는 방법

• 탐색: 비석을 무시하고 탐색을 계속 진행
• 삽입: 비석이 표시된 위치를 빈 위치로 간주하여 새 데이터를 삽입
• 비석의 개수가 증가할수록 평균 탐색 거리가 증가하는 문제