[자료구조] 트리, 이진검색 트리(javascript로 구현하기)

트리

• 부모자식관계가 있는 노드들로 이루어진 비선형 데이터 구조
• 하나의 시작노드가 있다.
• 형제노드끼리 연결되어 있으면 안되고 한 노드의 직계 부모가 둘일 수도 없다
• 다양한 형태의 트리구조 존재
• 예시) html DOM

 

이진트리(binary tree)

• 각 노드가 두개 이하의 자식노드를 갖는 트리구조

 

이진탐색트리(binary search tree)

 

• 특정한 방식으로 정렬되어있는 이진트리.
• 좌 상(하)방에는 자신보다 작은 값의 노드가 위치.
• 우 상(하)방에는 자신보다 큰 값의 노드가 위치함.
• 검색속도가 빠름.
• 삽입 및 검색: O(logN)
• 한쪽으로 치우친 트리에서는 O(n)

 

이진탐색트리 구현

노드

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

 

BST(binary search tree) constuctor

class BST {
  constructor() {
    this.root = null;
  }
  // ...메소드...
}

 

삽입 메소드

• 반복문 혹은 재귀를 이용해 구현할 수 있다.
• 비슷한 뎁스에 길이이니 반복문이 더 나을듯 하다.

 // 반복문
insert(val) {
  const newNode = new Node(val);
  if (!this.root) {
    this.root = newNode;
    return this;
  }
  let currentNode = this.root;
  while (1) {
    if (val < currentNode.val) {
      if (!currentNode.left) {
        currentNode.left = newNode;
        return this;
      }
      currentNode = currentNode.left;
      continue;
    }
    if (!currentNode.right) {
      currentNode.right = newNode;
      return this;
    }
    currentNode = currentNode.right;
  }
}


 // 재귀
insert(val) {
  const newNode = new Node(val);
  if (!this.root) {
    this.root = newNode;
    return this;
  }
  const helper = (currentNode) => {
    if (val < currentNode.val) {
      if (!currentNode.left) {
        currentNode.left = newNode;
        return this;
      }
      helper(currentNode.left);
      return this;
    }
    if (!currentNode.right) {
      currentNode.right = newNode;
      return this;
    }
    helper(currentNode.right);
  };
  // helper(this.root);
}

 

검색 메소드

• 마찬가지로 재귀로도 가능(예시는 반복문)

  includes(val) {
    if (this.root) return false;
    let currentNode = this.root;
    while (1) {
      if (val < currentNode.val) 
      if (!currentNode.left) return false;
        currentNode = currentNode.left;
        continue;
      }
      if (val === currentNode.val) return true;
      if (!currentNode.right) return false;
      currentNode = currentNode.right;
    }
  }