트리(Tree)와 이진 탐색 트리(BST, Binary Search Tree)는 비선형 자료구조를 대표하는 핵심 개념으로, 데이터 간의 계층적 관계를 효과적으로 표현하고 빠른 탐색을 가능하게 한다. 현대 소프트웨어 시스템에서 다루는 데이터는 단순한 나열 형태를 넘어서 구조적이고 관계적인 특성을 가지는 경우가 많다. 이러한 데이터를 효율적으로 관리하기 위해 트리 구조는 필수적으로 사용된다. 파일 시스템, 데이터베이스 인덱스, 운영체제 내부 구조, 웹 문서의 DOM 구조까지 트리는 실무 전반에 깊숙이 활용되고 있다. 이 글에서는 2026년 기준 최신 학습 흐름에 맞춰 트리의 기본 개념부터 이진 탐색 트리의 동작 원리, 구조적 특징, 장단점, 활용 사례까지 단계적으로 정리한다.
트리(Tree)란 무엇인가? 기본 개념
트리는 노드(Node)와 간선(Edge)으로 구성된 비선형 자료구조로, 데이터가 계층적인 형태로 연결되어 있는 것이 가장 큰 특징이다. 트리에는 하나의 시작점이 되는 루트(Root) 노드가 존재하며, 루트에서 아래 방향으로 여러 개의 자식 노드가 뻗어 나간다. 각 노드는 또 다른 자식 노드를 가질 수 있고, 이러한 구조가 반복되면서 전체 트리 형태가 만들어진다.
트리는 선형 자료구조와 달리 데이터가 일렬로 나열되지 않는다. 대신 부모와 자식 관계를 통해 위계가 형성되며, 이 구조 덕분에 데이터 간의 관계를 직관적으로 표현할 수 있다. 예를 들어 회사 조직도, 폴더 디렉터리 구조, 메뉴 구성 등은 모두 트리 구조로 표현하는 것이 가장 자연스럽다.
트리의 중요한 특징 중 하나는 사이클이 존재하지 않는다는 점이다. 즉, 어떤 노드에서 출발하더라도 다시 자기 자신으로 돌아오는 경로가 없다. 또한 루트 노드를 제외한 모든 노드는 정확히 하나의 부모 노드를 가진다. 이 규칙은 트리 구조를 명확하게 유지해 주는 핵심 조건이다.
트리의 주요 용어와 구조적 특성
트리를 정확히 이해하기 위해서는 여러 용어를 함께 익혀야 한다. 부모 노드와 자식 노드, 같은 부모를 가진 형제 노드, 자식이 없는 리프(Leaf) 노드는 트리의 기본 구성 요소다. 또한 특정 노드까지의 경로 길이를 깊이(Depth)라고 하며, 트리 전체에서 가장 깊은 노드의 깊이를 트리의 높이(Height)라고 부른다.
트리의 높이는 성능과 직결되는 요소다. 트리가 낮고 균형 잡혀 있을수록 탐색 속도는 빨라진다. 반대로 한쪽으로 길게 늘어진 트리는 선형 자료구조와 큰 차이가 없어지며, 탐색 효율이 급격히 떨어질 수 있다. 이러한 이유로 트리 구조를 설계할 때는 균형이 매우 중요한 요소로 작용한다.
트리는 자식 노드의 개수에 따라 다양한 형태로 분류된다. 그중에서도 각 노드가 최대 두 개의 자식만 가질 수 있는 구조를 이진 트리(Binary Tree)라고 하며, 이진 트리는 이후 다양한 파생 구조의 기반이 된다.
이진 탐색 트리(BST)의 개념과 기본 원리
이진 탐색 트리는 이진 트리의 한 종류로, 데이터 저장에 명확한 규칙이 적용된다. 각 노드를 기준으로 왼쪽 서브트리에는 해당 노드보다 작은 값이, 오른쪽 서브트리에는 큰 값이 저장된다. 이 규칙은 트리 전체에 일관되게 적용되며, 이를 통해 데이터가 자동으로 정렬된 상태를 유지하게 된다.
BST의 탐색 과정은 매우 직관적이다. 찾고자 하는 값이 현재 노드보다 작으면 왼쪽으로, 크면 오른쪽으로 이동한다. 이 과정을 반복하면 불필요한 비교를 최소화할 수 있으며, 평균적으로 로그 시간 복잡도를 가진다. 이러한 특성 덕분에 BST는 빠른 검색이 필요한 환경에서 자주 활용된다.
삽입과 삭제 역시 동일한 규칙을 기반으로 수행된다. 새로운 값은 탐색 과정과 동일한 방식으로 위치를 찾아 삽입되며, 삭제 시에는 자식 노드의 개수에 따라 처리 방식이 달라진다. 이러한 동작 원리를 정확히 이해하는 것이 BST 학습의 핵심이다.
이진 탐색 트리의 장단점
BST의 가장 큰 장점은 효율적인 탐색 성능이다. 데이터가 정렬된 상태로 유지되기 때문에 검색, 삽입, 삭제 연산이 모두 평균적으로 O(log n)의 시간 복잡도를 가진다. 이는 단순 배열이나 연결 리스트와 비교했을 때 매우 큰 이점이다.
하지만 BST에는 분명한 단점도 존재한다. 데이터가 특정 순서로 삽입되면 트리가 한쪽으로 치우치는 현상이 발생할 수 있다. 이 경우 트리는 사실상 연결 리스트와 같은 형태가 되며, 시간 복잡도는 O(n)까지 떨어진다. 이러한 문제를 해결하기 위해 AVL 트리, 레드-블랙 트리와 같은 자가 균형 이진 탐색 트리가 등장했다.
따라서 BST는 구조적 특성과 함께 한계를 이해하고, 상황에 맞게 사용하는 것이 중요하다.
트리와 BST의 활용 사례
트리는 계층 구조를 표현해야 하는 거의 모든 시스템에서 사용된다. 운영체제의 파일 시스템, 웹 페이지의 DOM 구조, 조직 관리 시스템은 모두 트리 구조를 기반으로 설계되어 있다. 이러한 구조 덕분에 데이터의 관계를 직관적으로 파악하고 관리할 수 있다.
이진 탐색 트리는 빠른 검색이 필요한 상황에서 강점을 가진다. 데이터베이스 인덱스, 자동 완성 기능, 범위 검색, 사전 구조 등은 BST 또는 그 확장 구조를 활용한 대표적인 사례다. 또한 코딩 테스트와 기술 면접에서도 트리와 BST는 빠지지 않는 단골 주제다.
결론
트리(Tree)는 계층적 데이터를 표현하는 가장 기본적인 비선형 자료구조이며, 이진 탐색 트리(BST)는 그중에서도 효율적인 탐색을 가능하게 하는 핵심 구조다. 두 개념의 구조와 원리, 장단점을 정확히 이해하면 복잡한 데이터 구조를 훨씬 체계적으로 다룰 수 있다. 자료구조 학습 과정에서 트리와 BST는 반드시 깊이 있게 학습해야 할 중요한 주제다.