[알고리즘] 탐색/검색에 관하여

순차탐색

- 데이터집합의 처음부터 끝까지 차례대로 모든 요소를 비교해서 데이터를 찾는 탐색 알고리즘.

- 한쪽 방향으로만 탐색을 수행한다고해서 선형 탐색이라고 부르기도 함.

- 효율이 좋진 않지만, 높은 성능을 필요로 하지 않거나, 데이터집합의 크기가 작을 때 유용

 

 

자기구성 순차탐색

- 자주 찾는, 자주 사용하는 항목들을 다른 항목들보다 우선하여 접근하게 가까운곳에 배치한다.

- 자주 사용되는 항목을 어떻게 선별하는가에 대한 세가지 방법

1. 전진 이동법(Move To Front) : 한번 탐색되면 무조건 가장 앞에 위치 시킴.

2. 전위법(Transpose) : 한번 탐색되면 앞칸으로 한칸씩 이동. 자주 탐색되면 앞으로 몰림

3. 빈도 계수법(Frequency Count) : 각 요소들이 탐색되는 횟수를 별도의 공간으로 저장. 횟수가 높은 순으로 데이터 집합 재구성함.

 

 

이진탐색

조건 : 

- 오름차순 혹은 내림차순으로 정렬되어 있어야함. 

 

10개의 나열되어 있는 숫자는 찾는 값을 A라고 한다면

10개 중 절반인 5번째 값과 A를 비교하고 A보다 작으면 1~4개의 값중 또 절반 2번값과 비교하여 찾아가는 방식

크다면 6~10번의 숫자들 중 가운데와 비교하는 식 

 

 

 

시간복잡도 : 

 

 

 

이진탐색트리

이진탐색트리는 이진탐색을 기반으로 되어있는 트리이다.

- 오른쪽 서브트리들이 루트의 키보다 크다.

- 왼쪽 서브트리들이 루트의 키보다 작다

출처 : https://blog.hexabrain.net/248

문제점 : 자칫하여 값이 잘못들어가게 되면 

이런식으로 기형적으로 생겨날수 있다.

 

레드블랙트리

위의 이진탐색트리의 단점들을 보완하기에 유용하다.

 

레드블랙트리의 규칙

1. 모든 노드는 빨간색 아니면 검은색이다.

2. 루트노드는 검은색이다.

3. 잎노드는 검은색이다.

4. 빨간 노드의 자식들은 모두 검은색이다. 하지만, 검은색 노드의 자식이 빨간색일 필요는 없다.

5. 루트노드에서 모든 잎 노드 사이에 있는 검은색 노드의 수는 모두 동일.

 

 

출처 : https://velog.io/@main_door/%EB%A0%88%EB%93%9C%EB%B8%94%EB%9E%99%ED%8A%B8%EB%A6%AC