트리와 이진 탐색 트리(BST)의 차이를 설명해주세요.

트리는 계층 관계를 표현하는 비선형 자료구조이고, 이진 탐색 트리(BST)는 각 노드가 왼쪽에는 더 작은 값, 오른쪽에는 더 큰 값을 갖도록 제한한 특수한 이진 트리입니다. 일반 트리는 구조 표현이 목적이고, BST는 정렬된 데이터의 빠른 탐색이 목적입니다.

핵심 개념

• 트리는 루트, 부모/자식, 리프, 깊이 같은 개념으로 계층을 표현합니다.
• BST는 중위 순회(in-order traversal)를 하면 오름차순 결과가 나옵니다.
• 균형이 유지된 BST는 탐색/삽입/삭제가 O(log n)이지만, 한쪽으로 치우치면 O(n)이 됩니다.

동작 방식 또는 판단 기준

이 주제를 이해할 때는 다음 순서로 보면 실무 적용이 쉬워집니다.

1. 무엇을 해결하려는가: 성능, 표현력, 안정성, 접근성 중 어떤 문제를 줄이려는지 확인합니다.
2. 전제 조건은 무엇인가: 정렬 여부, 브라우저 지원, 네트워크 특성, 동시성 조건처럼 성립해야 하는 조건을 점검합니다.
3. 비용은 어디서 발생하는가: 시간 복잡도, 메모리, 캐시, 재시도, 렌더링 비용처럼 병목 지점을 나눠 봅니다.
4. 실패 시 어떤 문제가 생기는가: 잘못 적용했을 때의 버그나 운영 리스크를 함께 고려합니다.

실제 예시

BST 예시
        8
      /        3     10
    / \         1   6      14

6 검색: 8보다 작음 -> 3보다 큼 -> 6 발견
중위 순회: 1, 3, 6, 8, 10, 14

실무에서 주의할 점

• 정렬된 데이터를 순서대로 삽입하면 BST가 연결 리스트처럼 기울어질 수 있습니다.
• 중복 값 처리 정책(왼쪽에 둘지, count로 저장할지)을 명확히 해야 합니다.
• 실무에서는 직접 BST를 구현하기보다 balanced tree, B-tree, DB index를 사용하는 경우가 많습니다.

실무 적용 가이드

• 계층 데이터에는 일반 트리, 정렬된 검색/범위 조회에는 균형 트리를 검토합니다.
• AVL, Red-Black Tree처럼 자동 균형을 맞추는 구조를 이해하면 표준 라이브러리 동작을 이해하기 쉽습니다.
• 트리 문제는 순회 방식(pre/in/post/level-order)을 먼저 정하면 풀이가 단순해집니다.

함께 연결해서 보면 좋은 키워드

Tree, Binary Search Tree, Traversal, Balanced Tree

정리

트리는 계층 관계를 표현하는 비선형 자료구조이고, 이진 탐색 트리(BST)는 각 노드가 왼쪽에는 더 작은 값, 오른쪽에는 더 큰 값을 갖도록 제한한 특수한 이진 트리입니다. 다만 개념 자체보다 중요한 것은 적용 조건과 한계를 함께 이해하는 것입니다. 작은 예제에서는 단순해 보여도 실제 서비스에서는 성능, 보안, 유지보수성, 접근성 요구사항이 함께 얽히므로, 문제의 성격을 먼저 파악한 뒤 적절한 도구로 선택하는 것이 좋습니다.