자바스크립트로 이진 탐색 트리(BinarySearchTree) 만들기

이번 글에서는 자바스크립트를 사용해 이진 탐색 트리(Binary Search Tree)를 어떻게 생성하고 표현하는지 알아보겠습니다. 가장 먼저 해야 할 일은 BinarySearchTree 클래스를 만들고, 그 안에 노드(Node) 속성을 정의하는 것입니다.

예제 코드

class BinarySearchTree {
    constructor() {
        // 루트(root) 요소를 null로 초기화합니다.
        this.root = null;
    }
}

BinarySearchTree.prototype.Node = class {
    constructor(data, left = null, right = null) {
        this.data = data;
        this.left = left;
        this.right = right;
    }
};

코드 설명

위 코드는 BST(이진 탐색 트리) 클래스의 기본 뼈대를 만든 것입니다. 각 부분을 살펴보면 다음과 같습니다.

BinarySearchTree 클래스: 생성자에서 root 속성을 null로 초기화합니다. 트리가 비어 있는 상태를 나타내며, 이후 노드가 추가되면 이 root가 트리의 시작점이 됩니다.

Node 클래스: 트리를 구성하는 개별 노드를 표현합니다. 각 노드는 세 가지 속성을 가집니다.

• data: 노드에 저장되는 값입니다.
• left: 왼쪽 자식 노드에 대한 참조입니다. 값이 없으면 null입니다.
• right: 오른쪽 자식 노드에 대한 참조입니다. 값이 없으면 null입니다.

여기서는 프로토타입(prototype)을 활용해 Node 클래스를 BinarySearchTree의 정적 속성으로 정의했습니다. 이렇게 하면 노드 구조가 트리 클래스와 논리적으로 묶여 있어 코드의 응집도가 높아집니다.

아직은 트리의 기본 구조만 정의한 상태입니다. 앞으로 삽입(insert), 검색(search), 삭제(delete) 같은 핵심 연산 메서드를 하나씩 추가하면서 이진 탐색 트리를 완성해 나가겠습니다.