알고리즘 내용에서 검색 방법에 대한 내용을 공부해보았습니다.

아래는 오늘 공부한 내용을 요약한 노트입니다.

검색

자료집합에서 원하는 데이터를 찾아내는 것입니다.

검색 알고리즘의 구성

검색속도가 빨라야하며, 자료 집합에 새로운 데이터를 빨리 넣어야 합니다. 그리고 자료집합에서 자료를 빨리 뺄 수 있어야합니다.

종류

검색 키가 하나면 1차원 검색이며, 검색 키가 둘 이상이면 다차원 검색입니다.

또한 단일 키 검색과 범위 검색도 있습니다.

1차원 검색 알고리즘

• 순차 검색

• 이진 검색

• 보간 검색

• 이진트리 검색

• 해쉬

• 기수 검색

• b-트리

map 클래스

검색 알고리즘은 insert, remove, find의 공통이 있어서 class로 묶는게 좋습니다.

순차검색

무순서로 저장된 자료집합에서 검색하고자하는 키를 처음부터 순차적으로 찾아내는 방법입니다.

배열의 가장 뒤에 새로운 자료가 추가되며 처음부터 키를 찾고, 제거시는 메모리가 자동으로 이동되고 갯수가 감소됩니다.

이진검색

반드시 자료집합은 정렬되어 있어야하며, 키값과 중앙 값의 크기를 비교하여 값을 찾습니다.

보간검색

자료집합이 정렬된 선형 분포를 가지면서 이진법에 의해 중앙 값을 찾습니다.

이진트리 검색

이진트리를 이용한 검색방법으로서, 평균적으로 O(n)의 성능이 납니다.

상위 노드가 왼쪽 서브트리보다 크고, 오른쪽 노드보다 작아야합니다.

해쉬

키값을 양의 정수로 변환하는 것입니다.

해쉬 자료구조 : 자료를 해쉬함수의 결과 위치에 배치하는 방법입니다.

o(1)의 성능을 가지는 검색구조이며 해쉬 테이블의 크가가 중요합니다.

서로 다른 키의 해쉬 연산이 같을때 충돌이나며, 선형 탐사법과 연결법으로 해결할 수 있다고 합니다.

해쉬 함수

해쉬 함수는 인접키와 빈도가 높은 키 영역을 퍼트리고, 테이블의 크기는 소수로 하도록 권해집니다.

선형 탐사법

해쉬 연산이 같을때 해결하는 방법중 하나로서, 순차적으로 탐사하여 빈 곳을 찾아 해결합니다.

이중 해쉬 : 선형 탐사와 다르게 이차 해쉬 함수의 결과만큼 증가하며 빈곳을 찾아 해결합니다.

삽입 - 입력 자료의 해쉬 값에서 인덱스로 자료추가합니다.

삭제 - 삭제 자료를 테이블에서 찾은 뒤, DELETED 라고 표시합니다.

검색 - 입력자료의 해쉬 값에 해당하는 인덱스부터 순차적으로 검사합니다.

연결법

링크드리스트의 배열로 이루어진 해쉬테이블을 이용하여 충돌이 발생하면 해당 위치의 리스트에도 추가합니다.

삽입 - 해쉬 값의 인덱스에 있는 리스트에서 새로운 노드 추가

삭제 - 해쉬 값의 인덱스에 있는 리스트에서 해당 노드 삭제

검색 - 해쉬 값의 인덱스에 있는 리스트에서 순차 검색

기수 검색

기수트리 : 노드의 레벨에 해당하는 비트의 값에 따라 O은 왼쪽 하위로 1은 오른쪽 하위로 배치합니다.

삽입 - 레벨에 따른 비트 검사를 통해 리프로 이동하고 새로운 노드를 리프에 추가합니다.

검색 - 검색키의 비트 검사를 통해 노드를 탐색합니다.

삭제 - 이진검색 트리와 같습니다.

트리에서 노드는 정보 노드와 분기노드가 있습니다.

정보 노드 - 실제 데이터입니다.

분기 노드 - 빈 노드

정보노트는 항상 리프에 존재하며 모든 내부도는 분기노드입니다.

특성

자료의 입력 순서와 무관하며, 키의 중복이 허용되지 않습니다.

B-트리

이진트리 검색의 좌우 비균형의 비효율을 개선한 것입니다.

삽입과 삭제시 필요하면 스스로 균형을 유지합니다.

항상 O(LogN)의 성능을 냅니다.

하나의 노드에 여러자료가 배치되는 트리구조이며, 한 노드에 m개의 자료가 배치되면서 m차 b-tree가 됩니다.

각 노드는 정렬되어 있어야 하며, 노드 자료수가 n개이면 하위의 수가 n+1이여야 합니다. 그리고 최상위 노드는 적어도 2개 이상의 하위 노드를 가져야하며, 최상위 노드를 제외한 모든 노드는 적어도 m/2개의 자료를 가지고 있어야합니다.

외부노드로 가는 경로의 길이는 모두 같고, 입력 자료는 중복될 수 없다고 합니다.

레드-블랙 트리

이진트리로 2-3-4 트리의 밸런스 특성을 구현한 것입니다.

red와 black 노드 두가지가 있습니다.

특징 : 이진검색 트리와 동일하게 상위 노드는 왼쪽 서브트리보다 크고 오른쪽 서브트리보다 작습니다. 그리고, 최상의에서 리프로 가는 경로의 검정 노드의 수는 모두 같고 새로 삽입되는 노드는 리프에 위치하며 빨간 노드입니다.

기본 동작은 색변환,회전이 있습니다.

검색 - 이진검색 트리와 동일합니다.

삽입 - 색 승격 + 회전

삭제 - 색 좌천 + 회전

성능은 o(LogN)입니다.