Computer Science/Algorithm, Data Structure

자바스크립트 자료구조 트리(Tree)

Write and Remember 2019. 6. 11. 17:44

모든 자바스크립트 개발자가 알아야 하는 33가지 개념

 

트리의 용어에 대해 알아보면

 

Root: 트리의 최상위 노드

 

Child: 자식 노드

 

Parent: 부모 노드

 

leaf: 자식 노드가 없는 노드

 

ancestor: 조상 노드

 

descendant: 자손 노드

 

sibling: 형제 노드

 

트리는 다양한 종류가 있는데 이진 탐색 트리(Binary Search Tree)에 대해 알아보자.

 

여기서 이진 트리란 최대 두 개의 자식 노드를 가지는 트리 자료 구조이다.

 

이진 탐색 트리는 아래와 같은 속성이 있는 이진 트리의 자료 구조이다.

 

이진 탐색 트리(Binary Search Tree)

 

모든 노드에는 최대 2개의 하위 노드가 있고

 

각 노드의 키가 왼쪽 하위 트리에 저장된 키보다 크거나 같고

 

오른쪽 하위 트리에 저장된 키보다 작거나 같아야 한다.

 

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

class BinarySearchTree {
  constructor() {
    this.root = null;
  }
  // 추가
  insert(data) {
    const node = new Node(data);

    if (!this.root) {
      this.root = node;
      return this;
    }

    let current = this.root;

    while (current) {
      // 중복 검사
      if (data === current.data) return;
      // 왼쪽 노드 추가
      if (data < current.data) {
        if (!current.left) {
          current.left = node;
          break;
        }
        current = current.left;
      }
      // 오른쪽 노드 추가
      if (data > current.data) {
        if (!current.right) {
          current.right = node;
          break;
        }
        current = current.right;
      }
    }
  }
  // 검색
  find(data) {
    if (!this.root) return null;
    let current = this.root;

    while (current) {
      if (data === current.data) return current.data;

      if (current.right && data > current.data) {
        current = current.right;
      } else {
        current = current.left;
      }
    }

    return false;
  }
  // 포함
  include(data) {
    const found = this.find(data);

    return found ? true : false;
  }

  // Breadth-first search(너비 우선 탐색)
  bfs() {
    let node = this.root;
    const queue = [node];
    const finalData = [];
    while (queue.length) {
      node = queue.shift();
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
      finalData.push(node.data);
    }

    return finalData;
  }

  // Depth-first search(깊이 우선 탐색)
  // 1. Pre-order traversal(전위 순회)
  preOrder() {
    const finalData = [];
    // 재귀함수
    function traverse(node) {
      finalData.push(node);
      if (node.left) traverse(node.left);
      if (node.right) traverse(node.right);
    }

    traverse(this.root);
    return finalData;
  }
  // 2. Post-order traversal(후위 순회)
  postOrder() {
    const finalData = [];
    // 재귀함수
    function traverse(node) {
      if (node.left) traverse(node.left);
      if (node.right) traverse(node.right);
      finalData.push(node);
    }
    traverse(this.root);
    return finalData;
  }
  // 3. In-order traversal(중위 순회)
  inOrder() {
    const finalData = [];
    // 재귀함수
    function traverse(node) {
      if (node.left) traverse(node.left);
      finalData.push(node.data);
      if (node.right) traverse(node.right);
    }
    traverse(this.root);
    return finalData;
  }
  // Max
  maxNode() {
    if (!this.root) return null;
    let current = this.root;
    while (current.right) {
      current = current.right;
    }

    return current.data;
  }
  // Min
  minNode() {
    if (!this.root) return null;
    let current = this.root;
    while (current.left) {
      current = current.left;
    }

    return current.data;
  }
}

const bst = new BinarySearchTree();

bst.insert(15);
bst.insert(20);
bst.insert(30);
bst.find(15); // true
bst.find(10); // false
bst.include(20); // true
bst.include(25); // false
bst.bfs(); [15, 20, 30]
bst.maxNode(); 30
bst.minNode(); 15
bst.preOrder(); [15, 20, 30]
bst.postOrder(); [30, 20, 15]
bst.inOrder(); [15, 20, 30]