[자료구조-JS] 이진탐색트리 너비우선탐색(BFS) 구현

너비우선탐색이란 무엇인가?

• 트리나 그래프를 탐색하는 기법 중 하나로써 너비(Breadth)를 우선적으로 탐색하는 방법이다.
• 너비우선탐색 구현을 위해서 보통 큐(Queue) 자료구조를 이용한다.

너비우선탐색의 동작

• 루트 노드부터 탐색을 시작한다.
• 기준 노드에 자식 노드들이 존재한다면 큐에 추가하고, 자기 자신은 큐에서 나온다.
• 위의 과정을 반복한다. 큐에 아무것도 존재하지 않게 된다면 탐색이 종료된다. 

너비우선탐색 주의사항

• 만약 너비가 넓은 트리나 그래프라면 큐에 저장해야하는 너비 요소들이 많아지므로 공간복잡도가 증가한다.
• 따라서 너비우선탐색을 효과적으로 사용하기 위해서는 너비가 좁은 트리나 그래프를 대상으로 사용하는 것이 좋다. 

구현

// 트리 구현체
class BST {
  constructor() {
    this.root = null
  }

  insert(value) {
    let 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
      }
      if (value > current.value) {
        if(current.right === null) {
          current.right = newNode
          return this
        }
        current = current.right
      }
    }
  }

  find(value) {
    if (this.root === null) return undefined
    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
  }
  
  // 너비우선탐색 코드
  BFS() {
    let node = this.root
    let queue = []
    let data = []
    queue.push(node)
    while(queue.length) {
      node = queue.shift()
      data.push(node.value)
      if (node.left) queue.push(node.left)
      if (node.right) queue.push(node.right)
    }
    return data
  }
}