[Javascript] 자료구조 - Tree

 

 

 

1. Tree란?

자료구조에서 Tree(트리)는 계층적인 구조를 나타내는 비선형 자료구조이다. 트리는 노드(Node)들로 이루어져 있으며, 노드들은 간선(Edge)으로 연결되어 있다. 트리에서는 각 노드가 부모(Parent)와 자식(Child) 노드로 구성된다.

트리 구조에서 맨 위에 있는 노드는 루트노드라고 하며, 아래로 내려가면서 다양한 노드들이 연결되어 있다. 각 노드는 자신의 부모 노드와 연결된 간선을 통해 상위 레벨의 노드에 접근할 수 있다.

 

2. Tree가 사용되는 사례

트리는 여러 용도로 활용되는데 예를 들어, 데이터베이스에서 인덱싱(indexing), 파일 시스템의 폴더 구조, 컴퓨터 네트워크의 라우팅 테이블 등에서 사용된다. 또한 알고리즘에서는 이진 트리(Binary Tree), 이진 탐색 트리(Binary Search Tree), AVL 트리, 레드-블랙 트리 등 다양한 종류의 트리가 사용되는데 각각의 트리는 특정한 목적에 맞게 설계되어 있으며, 효율적인 데이터 저장 및 탐색을 위해 활용된다.

 

3. 이진트리(Binary Tree)

이진 트리(Binary Tree)는 각 노드가 최대 두 개의 자식 노드를 가지는 트리 구조인데 이진 트리에서 각 노드는 왼쪽 자식 노드와 오른쪽 자식 노드를 가질 수 있다.

이진 트리는 효율적인 탐색 알고리즘이 가능하다. 특히 이진 탐색 트리(Binary Search Tree)라는 특수한 종류의 이진 트리는 탐색, 삽입, 삭제 연산을 평균적으로 O(log n)의 시간 복잡도로 수행할 수 있다.

 

4. Javascript로 구현하는 Binary Tree

// 이진 트리 노드 클래스 정의
class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

// 이진 트리 클래스 정의
class BinaryTree {
    constructor() {
        this.root = null;
    }

    // 새로운 노드를 삽입하는 메서드
    insert(value) {
        const newNode = new Node(value);
        if (this.root === null) {
            this.root = newNode;
        } else {
            this.insertNode(this.root, newNode);
        }
    }

    // 삽입 보조 함수
    insertNode(node, newNode) {
        if (newNode.value < node.value) {
            if (node.left === null) {
                node.left = newNode;
            } else {
                this.insertNode(node.left, newNode);
            }
        } else {
            if (node.right === null) {
                node.right = newNode;
            } else {
                this.insertNode(node.right, newNode);
            }
        }
    }

    // 이진 트리를 중위 순회하여 값 출력
    inorderTraversal(node = this.root) {
        if (node !== null) {
            this.inorderTraversal(node.left);
            console.log(node.value);
            this.inorderTraversal(node.right);
        }
    }
}

// 이진 트리 생성 및 삽입
const binaryTree = new BinaryTree();
binaryTree.insert(50);
binaryTree.insert(30);
binaryTree.insert(70);
binaryTree.insert(20);
binaryTree.insert(40);
binaryTree.insert(60);
binaryTree.insert(80);

// 중위 순회로 값 출력
binaryTree.inorderTraversal();