트리 (Tree)

Bin2·2022년 6월 29일

JavaScript 자료구조

트리 (Tree)

자료구조 중에 하나로 루트 노드를 기준으로 부모 노드와 자식 노드들이
트리처럼 뻗어나가는 구조를 갖는다.

이진 트리 (Binary Tree)

트리의 종류 중 하나로 각 노드가 2개 이하의 자식 노드만을 가지고 있는 구조이다.

이진 탐색 트리 (Binary Search Tree)

이진탐색트리란 다음과 같은 특징을 갖는 이진트리를 의미한다.

부모 노드의 왼쪽에 있는 노드들은 부모보다 항상 작다.
부모 노드의 오른쪽에 있는 노드들은 부모보다 항상 크다.

특정 값을 찾을 때 다른 자료구조에 비해 더 유리하다.
다른 자료구조의 경우 특정 값을 찾을 때 모든 요소들을 순회하며 찾아야 하지만
이진탐색트리의 경우 노드의 값과 찾고자 하는 값의 크기를 비교하는 방식으로 순회하기 때문에 시간복잡도를 크게 줄일 수 있다.

JavaScript로 이진 탐색 트리 구현

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

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

  insert(value) {
    const newNode = new Node(value);
    if (this.root === null) {
      this.root = newNode;
      return this;
    }

    let current = this.root;

    while (true) {
      if (value === current.value) return undefined;
      if (value < current.value) {
        if (current.left === null) {
          current.left = newNode;
          return this;
        }
        current = current.left;
      } else {
        if (current.right === null) {
          current.right = newNode;
          return this;
        }
        current = current.right;
      }
    }
  }

  contains(value) {
    if(this.root === null) return false;
    let current = this.root;

    while(current) {
      if(value < current.value) {
        current = current.left;
      } else if(value > current.value) {
        current = current.right;
      } else {
        return true;
      }
    }
    return false;
  }
}