트리 순회(Tree Traversal)

트리 순회란?

트리 순회는 어떤 트리에서든 사용 가능한 개념이다. 트리 내의 모든 노드를 한 번씩 방문할 수 있도록 하는 알고리즘이다. 이러한 트리를 한 번씩 돌 수 있는 방법에는 네 가지 방법이 있다.

1. 너비우선탐색 BFS(Breadth First Search)

루트 노드부터 시작해서 아래로 내려가면서 같은 레벨에 있는 모든 노드들을 가로질러서 거쳐가는 방식이다.

구현

  // 기존 BST에서 탐색하는 BFS이므로 BST 클래스의 메서드로 추가
  BFS() {
    // 탐색하면서 움직이는 점 node
    var node = this.root,
      // 탐색 경로를 저장하는 data 배열
      data = [],
      // 앞으로 탐색할 곳을 담아놓는 queue 배열
      queue = [];
 
    queue.push(this.root);
    // queue 배열이 빌 때까지 계속 반복해서 탐색
    // 빈 배열은 참의 값을 가지므로 length가 0일 때 falthy값을 가지는 것을 이용
    while (queue.length) {
      node = queue.shift();
      data.push(node.val);
      // 왼쪽과 오른쪽에 탐색할 수 있는 노드가 있으면 모두 queue에 넣음
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    return data;
  }

2. 깊이우선탐색 DFS(Depth First Search)

깊이우선 탐색은 내가 처음 탐색하는 노드에서부터 계속 끝까지, 즉 수직으로 트리의 끝까지 들어갔다가 더 이상 탐색할 노드가 없다면 나오고, 탐색할 노드가 있다면 다시 돌아가 똑같이 탐색을 계속 안으로 파고들며 재귀적으로 탐색하는 알고리즘이다. 수평으로 탐색을 하는 너비 우선 탐색(BFS)와는 탐색 방식 자체가 다르다.

깊이우선 탐색에는 탐색 순서에 따라 세 가지로 나뉠 수 있다. 탐색 순서의 이름은 가운데, 즉 루트 노드의 위치가 어떤 순서에 오는지에 따라 전위순회, 후위순회, 중위순회로 나뉘어진다.

2-1. 전위 탐색(PreOrder)

전위 탐색은 가장 처음 노드에 접근한 이후에 왼쪽 서브트리를 재귀적으로 전위순회하고 오른쪽 서브트리를 재귀적으로 전위순회하는 식으로 탐색한다.

구현

  DFSPreOrder() {
    // 방문한 노드를 저장하는 배열인 visited
    var visited = [];
    function traverse(node) {
      //방문한 노드에 해당 노드의 값을 추가
      visited.push(node.val);
      // 왼쪽 -> 오른쪽 순서대로 탐색이므로 왼쪽부터 재귀적으로 호출
      if (node.left) traverse(node.left);
      if (node.right) traverse(right);
    }
    // 루트노드부터 탐색을 시작하여 재귀적으로 파고들며 탐색
    traverse(this.root);
    return visited;
  }

2-2. 후위 탐색(PostOrder)

후위 탐색은 가장 왼쪽 서브트리를 재귀적으로 후위순회하고 오른쪽 서브트리를 재귀적으로 후위순회한 뒤 마지막으로 루트 노드를 후위탐색하는 순으로 탐색한다.

구현

  DFSPostOrder() {
    // 방문한 노드를 저장하는 배열인 visited
    var visited = [];
    function traverse(node) {
      // 왼쪽 -> 오른쪽 순서대로 탐색이므로 왼쪽부터 재귀적으로 호출
      if (node.left) traverse(node.left);
      if (node.right) traverse(right);
      //후위순위는 마지막에 루트 노드를 추가
      visited.push(node.val);
    }
    // 루트노드부터 탐색을 시작하여 재귀적으로 파고들며 탐색
    traverse(this.root);
    return visited;
  }

2-3. 중위 탐색(InOrder)

중위 탐색은 왼쪽 서브트리를 재귀적으로 중위순회한 뒤에 루트 노드를 거쳐 오른쪽 서브트리로 간 뒤 오른쪽 서브트리를 재귀적으로 중위순회하는 식으로 탐색한다.

구현

  DFSInOrder() {
    // 방문한 노드를 저장하는 배열인 visited
    var visited = [];
    function traverse(node) {
      // 왼쪽 -> 오른쪽 순서대로 탐색이므로 왼쪽부터 재귀적으로 호출
      // 다른 문법을 사용했을 뿐 if문과 작동 방식은 같음
      node.left && traverse(node.left);
      // 중위순위는 중간에 루트 노드의 값을 추가한 뒤에 오른쪽 서브트리로 이동하여 재귀적으로 탐색
      visited.push(node.val);
      node.right && traverse(right);
    }
    // 루트노드부터 탐색을 시작하여 재귀적으로 파고들며 탐색
    traverse(this.root);
    return visited;
  }

BFS와 DFS중 무엇이 더 나은 알고리즘인가?

결론부터 말하자면 상황에 따라 다르다. 즉, 트리의 형태에 따라 사용하는 알고리즘의 효율적인 면에서 차이가 발생하게 되는 것이다.

사실 시간복잡도적인 측면에서는 같을 수밖에 없다. 트리 순회라는게 어찌 됐든간에 모든 노드를 방문해야 순회이기 때문에 결국 방문하는데 드는 시간 복잡도는 같지만 공간복잡도적인 측면에서 효율성이 갈릴 수 있다.

BFS의 경우

위와 같은 그림을 보면 노드의 수는 2배만큼 계속 증가한다. 지금은 얼마 없지만 2의 거듭제곱은 기하급수적으로 증가하기 때문에 레벨이 깊어질수록 노드의 수는 매우 많아진다.

만약 이런 트리 구조에 모든 노드가 꽉 차있는 형태가 된다면 BFS로 탐색을 할 때 모든 바로 아래 모든 노드를 배열에 저장한 뒤 하나씩 빼가면서 찾게 되는데, 여기서 쓰이는 공간복잡도 또한 기하급수적으로 늘어나게 된다.

따라서 공간복잡도적인 측면에서 이러한 형태의 트리는 BFS가 효율적이지 못하다.

DFS의 경우

DFS의 경우에는 전에 말했던 노답 이진트리처럼 한 줄로 이어져있는 이진트리가 효율적이지 못하다. 여기서는 깊이 우선 탐색을 하게 될 경우 무조건 계속 끝 레벨까지 재귀적으로 호출하면서 그 전 레벨까지는 모두 메모리에 저장되어 있어야 하기 때문에 공간복잡도적인 측면에서 효율성이 떨어진다.

이러한 트리에 BFS 탐색을 할 경우엔 계속해서 하나의 노드만 배열에 들어가고 탐색을 진행하기 때문에 메모리에서 사용되는 공간이 거의 없어 공간복잡도적인 측면에서 효율적이다.

DFS에서 서로 다른 종류의 탐색을 언제 시행해야 하는가?

사실 여기에도 명확한 답은 없다. 상황에 따라 다를 뿐이다

중위순회(Inorder)의 경우

중위순회의 경우 트리의 값들을 오름차순으로 정렬할 때 유용하게 쓰인다. DFS는 이진탐색트리, 즉 BST 트리에 쓰이는 탐색 방법이므로 탐색을 할 때 왼쪽-중앙-오른쪽 순이 곧 오름차순이기 때문이다.

전위순회(Preorder)의 경우

전위순회의 경우 트리를 복사하거나 평탄화해서 파일이나 데이터베이스 등에 저장하는 경우에 유용하게 사용될 수 있다. 순서대로 자식을 똑같은 전위순회 식으로 넣어주면 다시금 트리를 구성하기 용이해진다.