검색트리 데이터의 저장과 검색은 자료구조와 알고리즘 분야에서 매우 중요하다. 수행시간에서 커다란 차이를 보이기 때문이다. 데이터의 저장과 검색을 효율적으로 하기 위해서는 적절한 자료구조 및 알고리즘의 사용을 필요로 한다는 사실은 자명하다. 만약 데이터가 들어오는 순서대로 배열에 저장한다고 가정해보자. 자료수가 n개일 때 수행시간은 다음과 같다. 새로운 자료 하나를 저장하는 시간은 Θ(1) 자료를 검색하는 시간은 Θ(n) 보다시피 검색에는 비효율적이다. 허나, 트리 모양 구조의 검색 트리에 저장한다면 어떨까? 저장과 검색, 둘 모두 Θ(log n)의 시간이 걸린다. 검색트리는 자식노드 갯수에 따라, 저장장소에 따라, 검색키에 포함된 필드수에 따라 분류된다. 다만 여기서는 언급하지 않겠다. 이진 검색트리 이..
