[자료구조-JS] 이진탐색트리(Binary Search Tree) 구현

사진출처 : https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%ED%83%90%EC%83%89_%ED%8A%B8%EB%A6%AC

 

트리란 무엇인가?

• 트리는 부모, 자식 노드의 관계를 정의한 자료구조라고 볼 수 있다.
• 트리에 속한 노드는 부모-자식 관계에 따라 부모가 자식을 가르키는 방향으로 진행된다.
• 이 때 모든 노드는 루트 노드와 멀어지는 방식으로 연결된다.

이진 탐색 트리의 동작

• 모든 부모 노드가 최대 2개의 자식 노드(left, right)를 가진다. (모든 이진트리의 공통점)
• 왼쪽 자식 노드는 부모보다 항상 작고,
• 오른쪽 자식 노드는 부모보다 항상 크다.

이진 탐색 트리가 단순 이진 트리보다 빠른 이유

• 단순 이진 트리는 부모 노드가 최대 2개의 자식노드만 가진다는 특징만 있다.
  = 따라서 노드의 값만 보고 부모자식간 대소판별이 불가능하다.
• 이진 탐색 트리는 부모 노드를 기준으로 왼쪽에는 부모 노드보다 작은 값, 오른쪽에는 부모 노드보다 큰 값을 지닌다.
  = 이를 기준으로 노드의 값을 보고 탐색할 범위를 반씩 줄여나갈 수 있다.

BigO

• 삽입 : O(logN)
• 검색 : O(logN)
• 최악의 상황 : O(N)
  (부모보다 큰 값만 있으면 right에 모든 노드들이 몰빵됨)
  (부모보다 작은 값만 있으면 left에 모든 노드들이 몰빵됨)

구현

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

class BST {
  constructor() {
    this.root = null
  }

  insert(value) {
    // 새 노드를 만듦
    let newNode = new Node(value)
    // root 노드가 없는 상태라면 방금 만든 노드가 root 노드가 되고 return
    if(this.root === null) {
      this.root = newNode
      return this
    }
    // root 노드가 기준점이 되어 부모 노드 대비 값이 크다면 right, 작으면 left로 이동 
    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
      }
      if (value > current.value) {
        if(current.right === null) {
          current.right = newNode
          return this
        }
        current = current.right
      }
    }
  }


  find(value) {
    // root 노드를 기점으로 탐색 시작
    if (this.root === null) return undefined
    // 찾고자 하는 값이 current.value보다 크다면 노드의 오른쪽을, 작다면 노드의 왼쪽을 탐색
    // 값이 없다면 undefined를 return
    let current = this.root
    while(current.value !== value) {
      if (value < current.value) {
        if (current.left === null) return undefined
        current = current.left
      }
      if (value > current.value) {
        if (current.right === null) return undefined
        current = current.right
      }
    }
    return current
  }
}