이진 탐색 트리 (BST)

BST 는 Binary Search Tree 의 줄임말이다. 어느 노드에서 보든 왼쪽 아래에는 그 노드보다 작은 값만, 오른쪽 아래에는 큰 값만 두는 이진 트리다. 그래서 값을 찾을 때 루트(맨 위 노드)부터 비교해 작으면 왼쪽, 크면 오른쪽으로만 내려가면 된다. 다만 값을 정렬된 순서로 넣으면 한쪽으로만 길게 늘어져 연결 리스트처럼 느려진다.