탐색 알고리즘 {순차 탐색, 이진 탐색, 이진 탐색 트리, 레드 블랙 트리}

탐색 알고리즘이란 목적에 맞는 데이터를 찾아내기 위한 알고리즘이다.

 

순차 탐색: 처음부터 끝까지 차례대로 모든 요소를 비교해 원하는 데이터를 찾는 탐색 알고리즘으로,

어느 한쪽 방향으로만 탐색할 수 있어 선형 탐색이라고 부르기도 한다. 성능은 좋지 않지만 정렬되지 않은 데이터에서

원하는 항목을 찾을 수 있는 방법이며 구현이 간단해 버그를 만들 가능성이 적다는 장점이 있다.

 

자기 구성법: 순차탐색의 검색 효율을 끌어올리는 방법으로 자주 사용되는 항목을 데이터 앞쪽에 배치하는 방법.

자주 사용되는 항목을 선별하는 방법에 따라 3가지로 나뉜다.

 

1. 전진 이동법 - 탐색된 항목을 데이터의 가장 앞으로 옮기는 방법. 한 번 탐색된 항목이 다음에 또다시 검색될 가능성이 높은

데이터에 한해 사용해야 함.

 

2. 전위법 - 전위란 위치를 바꾼다는 뜻으로 탐색된 항목을 바로 이전 항목과 교환하는 방식으로 자주 탐색된 항목을 조금씩 앞으로 옮긴다. 자주 탐색되는 항목들이 데이터 앞쪽으로 모이지만 처음부터 정해진 데이터 요소의 위치에 영향을 받기 때문에  반드시 앞에 있는 데이터들이 선택을 많이 받았다고 보장할 수 없다.

 

3. 빈도 계수법 - 데이터 내 각 요소가 탐색된 횟수를 별도의 공간에 저장해 두고 탐색된 횟수가 높은 순으로 데이터를 재구성하는

전략. 계수 결과를 저장하는 별도 공간을 유지해야 하고 데이터 재배치에 비용이 많이 소요되는 단점이 있음.

 

이진 탐색: 탐색 범위를 1/2씩 줄여나가는 방식의 정렬된 데이터에 사용 가능한 고속 탐색 알고리즘. 

수행과정

1) 데이터의 중앙 요소 선정. 2) 중앙 요소 값과 찾고자 하는 목푯값 비교. 3) 목표수 값이 중앙 요소보다 작으면 왼쪽, 크면 오른쪽에 

대해 이진 탐색을 새로 수행. 4) 찾고자 하는 값을 찾을 때까지 1~3 반복.

 

이진 탐색의 성능: 데이터의 크기를 n, 반복 횟수를 x라고 할 때 최대 반복 횟수는 x = log2n이다. 그전에 목푯값을 찾으면 탐색 종료.

데이터의 크기가 아무리 커져도 탐색 소요 시간은 아주 미미하게 증가한다.

 

 

bsearch() 함수

 

bsearch() 함수: C언어 표준 라이브러리에서 이진 탐색을 구현한 함수.

Key는 목푯값 데이터의 주소, Base는 데이터 내 배열의 주소, Num은 데이터의 크기, SizeOfElements는 한 데이터 요소의 크기,

마지막 매개변수는 비교를 수행한 결과를 반환하는 함수에 대한 포인터.

 

이진 탐색 트리: 이진 탐색을 위한 이진트리. 이진 탐색이 배열에만 사용 가능한 알고리즘이기에 필요, 이진 탐색을 사용하려면 데이터의 처음과 끝을 알아야 하고 중앙요소를 계산할 수 있어야 하고 계산된 중앙 요소에 즉시 접근할 수 있어야 하기 때문. 이에 동적으로 노드를 추가하거나 제거할 수 있으면서 이진 탐색 알고리즘도 사용할 수 있는 방법이 이진 탐색 트리이다.

 

규칙: 왼쪽 자식 노드는 나보다 작고 오른쪽 자식 노드는 나보다 커다란 조건을 따름. 트리의 각 노드가 이진 탐색 노드의 조건을 갖추면 이진 탐색 트리다. 이진 탐색 트리도 이진 탐색이 가능한 상태로 정렬되어 있어야 사용이 가능하다. 

 

이진 트리에서의 이진 탐색

 

이진트리에서의 이진 탐색:  각 노드는 중앙 요소이다. 중앙 요소에서 좌우의 대소 비교를 반복한다.

 

노드 삽입 연산

 

노드 삽입 연산: 새 노드가 삽입될 곳을 찾는 게 핵심. 이진 탐색으로 새 노드를 연결할 부모 노드를 찾아 그곳에 노드를 내려놓으면 된다.

 

자료구조에서는 무언가를 만드는 일보다 없애는 일이 대체로 어렵다. 없애고 난 후 뒤처리가 복잡.

 

노드 삭제 연산

 

노드 삭제 연산: 삭제할 노드를 찾고 트리에서 떼어냄. 잎 노드라면 부모 노드에서 자식 노드의 포인터를 NULL로 만들고 삭제한 노드의 주소를 반환하면 된다. 자식이 있는 경우에는 1) 양 쪽 자식을 모두 갖고 있는 경우. 2) 어느 한쪽 자식만 갖고 있는 경우.

중 2번의 경우에는 삭제할 노드의 자식을 부모에 연결시키면 되고 1번의 경우에는 삭제된 노드의 오른쪽 하위 트리에서 가장 작은 값을 가진 노드 (최솟값 노드)를 삭제된 노드의 위치에 옮겨 놓으면 된다. 최솟값 노드에 자식이 있다면 (오른쪽 자식만 존재할 수 있음) 오른쪽 자식을 원래 부모 노드에게 연결하면 된다.

이진 탐색 트리의 문제점

 

이진 탐색 트리의 문제점: 예시와 같이 기형적으로 성장 시 검색 효율이 극단적으로 떨어진다. 

실제 데이터를 담는 경우 이 그림과 같이 성장할 가능성이 높다.

 

 

레드 블랙 트리: 노드를 빨간색 또는 검은색으로 표시, 노드의 색은 트리 전체의 균형을 유지할 수 있게 해주는 역할.

 

규칙

1. 모든 노드는 검은색 또는 빨간색이다.

2. 뿌리 노드는 검은색이다.

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

4. 빨간색 노드의 자식은 모두 검은색이다.(검은색 노드의 자식은 빨간색, 검은색 모두 가능)

5. 뿌리 노드와 모든 잎 노드 사이에 있는 검은색 노드의 수는 모두 동일하다. 

 

NIL 노드: 아무 데이터도 갖고 있지 않지만 색깔만 검은색인 더미 노드. 센티넬 노드라고 함. 레드 블랙 트리의 구현을 용이하게 하기 위해 사용한다. 원래 잎 노드에 NIL 노드를 양쪽 자식으로 두면 모든 잎 노드는 검은색이라는 규칙 3번을 항상 지킬 수 있기 때문. 

 

레드 블랙 트리의 연산:기본적으로 이진 탐색 트리와 비슷하나 연산 중 무너진 규칙을 바로 잡아주는 과정이 핵심이다.

레드 블랙 트리 회전

 

회전: 부모와 자식 노드의 위치를 서로 바꾸는 연산. 좌회전은 오른쪽 자식과 부모 위치를 교환, 우회전은 왼쪽 자식과 부모 위치를 교환.  이진트리 특성상 왼쪽 자식 노드는 부모보다 작고 오른쪽 자식은 부모보다 커야 한다. 이 때문에 그냥 회전시키면 안 되고

좌회전 시는 오른쪽 자식 노드의 왼쪽 자식 노드를 부모 노드의 오른쪽 자식으로 연결.

우회전 시는 왼쪽 자식 노드의 오른쪽 자식 노드를 부모 노드의 왼쪽 자식으로 연결.

노드 삽입 후 규칙 처리

 

노드 삽입: 새 노드를 삽입하면 이 노드를 빨간색으로 칠한 다음 NIL 노드를 이 노드의 양쪽 자식으로 연결해야 한다. 이때 삽입된 노드의 부모가 빨간색이면 문제 발생. 삼촌 노드(부모 노드의 형제 노드)의 색깔에 따라 3가지 경우로 나뉜다.

 

1) 삼촌 노드도 빨간색인 경우 - 부모와 삼촌 노드를 검은색으로, 할아버지 노드를 빨간색으로. 이후 할아버지 노드 기준으로 재검사

2) 삼촌이 검은색이며 새로 삽입한 노드가 부모 노드의 오른쪽 자식인 경우 - 부모 노드를 회전시켜서 3번 경우로 문제 유형 변경

3) 삼촌이 검은색이며 새로 삽입한 노드가 부모 왼쪽 자식인 경우 - 부모 노드를 검은색, 할아버지 노드를 빨간색으로 칠한 다음 할아버지 노드를 회전시킴.

 

노드 삭제 후 규칙 처리

 

노드 삭제: 빨간색 노드는 삭제 시 규칙에 영향을 주지 않음, 검은색 노드 삭제 시 균형 복구가 필요. 

검정 노드 삭제 시 자식이 빨간색 노드라면 자식을 검정으로 바꾸는 것으로 해결, 검정 노드의 자식이 NULL이거나 검은색 노드일 경우 이중 검정이 발생한다.

 

이중검정 발생 시 4가지 경우

 

1) 형제가 빨간색일 때 - 형제를 검은색, 부모를 빨간색으로 칠함. 부모를 기준으로 자식 노드 회전 => 2,3,4번 경우로 진입

2) 형제가 검은색이고 형제의 양쪽 자식이 모두 검은색일 때 - 형제를 빨간색으로 칠하고 이중 검정 중 하나를 부모 노드에게 넘김.

3) 형제가 검은색이고 형제의 왼쪽 자식은 빨간색, 오른쪽 자식은 검은색일 때 - 형제 노드를 빨간색으로 왼쪽 자식을 검은색으로 바꾸고 다음 형제 노드 기준 우회전

4) 형제는 검정, 오른쪽 자식은 빨간색인 경우 - 이중 검정 부모의 색을 형제 노드에 칠하고 부모 노드와 형제 노드의 오른쪽 자식 노드를 검은색으로 칠하고 부모 노드 기준 좌회전.