자료구조(11) 보간 탐색 트리

탐색은 데이터를 찾는 방법이다. 

탐색 1은(보간 탐색과 이진 탐색 트리) 트리의 뒷이야기에 해당합니다.

 

굳이 따지지면 탐색은 알고리즘보다 자료구조에 더 가까운 주제이다. 이유는 다음과 같다

"효율적인 탐색을 위해서 "어떻게 찾을까"만을 고민해서는 안된다. 그보다는 "효율적인 탐색을 위한 저장방법이 무엇일까"를 우선 고민해야 한다. 그리고 효율적인 탐색이 가능한 대표적인 저장방법은 '트리'이다. 때문에 탐색에 관한 이야기의 대부분은 트리의 연장선상에 놓여있다.

보간 탐색 (간단하게 설명)

이진 탐색처럼 값에 상관없이 그냥 중앙에서 탐색을 시작하지만, 보간 탐색은 그 값이 상대적으로 앞에 위치한다고 판단을 하면 앞쪽에서 탐색을 시작한다. 단번에 찾지 못하더라도 탐색의 위치가, 찾는 데이터와 가깝기 때문에 탐색대상을 줄이는 속도가 이진 탐색보다 뛰어나다

 

보간 탐색은 데이터의 값과 그 데이터가 저장된 위치의 인덱스 값이 비례한다고 가정한다.