Binary Search Tree

정렬된 array는 binary search로 빠르게 찾을 수 있지만, 새 값을 중간에 넣거나 지우려면 많은 원소를 이동해야 합니다. 반대로 hash table은 검색은 빠르지만 값의 순서를 보존하지 않아 범위 조회나 정렬 순회가 어렵습니다. BST는 '동적으로 변하는 데이터'를 정렬 상태와 함께 유지하려는 요구를 해결하려고 등장합니다.

컴파일러의 심볼 테이블, 메모리 관리, 초기 데이터베이스 인덱스 같은 시스템은 검색만 빠르면 끝나지 않았습니다. 값이 계속 들어오고 빠지면서도 순서 정보가 유지돼야 했고, floor/ceiling 같은 순서 기반 질의도 필요했습니다. Search tree 계열 구조는 이런 압력 속에서 발전했고, BST는 그 가장 기본적인 형태로 이후 AVL, red-black tree 같은 균형 트리의 출발점이 됐습니다.

탐색은 루트에서 시작해 찾는 키를 현재 노드와 비교하는 식으로 진행됩니다. 찾는 값이 더 작으면 왼쪽으로, 더 크면 오른쪽으로 내려가며 같은 과정을 반복합니다. 삽입도 같은 비교 경로를 따라가 빈 자리에 새 노드를 붙입니다. 이 규칙 덕분에 중위 순회(left-root-right)를 하면 값이 정렬된 순서로 나오지만, 입력 순서가 한쪽으로 치우치면 트리가 막대기처럼 길어져 탐색과 삽입이 다시 선형 시간에 가까워질 수 있습니다.

BST와 heap은 둘 다 트리지만 유지하는 질서가 다릅니다. BST는 전체적인 정렬 관계를 보존해 범위 조회와 정렬 순회에 유리하고, heap은 부모가 자식보다 더 우선이라는 부분 질서만 유지해 최상단 원소를 빠르게 꺼내는 데 집중합니다. 또 BST는 hash table과 달리 순서를 직접 보존하지만, 해시 기반 구조처럼 평균 O(1) 키 조회를 목표로 하지는 않습니다.

BST는 정렬된 집합과 맵, 범위 검색, predecessor/successor 조회처럼 순서 정보가 비즈니스 로직의 일부인 곳에서 쓰입니다. 예를 들어 가격 구간별 조회, 시간 순으로 가장 가까운 예약 찾기, 사전순 추천 후보 관리 같은 문제가 여기에 가깝습니다. 다만 실제 서비스 구현에서는 한쪽으로 치우치는 문제를 피하려고 균형 BST 변형을 더 자주 쓰며, BST 자체는 그 균형 전략이 왜 필요한지 이해하는 출발점으로 중요합니다.