트리 순회(Tree traversal)

• 트리의 모든 노드를 순회하는 2가지 방법(이진탐색트리뿐만 아니라 트리 전반에 대한 방법)
  • Breadth-frist Search(BFS, 너비우선탐색)
  • Depth-first Seacrh(DFS, 깊이우선탐색)
• 본 포스팅에서 살펴볼 트리 순회 코드는 16. 이진탐색트리 포스팅에 적은 BinarySearchTree 클래스 코드를 기반으로 한 메서드다. 만약 삼진 트리를 다룬다면, Node 클래스 costructor에 this.left, this.right 뿐만 아니라 this.mid 같은 프로퍼티를 하나 더 추가해야 할 것이고, 트리 순회 메서드에서도 this.mid에 대해서도 다루는 알고리즘을 추가해야 한다. 아무튼 이번 포스팅에서는 이진탐색트리를 기반으로 트리 순회에 대해 살펴본다.

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

class BinarySearchTree {
  constructor() {
    this.root = null;
  }
	// 메서드 생략, Insert 메서드 등은 이진탐색트리 포스팅에서 확인
}

1. BFS(너비우선탐색)

• 루트부터 시작하고 기본적으로 트리를 가로질러서 작업한다.

  BFS() {
    // 방문한 노드를 저장할 변수(data)와 queue(배열로도 가능)를 만든다.
    let node = this.root;
    const data = [];
    const queue = [];
    // root 노드를 queue에 넣는다.
    queue.push(node);
    
    // queue에 노드가 있는 동안 루프를 돈다.
    while (queue.length) {
      // queue에서 노드를 dequeue하고
      node = queue.shift();
      // dequeue된 노드의 값을 data에 추가한다.
      data.push(node.value);
      // 만약 dequeue된 노드의 왼쪽 child가 있으면, 그 child를 queue에 추가한고,
      if (node.left) queue.push(node.left);
      // 만약 dequeue된 노드의 오른쪽 child가 있으면, 그 child도 queue에 추가한다.
      if (node.right) queue.push(node.right);
    }
    // 값을 저장한 변수를 return한다.
    return data;
  }

2. DFS(깊이우선탐색)

• 깊이우선탐색의 방향은 트리의 수직 방향이고, 아래로 내려간 다음에 다시 올라온다.
• 깊이우선탐색에는 세 가지 방법이 있다. 모두 재귀를 사용하며, 이 세 가지 방법의 각각의 코드들은 재귀의 헬퍼함수 내에서 data.push(node.value); 한 줄의 위치만 다르고 나머지는 동일한다.
  • PreOrder(전위순회)
  • InOrder(중위순회)
  • PostOrder(후위순회)

2.1. DFS - PreOrder(전위 순회)

DFSPreOrder() {
  // 방문한 노드를 저장하는 변수(data)를 만든다.
  const data = [];
  // 노드를 인수로 받는 재귀의 헬퍼 함수를 만든다.
  function traverse(node) {
    // 방문한 노드의 값을 data 배열에 추가한다.
    data.push(node.value);
    // 방문한 노드의 왼쪽 child가 있으면, 그 child에 대하여 재귀함수를 호출한다.
    if (node.left) traverse(node.left);
    // 방문한 노드의 오른쪽 child가 있으면, 그 child에 대하여 재귀함수를 호출한다.
    if (node.right) traverse(node.right);
  }
  // root 노드부터 재귀함수를 처음으로 호출한다.
  traverse(this.root);
  return data;
}

2.2. DFS - InOrder(중위 순회)

DFSInOrder() {
    const data = [];
    function traverse(node) {
      if (node.left) traverse(node.left);
      data.push(node.value); // 다른 DFS와 비교하면 이 라인의 위치만 다르다.
      if (node.right) traverse(node.right);
    }
    traverse(this.root);
    return data;
  }

2.3. DFS - PostOrder(후위 순회)

DFSPostOrder() {
    const data = [];
    function traverse(node) {
      if (node.left) traverse(node.left);
      if (node.right) traverse(node.right);
      data.push(node.value);  // 다른 DFS와 비교하면 이 라인의 위치만 다르다. 
    }
    traverse(this.root);
    return data;
  }

트리순회 각각의 방법들을 언제 쓰면 좋을까?

• 트리순회 방법 중 BFS와 DFS 중 무엇이 나은가?
  • 상황에 따라 다르다. 각각 장단점이 있다.
    • 일단, BFS나 DFS 모두 모든 노드를 한 번씩 방문하기 때문에, 시간복잡도는 동일하다. 두 방법의 차이점은 공간복잡도에 있다.

• 위와 같이 추적해야 할 노드가 넓게 퍼져서 많은 경우에 BFS(너비우선탐색)을 사용하면, 트리를 가로지르면서 Queue에 데이터를 다 저장해야 해서 결국 많은 데이터가 저장되어 공간복잡도가 높아진다(시간복잡도는 BFS와 DFS가 서로 같아서 상관 없다).

• 반면 위와 같이 동일한 데이터 형태에 DFS(깊이우선탐색)를 사용하면, 트리를 가로지르지 않고 수직으로 내려가며 재귀를 이용하므로 추적해야 하는 노드가 더 적다. 빨간색 점 각각에서 재귀가 발생하여 호출 스택의 한 칸이 된다.
• 즉, 이런 식으로 세로로 깊지 않고 가로로 넓은 트리의 경우에는 DFS(깊이우선탐색)가 BFS(너비우선탐색)보다 더 적은 공간을 점유하므로, DFS를 사용하는 것이 적절하다.
• 반대로 아래 이미지처럼 가로는 좁고 세로로만 아주 깊은 트리라면, BFS(너비우선탐색)가 DFS(깊이우선탐색)보다 더 적은 공간을 점유하므로, BFS를 사용하는 것이 적절하다.

• DFS의 전위, 중위, 후위 탐색을 각각 언제 사용할까?
  • 이진탐색트리에서 DFS-중위 탐색을 하면, 모든 노드가 오름차순 순서대로 나오게 된다. 예를 들어서, 리스트를 받아서 데이터베이스에 넣어야 한다던가 순서대로 무언가 작업을 해야 하는 경우 도움이 될 수 있다. 물론 이진탐색트리에서 가능한 방법이다.
  • DFS-전위 탐색은 root부터 하위 child로 순차적으로 순회하므로, 트리를 외부에 저장했다가 나중에 다시 트리를 그대로 구성해야 하는 경우에 도움이 된다.