탐색

탐색!

데이터를 찾고자 한다!!

* 순차 탐색

- 처음부터 끝까지 차례대로 모든 요소 비교

- 처음부터 끝으로 한 방향으로만 탐색하므로 선형 탐색

- 장점 : 구현이 간단해 버그의 가능성이 적음 / 정렬되지 않은 데이터 중 원하는 데이터를 찾을 수 있는 방법

   => 높은 성능이 필요없거나 데이터 집합의 크기가 작은 곳에서 사용

* 자기 구성 순차 탐색

- 자주 사용되는 항목을 데이터 집합의 앞쪽에 배치해 순차 탐색의 검색 효율을 증가시키는 방법

- 전진 이동법 : 한번 탐색되면 그 항목을 데이터 집합의 가장 앞(링크드 리스트의 Head)으로 위치

- 전위법 : 탐색된 항목을 바로 이전 항목과 교환

- 빈도 계수법 : 탐색된 횟수를 별도의 공간에 저장, 탐색된 횟수의 높은 순으로 집합을 재구성

* 이진 탐색

- 탐색 범위를 반으로 줄여나가는 방식

- 수행 과정

1. 데이터 집합 중 중앙의 요소 선택

2. 중앙 요소의 값과 찾고자 하는 값을 비교

3. 찾으려는 값이 중앙 요소보다 작으면 중앙을 기준으로 왼편에서, 크면 오른편에서 다시 검색 수행

- 이진 탐색의 반복 횟수는 long_2n

C 표준 라이브러리 이진 탐색 함수 => bsearch()

void *bsearch(

const void *key,                //찾고자 하는 목표 값 데이터의 주소

const void *base,                // 데이터 집합 배열의 주소

size_t num,                         // 데이터 요소의 개수

size_t width,                        // 한 데이터 요소의 크기

int (__cdecl *compare) (const void *, cont void *)        // 비교 함수에 대한 포인터

);

* 이진 탐색 트리

- 이진 탐색을 위한 이진 트리ㅋㅋ

- 이진 탐색은 데이터 집합이 배열인 경우에만 사용 가능

   => 사전에 정의된 크기의 데이터 집합에 대해서만 사용 가능 => 그래서 이진 탐색 트리 사용!

- 규칙

왼쪽 자식 노드는 나보다 작고, 오른쪽 자식 노드는 나보다 크다!

- 불규칙한 이진 탐색 트리의 성장은 검색 효율을 떨어뜨림

=> 그래서 레드 블랙 트리 등장!!

* 레드 블랙 트리

- 이진 트리의 균형을 유지하기 위한 트리

노드

typedef struct tagRBTNode

{

struct tagRBTNode* Parent;

struct tagRBTNode* Left;

struct tagRBTNode* Right;

enum { RED, BLACK } Color;

ElementType Data;

} RBTNode;

- 레드 블랙의 규칙

1. 모든 노드는 빨간색 or 검은색

2. 루트 노드는 검은색

3. 잎 노드는 검은색

4. 빨간 노드의 자식은 검은색! 검은색 노드의 자식은 상관 음슴

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

으잉 어려워잉@_@

출처 : 뇌를 자극하는 알고리즘 (한빛미디어)