트리(Tree) 자료구조의 기본 개념과 활용

자료구조는 프로그램의 효율성과 직결되는 중요한 요소입니다. 다양한 자료구조 중에서도 트리(Tree)는 계층적 데이터를 효과적으로 표현하는 비선형 자료구조의 대표적인 예시입니다. 특히 웹 프론트엔드 개발에서 자주 접하는 DOM(Document Object Model)이 트리의 한 형태로 구현되어 있어, 트리에 대한 이해는 웹 개발자에게 필수적입니다. 이 글에서는 트리 자료구조의 기본 개념과 주요 용어, 이진 탐색 트리(Binary Search Tree)의 특성, 그리고 너비 우선 탐색(BFS) 및 깊이 우선 탐색(DFS)과 같은 탐색 기법을 살펴봅니다.

트리(Tree)란 무엇인가?

트리는 데이터 항목들 간의 계층적 관계를 표현하는 자료구조입니다. 그 이름처럼 뿌리가 위쪽에 있고 잎이 아래쪽에 있는 나무를 뒤집어 놓은 형태와 유사하며, 데이터 간의 관계를 시각적으로 직관적으로 보여줍니다. 웹 사이트의 사이트맵, 파일 시스템, 조직도 등 다양한 분야에서 트리가 활용됩니다.

트리의 주요 구성 요소와 용어는 다음과 같습니다:

  • 루트 노드 (Root Node): 트리의 가장 상위에 있는 노드입니다. 모든 트리에는 오직 하나의 루트 노드만이 존재합니다.
  • 자식 노드 (Child Node): 부모 노드에 의해 직접 연결된 하위 노드입니다. 루트 노드를 제외한 모든 노드는 최소 하나의 부모 노드를 가집니다.
  • 부모 노드 (Parent Node): 특정 노드의 바로 상위에 위치한 노드입니다.
  • 형제 노드 (Sibling Node): 같은 부모 노드를 가지는 노드들을 말합니다.
  • 리프 노드 (Leaf Node): 자식 노드가 없는 노드를 리프 노드 또는 외부 노드라고 합니다.
  • 서브 트리 (Subtree): 특정 노드와 그 노드의 모든 후손들로 구성된 트리의 일부분입니다.
  • 깊이 (Depth): 루트 노드로부터 특정 노드까지 도달하기 위한 간선(edge)의 수입니다. 루트 노드의 깊이는 0입니다.
  • 높이 (Height): 특정 노드로부터 리프 노드까지의 가장 긴 경로에 있는 간선의 수입니다. 리프 노드의 높이는 0입니다. 트리의 높이는 루트 노드의 높이와 같습니다.

트리의 각 노드는 일반적으로 데이터를 저장할 수 있는 키(key) 또는 값(value)과 자식 노드들을 가리키는 참조를 포함합니다. 기본적인 트리 노드의 구조는 다음과 같습니다. 

class TreeNode {
    constructor(key) {
        this.key = key; // 노드의 값 또는 식별자
        this.children = []; // 자식 노드들을 저장할 배열
    }
}

이진 탐색 트리 (Binary Search Tree)

트리에는 일반 트리 외에도 이진 트리(Binary Tree), 이진 탐색 트리(Binary Search Tree, BST), AVL 트리, 레드-블랙 트리 등 여러 종류가 있습니다. 이 중 이진 탐색 트리는 특정 규칙에 따라 노드를 배치하여 삽입, 탐색, 삭제 연산을 효율적으로 수행할 수 있도록 설계된 이진 트리입니다.

이진 탐색 트리는 다음 규칙을 따릅니다:

  • 각 노드는 최대 두 개의 자식 노드를 가질 수 있습니다.
  • 왼쪽 자식 노드의 값은 부모 노드의 값보다 작아야 합니다.
  • 오른쪽 자식 노드의 값은 부모 노드의 값보다 커야 합니다.

이진 탐색 트리는 일반적으로 다음과 같은 연산들을 포함합니다. 

class BinarySearchTree {
    constructor() {
        this.root = null; // 트리의 루트 노드
    }

    // 이진 탐색 트리의 노드 구조
    class BSTNode {
        constructor(key) {
            this.key = key;
            this.left = null;  // 왼쪽 자식 노드
            this.right = null; // 오른쪽 자식 노드
        }
    }

    // 새 노드를 트리에 삽입하는 메서드
    insert(value) { /* ... */ }

    // 특정 값을 트리가 포함하는지 탐색하는 메서드
    search(value) { /* ... */ }

    // 트리 내의 최솟값을 반환하는 메서드
    findMin() { /* ... */ }

    // 트리 내의 최댓값을 반환하는 메서드
    findMax() { /* ... */ }

    // 트리의 특정 노드를 삭제하는 메서드
    remove(value) { /* ... */ }

    // 중위 순회 (In-order traversal): 왼쪽 -> 루트 -> 오른쪽
    traverseInOrder(callback) { /* ... */ }

    // 전위 순회 (Pre-order traversal): 루트 -> 왼쪽 -> 오른쪽
    traversePreOrder(callback) { /* ... */ }

    // 후위 순회 (Post-order traversal): 왼쪽 -> 오른쪽 -> 루트
    traversePostOrder(callback) { /* ... */ }
}

노드 삽입 (Insert)

새로운 키를 삽입할 때는 루트 노드부터 시작하여 삽입할 키와 현재 노드의 키를 비교하며 적절한 위치를 찾습니다.

  • 삽입할 키가 현재 노드의 키보다 작으면 왼쪽 자식 노드로 이동합니다.
  • 삽입할 키가 현재 노드의 키보다 크면 오른쪽 자식 노드로 이동합니다.
  • 이 과정을 반복하여 자식 노드가 없는 위치(null)에 도달하면 해당 위치에 새 노드를 삽입합니다.

예를 들어, 키 19를 삽입한다고 가정하면:

  • 19는 50(루트)보다 작으므로 왼쪽으로 이동합니다.
  • 다음 노드가 17이라면, 19는 17보다 크므로 오른쪽으로 이동합니다.
  • 다음 노드가 23이라면, 19는 23보다 작으므로 왼쪽으로 이동합니다.
  • 이 위치에 노드가 없으므로, 23의 왼쪽 자식으로 19를 추가합니다.

최솟값/최댓값 (Min/Max)

이진 탐색 트리에서 최솟값은 루트 노드에서 시작하여 항상 왼쪽 자식 노드로만 이동했을 때 도달하는 노드의 값입니다. 반대로 최댓값은 항상 오른쪽 자식 노드로만 이동했을 때 도달하는 노드의 값입니다.

트리 탐색: BFS vs. DFS

트리 순회(Traversal)에는 크게 두 가지 주요 방식이 있습니다: 너비 우선 탐색(Breadth-First Search, BFS)과 깊이 우선 탐색(Depth-First Search, DFS)입니다. 이 두 가지 방식은 데이터를 탐색하는 순서가 다르며, 각각의 활용 사례가 존재합니다.

다음 HTML 구조를 DOM 트리에 매핑하여 순회 방식을 살펴보겠습니다. 

<content>
    <sidebar>
        <menu></menu>
    </sidebar>
</content>
<main>
    <post></post>
    <img />
</main>

위 HTML을 DOM 트리로 시각화했을 때 (루트 노드가 최상위 요소라고 가정):

  • 깊이 우선 탐색(DFS) 순서는 다음과 같습니다:

    root → content → sidebar → menu → main → post → img

    (하나의 경로를 최대한 깊게 탐색한 후, 다시 돌아와 다른 경로를 탐색합니다.)

  • 너비 우선 탐색(BFS) 순서는 다음과 같습니다:

    root → content → main → sidebar → post → img → menu

    (현재 레벨의 모든 노드를 탐색한 후, 다음 레벨로 이동하여 탐색합니다.)

태그: 자료구조 트리 이진탐색트리 DOM 알고리즘

7월 5일 02:58에 게시됨

인기 태그

©2026 괴물 클럽