의사결정트리 (decision tree)란? #

결정 트리(decision tree)는 의사 결정 규칙과 그 결과들을 트리 구조로 도식화한 의사 결정 지원 도구의 일종이다. 결정 트리는 운용 과학, 그 중에서도 의사 결정 분석에서 목표에 가장 가까운 결과를 낼 수 있는 전략을 찾기 위해 주로 사용된다. wiki 의사결정트리

역추적 알고리즘의 의사결정트리 #

3개의 수 [1, 2, 3]이 주어지고 이 수들의 순열을 찾을때 역추적 알고리즘의 의사결정트리를 사용 할 수 있습니다.

위 UML은 backtracking의 의사결정트리입니다. 순열을 처음 계산할 때 손으로 만들던 그 트리와 비슷합니다.

해당 트리는 루트 노드에서부터 트리를 순회하고 경로를 숫자로 기록합니다.

배열의 길이가 3이므로 트리의 레벨은 출발점부터 계산하면 레벨 3까지 총 길이는 4가 되겠습니다.

이를 의사결정트리라고 부르는 이유는 각 트리의 노드에서 의사결정을 내리기 때문입니다.

노드에서 하위 트리를 생성할 때, 자신이 기록해둔 값들이 "1, 2라면 나머지 3을 하위 트리로 만든다" 라는 의사결정이 각 노드들에서 일어나는 것이 위 순열 문제의 의사결정입니다.

순회 #

순회에는 전위, 중위, 후위 순회가 있습니다.

각 순회의 위치는 root 노드의 방문 순서에 따라 이름 지어졌습니다.

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

const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);

예시를 위해 이진트리를 생성합니다.

트리는 위와 같은 그림을 그리게 됩니다.

// js
function preOrderTraversal(root) {
  if (root === null) {
    return;
  }

  console.log(root.value); // 현재 노드의 값

  preOrderTraversal(root.left); // 왼쪽 노드로
  preOrderTraversal(root.right); // 오른쪽 노드로
}

전위순회 함수인 preOrderTraversal 함수는 현재 방문한 node의 값을 출력합니다.

그리고 왼쪽 하위 트리로 재귀를 실행합니다. 따라서 왼쪽 하위 트리부터 방문을 하면서 기저조건에 닿은 경우 콜스택이 반환되고 그 다음 오른쪽 트리를 방문하게 됩니다.

따라서 1 --> 2 --> 4 --> 5 --> 3의 순서로 방문하게 됩니다.

전위순회는 루트를 가장 먼저 방문하기 때문에 전위입니다.

중위순회는 루트를 중간에 방문하기 때문에 중위순회입니다.

후위순회는 루트를 중간에 방문하기 때문에 후위순회입니다.

따라서 언제 각 노드의 값에 접근하는지에 따라 순회가 결정됩니다.

중위순회 #

// js 
// 중위순회 4 --> 2 --> 5 --> 1 --> 3
function inOrderTraversal(root) {
  if (root === null) {
    return;
  }

  preOrderTraversal(root.left); // 왼쪽 노드로
  console.log(root.value); // 현재 노드의 값
  preOrderTraversal(root.right); // 오른쪽 노드로
}

후위순회 #

// js 
// 후위순회 4 --> 5 --> 2 --> 3 --> 1
function postOrderTraversal(root) {
  if (root === null) {
    return;
  }

  preOrderTraversal(root.left); // 왼쪽 노드로
  preOrderTraversal(root.right); // 오른쪽 노드로
  console.log(root.value); // 현재 노드의 값
}

이렇게 각 순회 방법을 알아봤습니다.

감사합니다.