[자료구조] javascript 트리 (Tree)

javascript 에서 트리 자료구조에 대해서 알아보자

트리구조의 특징

루트 정점을 제외한 모든 정점은 반드시 하나의 부모 정점을 가진다.
정점이 N개인 트리는 반드시 N-1개의 간선을 가진다.
루트에서 특정 정점으로 가는 경로는 유일하다.

이진트리

이진트리 종류: 완전 이진트리, 포화 이진트리, 편향 트리

이진트리 특징

정점이 N개인 이진트리는 최악의 경우 높이가 N이 될수있다. (편향트리일 경우)
정점이 N개인 포화 또는 완전 이진트리의 높이는 log N 이다.
높이가 a인 포화 이진트리는 2ª - 1 개의 정점을 가진다.
일반적인 이진 트리를 사용하는 경우는 많지 않다. 다음 자료구조에 응용된다. (이진트리 탐색, 힙, AVL 트리, 레드 블랙 트리)

이진 탐색 트리 조건

부모 노드의 왼쪽 노드는 부모 노드보다 작아야 한다.
부모 노드의 오른쪽 노드는 부모 노드보다 커야 한다.

이진트리 구현

// 이진 트리 노드 클래스 정의
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);
      }
    }
  }

  // 트리 순회 메서드: 전위 순회 (루트-왼쪽-오른쪽)
  preOrderTraversal(node) {
    if (node !== null) {
      console.log(node.value);
      this.preOrderTraversal(node.left);
      this.preOrderTraversal(node.right);
    }
  }

  // 트리 순회 메서드: 중위 순회 (왼쪽-루트-오른쪽)
  inOrderTraversal(node) {
    if (node !== null) {
      this.inOrderTraversal(node.left);
      console.log(node.value);
      this.inOrderTraversal(node.right);
    }
  }

  // 트리 순회 메서드: 후위 순회 (왼쪽-오른쪽-루트)
  postOrderTraversal(node) {
    if (node !== null) {
      this.postOrderTraversal(node.left);
      this.postOrderTraversal(node.right);
      console.log(node.value);
    }
  }
}

// 이진 트리 인스턴스 생성
const binaryTree = new BinaryTree();

활용 예시

계층적 데이터, 정렬된 데이터, 검색이 빈번한 데이터 등

계층적 데이터: 조직도, 디렉토리 구조 등
정렬된 데이터: 이진 탐색 트리, AVL 트리, 레드-블랙 트리 등
검색이 빈번한 데이터: 데이터베이스 인덱스 등