1. BST (Binary Search Tree)란? 아마 자료구조 시간에 다 배웠으실 텐데요. BST는 ordered set (순서 가능한 집합)에 속한 원소(key)로 이루어진 이진 트리이고, 다음의 조건을 만족합니다. 각각의 노드는 하나의 unique한 key를 갖고 있다. node의 left subtree는 node의 key보다 작거나 같다. node의 right subtree는 node의 key보다 크거나 같다. 생각보다 간단하죠? 우리의 목적은 BST에서 검색하는 key와 같은 원소를 찾는 average time을 최소화하는 데 있습니다. 만약에 각 원소가 검색될 확률이 모두 동일하다면, 트리의 높이는 낮을 수록, 그리고 좌우의 높이 차가 덜 클수록 효율적입니다. 하지만 만약에 각 원소가 검색..
