BFS(Breadth First Search) & DFS(Depth First Search)

BFS

/**
 * 2 ways of traversing a tree.
 * - Breadth First Search (BFS)
 * - Depth First Search (DFS)
 *
 * BFS (Steps - Iteratively)
 * - Create a queue(this can be an array) and a variable to store the values of nodes visited.
 * - Place the root node in the queue.
 * - Loop as long as there is anything in the queue.
 * > Dequeue a node from the queue and push the value of the node into the variable that stores the nodes.
 * > if there is a left property on the node dequeued - add it to the queue.
 * > If there is a right property on the node dequeued - add it to the queue.
 * - Return the variable that stores the values.
 *
 *
 */

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) {
      this.root = newNode;
      return this;
    }

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

  find(value) {
    if (!this.root) return false;

    let current = this.root;
    let found = false;

    while (current && !found) {
      if (value < current.value) {
        current = current.left;
      } else if (value > current.value) {
        current = current.right;
      } else {
        found = true;
      }
    }
    if (!found) return undefined;
    return current;
  }

  BFS() {
    const data = [];
    const queue = [];
    let node = this.root;
    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;
  }
}

const tree = new BinarySearchTree();
tree.insert(10);
tree.insert(6);
tree.insert(15);
tree.insert(3);
tree.insert(8);
tree.insert(20);
console.log(tree.BFS());

 

DFS

/**
 * 2 ways of traversing a tree.
 * - Breadth First Search (BFS)
 * - Depth First Search (DFS)
 *
 * DFS
 * - InOrder : traverse from the left subtree to the root then to the right subtree.
 * - PreOrder : traverse from the root to the left subtree then to the right subtree.
 * - PostOrder : traverse from the left subtree to the right subtree then to the root.
 *
 */

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) {
      this.root = newNode;
      return this;
    }

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

  /**
   * DFS - PreOrder (Steps - Recursively)
   * - Create a variable to store the values of nodes visited
   * - Store the root of the BST in a variable called current.
   * - Write a helper function which accepts a node
   * > - Push the value of the node to the variable that stores the values.
   * > - If the node has a left property, call the helper function with the left property on the node.
   * > - If the node has a right property, call the helper function with the right property on the node.
   */
  DFSPreOrder() {
    const data = [];
    let current = this.root;

    function traverse(node) {
      data.push(node.value);
      if (node.left) traverse(node.left);
      if (node.right) traverse(node.right);
    }

    traverse(current);
    return data;
  }

  /**
   * DFS - PostOrder (Steps - Recursively)
   * - Create a variable to store the values of nodes visited
   * - Store the root of the BST in a variable called current.
   * - Write a helper function which accepts a node
   * > - If the node has a left property, call the helper function with the left property on the node.
   * > - If the node has a right property, call the helper function with the right property on the node.
   * > - Push the value of the node to the variable that stores the values.
   * > - Invoke the helper function with the current variable.
   * - Return the array of values.
   */
  DFSPostOrder() {
    const data = [];
    let current = this.root;

    function traverse(node) {
      if (node.left) traverse(node.left);
      if (node.right) traverse(node.right);
      data.push(node.value);
    }

    traverse(current);
    return data;
  }

  /**
   * DFS - InOrder (Steps - Recursively)
   * - Create a variable to store the values of nodes visited
   * - Store the root of the BST in a variable called current.
   * - Write a helper function which accepts a node
   * > - If the node has a left property, call the helper function with the left property on the node.
   * > - Push the value of the node to the variable that stores the values.
   * > - If the node has a right property, call the helper function with the right property on the node.
   * - Invoke the helper function with the current variable.
   * - Return the array of values.
   */
  DFSInOrder() {
    const data = [];
    let current = this.root;

    function traverse(node) {
      if (node.left) traverse(node.left);
      data.push(node.value);
      if (node.right) traverse(node.right);
    }

    traverse(current);
    return data;
  }
}

function prettyLog(title, result) {
  console.log();
  console.log(title);
  console.log(result);
  console.log();
}

const tree = new BinarySearchTree();
tree.insert(10);
tree.insert(6);
tree.insert(15);
tree.insert(3);
tree.insert(8);
tree.insert(20);
prettyLog("DFS-PreOrder", tree.DFSPreOrder());
prettyLog("DFS-PostOrder", tree.DFSPostOrder());
prettyLog("DFS-InOrder", tree.DFSInOrder());

 

 

Q. BFS(너비 우선 탐색) 와 DFS(깊이 우선 탐색)는 언제 사용되는가?

 

Q. BFS(너비 우선 탐색) 와 DFS(깊이 우선 탐색) 중 어떤 것을 사용해야 하는가? 

트리에 따라 다르다. (시간복잡도는 같으나 공간복잡도가 다르다.)

 

완전히 넓게 펴진 상태로 아래까지 뻗어 나가는 트리

BFS -> 모든 노드를 저장하기 위해 Queue 를 사용해야 한다. (공간복잡도가 크다.)

DFS -> BFS와 달리 모든 노드를 저장할 필요가 없다. (공간복잡도가 작다.)

 

한쪽으로 치우쳐져 아래까지 뻗어 나가는 트리

BFS -> 메모리에서 사용되는 공간이 거의 없다. (큐에 한개 이상의 요소가 들어가지 않기 때문)

DFS -> 처리하고 있는 레벨 위의 모든 레벨들이 다 메모리에 저장되어야 해서 메모리 사용을 많이 한다.

 

Q. DFS에서 어떤 종류를 언제 사용해야 하는가?

InOrder (정위) : 트리의 모든 노드를 기본 순서로 가져온다. (순서대로 작업할때 유용)

PreOrder (전위) : 트리를 복사하거나 평탄화해서 저장하는 경우 유용하다.

InOrder 의 경우 재구성을 하고자 할 때, 트리의 루트가 무엇인지 잘 모름

(파일이나 DB같은 곳에 저장했다가 연쇄 구조로 다시 만들어낼 때 유용하다.)

 

 

 

정리

- 트리는 비선형 데이터 구조이며, 하나의 루트와 많은 자식 노드들로 구성되어 있다.

- BT(Binary Tree)는 아무런 종류의 값을 가질 수 있지만, 각 노드는 최대 2개의 자식을 가질 수 있다.

- BST (Binary Search Tree)는 BT의 특별한 종류의 트리이다. 부모의 왼쪽에 있는 모든 노드는 부모보다 작고, 오른쪽에 있는 모든 노드는 크다. -> BST는 비교가 가능한 데이터 종류에만 사용할 수 있다.

 

 

 

 

본 내용은 작성자가 (Udemy) JavaScript 알고리즘 & 자료구조 마스터클래스 강의를 듣고 정리 및 메모한 내용입니다.  오역 및 오개념이 있을 수 있으니 바로잡기 위해 문제가 있는 경우 댓글 남겨주시면 매우 감사하겠습니다.

https://www.udemy.com/course/best-javascript-data-structures/

JavaScript (JS) Algorithms and Data Structures Masterclass