이진 트리(Binary Tree)는 데이터 저장을 목적으로 사용되는 특수한 자료구조입니다. 이진 트리의 가장 큰 특징은 각 노드가 최대 두 개의 자식 노드만 가질 수 있다는 조건입니다.
이진 트리는 정렬된 배열과 연결 리스트의 장점을 동시에 지니고 있습니다. 즉, 탐색 속도는 정렬된 배열처럼 빠르면서도, 삽입과 삭제 연산은 연결 리스트처럼 효율적으로 처리할 수 있습니다. 이러한 균형 잡힌 성능 덕분에 이진 트리는 다양한 알고리즘과 데이터 관리 시스템에서 널리 활용됩니다.
아래는 이진 트리의 구조를 보여주는 예시 그림입니다.
이진 트리의 핵심 용어
트리 구조를 이해하려면 다음과 같은 기본 용어들을 반드시 알아야 합니다.
경로(Path) − 트리의 간선(edge)을 따라 이어지는 노드들의 순서를 의미합니다.
루트(Root) − 트리의 최상단에 위치한 노드를 말합니다. 하나의 트리에는 오직 하나의 루트만 존재하며, 루트에서 트리 내 임의의 노드까지 이어지는 경로는 단 하나뿐입니다.
부모(Parent) − 루트 노드를 제외한 모든 노드는 위쪽 방향으로 하나의 간선과 연결되어 있는데, 이때 위쪽에 있는 노드를 부모 노드라고 합니다.
자식(Child) − 특정 노드의 아래쪽으로 간선과 연결되어 있는 노드를 자식 노드라고 합니다.
리프(Leaf) − 자식 노드를 하나도 가지지 않는 노드를 리프 노드(잎 노드)라고 합니다.
서브트리(Subtree) − 특정 노드의 모든 하위(후손) 노드들이 이루는 집합을 의미합니다.
방문(Visiting) − 프로그램의 제어 흐름이 해당 노드에 도달했을 때, 그 노드의 값을 확인하는 것을 말합니다.
순회(Traversing) − 특정한 순서에 따라 트리의 노드들을 차례대로 거쳐 가는 과정을 의미합니다.
레벨(Level) − 노드가 몇 번째 세대에 속하는지를 나타냅니다. 루트 노드를 레벨 0이라 하면, 그 자식 노드는 레벨 1, 손자 노드는 레벨 2가 되는 식으로 계층이 형성됩니다.
키(Key) − 노드가 가진 값으로, 노드를 검색할 때 기준이 되는 값을 의미합니다.
마무리
이진 트리는 탐색, 삽입, 삭제 작업을 효율적으로 수행할 수 있는 강력한 자료구조입니다. 위에서 소개한 용어들은 이진 트리뿐 아니라 이진 탐색 트리(BST), 힙(Heap) 등 다양한 트리 기반 자료구조를 학습할 때 공통으로 사용되는 기본 개념이므로, 확실히 익혀두는 것이 좋습니다.