모두의 알고리즘 : MISSION 4-2(선형검색/이진검색/이진탐색트리/AVL트리/B트리)

모두의 알고리즘 with 자바스크립트에 담긴 내용을 기초로 하여 적는 글.

<모두의 알고리즘  with 자바스크립트 : MISSION 4-2>

검색 알고리즘을 알아보자

1. 선형 검색(linear search)
2. 이진 검색(binary search)

선형 검색, 리니어 서치(linear search)는 여러 데이터에서 찾으려는 데이터가 나올 때까지 처음부터 차례대로 검색하는 알고리즘이다. [1박 2일]의 시그니처 게임인 까나리 액젓 복불복 게임을 떠올려보자.
선형 검색은 1번부터 6번까지 모두 마셔보며 하나의 아메리카노를 찾는 알고리즘 방식이다. 1번이 아메리카노일 경우 한 번에 아메리카노를 고를 것이지만 6번이 아메리카노일 경우 5잔의 까나리 액젓을 다 마셔봐야 할 것이다. 선형 검색의 문제는 여기에 있다. 컵이 1000잔으로 늘어난 경우 && 1000번째 잔에 아메리카노가 들어있을 경우 999잔의 까나리 액젓을 다 마시기까지 너무 오랜 시간이 걸린다는 것이다. 알고리즘을 실행한 멤버는 더 이상 버티지 못하고 응급실에 실려갈지도 모른다!

이진 검색, 바이너리 서치(binary search)는 검색 기준을 반으로 나눠 원하는 데이터를 찾을 때까지 계속 검색하는 방식이다. 무한도전 와이키키 브라더스 편에서 나왔던 게임인 '업 앤 다운'이 이진 검색이 적용된 게임이다.
하와이행 티켓배 게임에 탈락한 무한도전 멤버들은 최후의 1인 멤버도 탈락시키기 위해ㅋㅋ 그 멤버가 생각한 1부터 100 사이의 숫자를 맞춰야 했다. 가장 먼저 50보다 크거나 작은지, 작으면 25보다 크거나 작은지 크면 75보다 크거나 작은지…를 질문하여 숫자를 추측했다. 탈락 멤버들은 숫자를 맞추지 못했고 최후의 1인 멤버는 하와이행 티켓을 거머쥔 에피소드지만 이건 횟수 제한 때문에 맞추지 못한 것이고 보통 대소 관계가 정의된 데이터는 모두 이진 검색으로 검색이 가능하다.

자료구조를 알아보자

위에서 설명한 검색 알고리즘도 처리를 하려면 데이터를 저장하는 방법도 중요하다. 데이터를 어떻게 저장했는지에 따라 처리 효율성이 달라지기 때문이다. 이러한 데이터의 저장형식을 자료구조라고 한다. 자료를 효율적으로 저장하기 위해서는 다른 자료 구조를 사용하는 것이 좋을 때도 있다. 그래서 소개하는 것이 트리 구조다.
트리 구조는 말그대로 나무와 같다. 트리 구조를 구성하는 모든 것들을 노드라고 하고, 부모 노드가 없는 가장 상위의 노드를 루트노드 / 자식 노드가 없는 가장 하위의 노드를 리프노드라고 부른다. 이 노드들은 모두 선으로 연결된다. 이 선을 엣지라고 하고, 가장 상위의 루트노트부터 가장 하위의 리프노드까지의 계층을 트리높이 혹은 깊이라 칭한다. 결과적으로 트리 구조는 루트 노드에서 여러 개의 엣지를 거친 후 리프 노드에 도달한다.

노드의 갯수에 따라 달라지는 트리의 종류

노드 2개를 가지는 트리를 이진트리라고 부르며, 노드 3개 이상을 가지는 트리를 다중 트리(노드 3개 이상) 혹은 N항 트리(노드 N개)라고 한다.

다양한 트리

1. 균형 트리는 루트 노드에서 리프 노드까지의 높이가 일정하도록 만들어진 트리구조를 말한다.
2. 이진 탐색 트리는 이진 트리중에서 왼쪽 자식 노드의 값이 부모 노드보다 작고 오른쪽 자식 노드의 값이 부모 노드보다 크게 구성된 트리 구조를 가르킨다. 왼쪽은 효자 오른쪽은 불효자... 라고 생각하면 되는 건가.. 무튼 그렇다!
3. AVL 트리는 데이터가 추가되었을 때 스스로 왔다리- 갔다리- 하는 능력(트리 회전)이 있는 트리며 한 노드를 중심으로 좌우 부분 트리의 높이 차가 1 이하인 이진 탐색 트리이기도 하다. 데이터 추가 시 스스로 조정을 한다니.. 얼마나 똑똑한 트리인가!

다중 트리

B 트리
는 다중 트리면서 균형 트리 구조를 가졌다. 즉, 새로운 데이터가 들어와도 균형을 유지하는데, 트리 회전을 하는 AVL 트리와는 조금 다른 방법으로 균형을 유지한다.

②,③ 과정에서 추가된 데이터는 비어있는 노드에 저장한다. ④ 과정에서는 노드가 가득차게 되고, 중심값인 13을 저장하는 새로운 노드가 만들어지고, 그 밖의 데이터는 13과의 크기를 비교해서 좌우의 자식 노드에 나누어 저장한다. ⑤ 과정에서는 데이터를 알맞는 자리에 저장한다. ⑥ 과정에서는 오른쪽의 자식 노드가 가득 찼으므로 중심 값 27을 부모 노드의 비어 있는 장소에 저장한다. 또한 새로운 자식 노드를 만들어 중심 값을 기준으로 크기를 비교해 나누어 저장한다.