[알고리즘]탐색/검색(순차, 자기 구성, 이진 탐색, 레드블랙트리)

탐색/검색이란

무엇인가를 찾는 의미이며 컴퓨터에서는 데이터를 찾는 의미

순차 탐색

맞는 짝이 나올 때까지 처음부터 차례대로 비교하는 방법

한쪽 방향으로 탐색을 수행한다고 하여 선형 탐색이라고 부르기도 함

'처음부터 끝까지 모든 데이터를 확인'하여 효율이 좋지 않은 방법

정렬 되지 않은 데이터에서는 원하는 데이터를 찾을 수 있는 유일한 방법

자기 구성 순차 탐색

특정 데이터를 선택 하고 해당 데이터를 자주 사용하는 항목, 즐겨찾기와 같은 기능에 사용 되는 방법

- 전진 이동법

- 전위법

- 빈도 계수법

전진 이동법

특정 데이터가 한번 탐색 되면 해당 데이터를 가장 처음으로 위치를 변경

ex) 3번 선택 시

1 2 3 4 5  :    3 1 2 4 5

    ↑

전위법

특정 데이터가 한번 탐색 되면 이전 데이터와 위치를 변경

ex) 3을 선택 시

1 2 3 4 5  :    1 3 2 4 5

    ↑

빈도 계수법

특정 필드 및 공간을 생성하여 탐색 된 숫자의 횟수를 저장하는 방법

이진 탐색

정렬 된 데이터에서 사용 할 수 있는 고속 탐색 알고리즘

탐색 범위를 1/2씩 줄여 나가는 방식

O(logn)

1. 데이터 집합에서 중앙 데이터를 선택합니다.

2. 중앙 데이터의 값과 찾고자 하는 값을 비교합니다.

3. 찾고자 하는 값보다 작으면 왼쪽으로, 크면 오른쪽으로 확인 작업을 반복합니다.

가운데 값을 찾습니다.

선택 된 값과 찾고자 하는 값을 비교 합니다.

작다면 왼쪽 편의 가운데 값을 선택합니다.

반복합니다.

1을 찾았습니다.

트리 형태

레드 블랙 트리

이진 탐색 트리에 대한 문제점을 해결하기 위한 방안

이진 탐색 트리의 트리가 균형을 갖추지 못하는 형태로 발전하면 성능 저하 되며 이를 해결 하기 위한 방안

이진 탐색 트리와 다른 점은 빨간색과 검은색으로 표시하는 점, 색 필드와 부모 필드가 추가

이진 탐색 트리의 탐색을 그대로 사용하고 삽입과 삭제의 문제를 규칙에 맞는 '후처리'로 균형을 유지

시물레이션 해보기

한쪽으로 치우친 균형적이지 않은 트리 형태

레드 블랙 트리의 균형을 유지하는 규칙

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

2. 루트 노드는 검은색입니다.

3. 말단(잎) 노드는 검은색입니다.

4. 빨간색 노드의 자식들은 모두 검은색입니다. 

단, 검은색 노드의 자식은 꼭 빨간색이지 않아도 됩니다.

5. 루트 노드에서 모든 말단(잎) 사이에 있는 검은색 노드의 수는 모두 동일합니다.

레드 블랙에서의 말단(잎) NIL

NIL은 이해를 돕기 위한 가상의 공간을 차지 않는 데이터 : 단말(잎)은 항상 검은색이라는 규칙을 항상 지킴

NIL 변수를 전역으로 선언하고 이를 같은 공간을 공유하는 더미 노드

레드 블랙 트리의 연산을 위한 '회전'

우회전 : 왼쪽 자식과 부모의 위치를 교환

좌회전 : 오른쪽 자식과 부모의 위치를 교환

레드 블랙 트리의 삽입

1. 이진 탐색 트리로 삽입 위치를 찾습니다.

2. 새로운 노드의 색을 빨간색으로 하고 삽입합니다.

3. NIL이고 색을 검은색으로 가진 자식 노드를 만들어 주고 '후처리'를 합니다.

5가지 규칙 중 4번 규칙만 위반하게 되는 상황 발생

부모가 빨간색이고 새로 추가한 자식도 빨간색인 상황은 4번 규칙을 위반하므로 이를 해결 하기 위한 '후처리'를 진행

레드 블랙 트리의 삽입의 '후처리'

3가지 경우가 발생

1. 삼촌(형제) 노드가 빨간색인 경우

2. 삼촌(형제) 노드가 검은색이고 새로 삽입한 노드가 부모 노드의 오른쪽 자식인 경우

3. 삼촌(형제) 노드가 검은색이고 새로 삽입한 노드가 부모 노드의 왼쪽 자식인 경우

2번과 3번의 경우 상반되는 상황이므로 둘 중 하나의 상황으로 변경하여 문제를 해결 해야 함

1. 삼촌(형제) 노드가 빨간색인 경우

삼촌(형제) 노드가 빨간색이면 부모와 삼촌(형제) 노드를 검은색으로 변경하고 할아버지 노드를 빨간색으로 변경

단, 할아버지 노드가 4번을 위반하는 상황이면 부모 노드가 검은색이거나 새로 삽입 한 노드가 루트여야 종료

2. 삼촌(형제) 노드가 검은색이고 새로 삽입한 노드가 부모 노드의 오른쪽 자식인 경우

부모 노드를 왼쪽으로 회전시켜 3번의 경우의 문제로 변경하여 문제를 해결 시도

3. 삼촌(형제) 노드가 검은색이고 새로 삽입한 노드가 부모 노드의 왼쪽 자식인 경우

부모 노드를 검은색으로, 할아버지 노드를 빨간색으로 변경하고 할아버지 노드를 우회전

레드 블랙 트리의 삭제

1. 이진 탐색 트리로 삭제 위치를 찾습니다.

2. 이진 탐색 트리에서 삭제 시 할아버지 노드와 자식 트리를 연결 했듯이 연결합니다.

3. 검은색 노드를 삭제 시 '후처리'를 합니다.

레드 블랙 트리의 '후처리'

빨간색일 경우에는 후처리를 하지 않아도 문제가 되지 않습니다.

검은색의 경우에만 후처리를 해야 합니다.

자식이 빨간색일 때 부모를 삭제하면 4,5번을 위반하게 됩니다.

부모 자리로 온 10번을 검은색으로 변경하면 4,5번을 보완 할 수 있습니다.

10번에게 더이상 자식이 없는 상태에서는 이정도 '후처리'만 해줘도 해결 할 수 있습니다.

문제는 자식과 조카가 함께 있는 경우입니다.

부모를 삭제하고 자식을 올려도 5번 규칙을 위반하게 됩니다. 

5번 위반이라는 문제를 쉽게 풀기 위해 이중 흑생이라는 문제를 풀기 위한 개념이 등장합니다.

5번 규칙은 지켰으나 1번 규칙을 위반하게 됩니다.

이중 흑색이라는 빨간색도 검은색도 아니게 됩니다.

1번 규칙을 지키기 위해서는 4가지 경우를 고려합니다.

(이중 흑색 노드가 부모 노드의 왼쪽 자식인 경우에 한함/ 오른쪽 자신인 경우 반대로(왼쪽/오른쪽) 변경)

1. 형제가 빨간색인 경우

2. 형제가 검은색이고

2-1. 형제의 양쪽 자식이 모두 검은색인 경우

2-2. 형제의 왼쪽 자식은 빨간색, 오른쪽 자식은 검은색인 경우

2-3. 형제의 오른쪽 자식이 빨간색인 경우

1. 형제가 빨간색인 경우

형제를 검은색으로, 부모를 빨간색으로 변경하고 부모를 기준으로 좌회전합니다.

형제 노드가 검은색으로 변경되었습니다.

2번 형제가 검은색이고~로 문제가 변경되었기 때문에 이후에는 2번의 경우에 따라 문제를 해결합니다.

부모를 삭제하고 이증 흑색으로 변경합니다. 규칙 1번 위반입니다.

부모 노드를 빨간색으로, 형제 노드를 검은색으로 변경합니다.

부모를 기준으로 좌회전하면 새로운 형제가 검은색이 됩니다.

현재 상태는 2-3입니다.

2-1. 형제가 검은색이고 형제의 양쪽 자식이 모두 검은색인 경우

형제 노드만 빨간색으로 변경하고 이중 흑색 노드가 가지고 있던 하나의 흑색을 부모 노드에게 전달합니다.

부모 노드도 형제에 따라 대처합니다.

부모 노드가 빨간색이면 검은색으로 변경합니다.

부모 노드가 검은색이면 루트에게 이중 흑색을 전달하거나 빨간색을때까지 반복합니다.

2-2. 형제가 검은색이고 형제의 왼쪽 자식은 빨간색, 오른쪽 자식은 검은색인 경우

형제 노드를 빨간색으로 변경하고 왼쪽 자식은 검은색으로 변경합니다.

그리고 형제 노드를 기준으로 우회전합니다.

이중 흑색은 그대로 남아 있는 상태고 현재 상태를 보면 '형제가 검은색이고 형제의 오른쪽 자식이 빨간색인 경우'로 변경 되었습니다. 2-3에서 이어 해결합니다.

2-3. 형제가 검은색이고 형제의 오른쪽 자식이 검은색인 경우

이중 흑색 노드의 부모 노드가 갖고 있는 색을 형제 노드에게 변경합니다.(부모:빨, 형제:검 -> 형제:빨)

부모 노드와 형제 노드의 오른족 자식 노드를 검은색으로 변경하고 부모 노드를 기준으로 좌회전합니다.

2-1과 같이 루트에게 이중 흑색을 전달 할 때까지 반복하거나 부모 노드가 빨간색이면 검은색으로 변경합니다.

소스는 많아서 깃허브에 올렸습니다.

레드 블랙 트리는 C 소스만 있습니다.