Javascript의 이진 검색 트리

JavaScript로 이진 검색 트리 구현

이번 게시물에서는 JavaScript로 기본 BST(이진 검색 트리)를 구현하는 방법을 살펴보겠습니다. 노드를 삽입하고 다양한 트리 순회 방법(순서, 사전 순서, 사후 순서)을 수행하는 방법을 다룹니다.

노드 클래스
먼저 트리의 각 노드를 나타내는 Node 클래스를 정의해 보겠습니다.

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

각 노드 객체에는 세 가지 속성이 있습니다.

• 값: 노드에 저장된 데이터입니다.
• left: 왼쪽 자식 노드에 대한 포인터.
• right: 오른쪽 하위 노드에 대한 포인터.

BinarySearchTree 클래스

다음으로 노드를 관리하고 트리와 상호 작용하는 메서드를 제공하는 BinarySearchTree 클래스를 정의하겠습니다.

class BinarySearchTree {
    constructor() {
        this.root = null;
    }

    isEmpty() {
        return this.root === null;
    }

    insertNode(root, newNode) {
        if(newNode.value < root.value) {
            if(root.left === null) {
                root.left = newNode;
            } else {
                this.insertNode(root.left, newNode);
            }
        } else {
            if(root.right === null) {
                root.right = newNode;
            } else {
                this.insertNode(root.right, newNode);
            }
        }
    }

    search(root, value) {
        if(!root) {
            return false;
        }
        if(root.value === value) {
            return true;
        } else if(root.value > value) {
            return this.search(root.left, value);
        } else {
            return this.search(root.right, value);
        }
    }

    insert(value) {
        const newNode = new Node(value);
        if(this.isEmpty()) {
            this.root = newNode;
        } else {
            this.insertNode(this.root, newNode);
        }
    }
}

주요 방법:

• isEmpty(): 트리가 비어 있는지 확인합니다.
• insertNode(root, newNode): 이진 검색 트리 속성을 유지하면서 트리에 새 노드를 삽입합니다.
• search(root, value): 트리에서 값을 반복적으로 검색합니다.
• insert(value): 트리에 새 값을 삽입하는 편리한 방법입니다.

트리 순회 방법

트리가 있으면 이를 탐색해야 하는 경우가 많습니다. 세 가지 일반적인 순회 방법은 다음과 같습니다.

순차 순회

순차 순회는 왼쪽, 루트, 오른쪽 순서로 노드를 방문합니다.

inOrder(root) {
    if(root) {
        this.inOrder(root.left);
        console.log(root.value);
        this.inOrder(root.right);
    }
}

이 순회는 이진 검색 트리에 대해 감소하지 않는 순서로 노드를 인쇄합니다.

선주문 순회

선주문 순회는 루트, 왼쪽, 오른쪽 순서로 노드를 방문합니다.

preOrder(root) {
    if(root) {
        console.log(root.value);
        this.preOrder(root.left);
        this.preOrder(root.right);
    }
}

이 순회는 트리 구조를 복사하는 데 유용합니다.

주문 후 순회

사후 순회는 왼쪽, 오른쪽, 루트 순서로 노드를 방문합니다.

postOrder(root) {
    if(root) {
        this.postOrder(root.left);
        this.postOrder(root.right);
        console.log(root.value);
    }
}

이 순회는 노드를 삭제하거나 해제하는 데 자주 사용됩니다.

사용예

이러한 방법이 어떻게 함께 작동하는지 살펴보겠습니다.

const bst = new BinarySearchTree();
bst.insert(10);
bst.insert(5);
bst.insert(20);
bst.insert(3);
bst.insert(7);

console.log('In-order Traversal:');
bst.inOrder(bst.root);

console.log('Pre-order Traversal:');
bst.preOrder(bst.root);

console.log('Post-order Traversal:');
bst.postOrder(bst.root);

결론

이제 구현을 통해 JavaScript에서 이진 검색 트리를 생성하고 상호 작용할 수 있습니다. 트리 구조와 순회 방법을 이해하는 것은 많은 알고리즘 문제, 특히 검색 알고리즘, 표현식 구문 분석, 계층적 데이터 관리와 같은 영역에서 매우 중요합니다.

위 내용은 Javascript의 이진 검색 트리의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!