BST

Binary Search Tree (이진 탐색 트리) 이진 탐색 트리는 앞서서 배운 트리의 확장적인 형태라고 보면 편하다. 일반적인 이진 트리는 탐색의 기준이 없어서 특정 데이터를 찾으려면 모든 노드를 탐색해야한다. 하지만 이진 탐색 트리에서는 평균적으로 훨씬 빠른 시간에 탐색이 가능해진다. Binary Search (이진 탐색) 우선 이진 탐색과 이진 탐색 트리를 구분해야 한다. 전자는 알고리즘의 일종이고 후자는 자료구조의 일종이다. 이진 탐색 트리의 원리를 알기 이전에 이진탐색의 원리를 알아야 한다. 이진 탐색은 간단하게 말하면 탐색 범위를 절반으로 줄여나가는 탐색이다. 바로 이전 포스트에서 말한 search table과 같다. 굳이 자세한 설명을 더 하진 않겠다. 이런 이진 탐색을 트리 형태로 구조..