[Udemy] Tree 순회 - BFS, DFS 이란?

정의

BFS(Breadth First Search), 너비 우선 탐색은 트리 자료구조에서 순회 시

루트노드에서 부터 시작하여 하위 노드들로 이동할 때, 같은 레벨에 있는 노드들부터 순회하는 방법을 말한다.

 

DFS(Depth First Search), 깊이 우선 탐색은 트리 자료구조에서 순회 시

루트노드에서 부터 시작하여 가장 리프 노드까지 먼저 순회하는 방법을 말한다.

DFS에서는 순회시 후위 순회, 전위 순회, 중위 순회 방법이 있다.

 

 

BFS 구현

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

class BinarySearchTree {
    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;
            } else {
                if (current.right === null) {
                    current.right = newNode;
                    return this;
                }
                current = current.right;
            }
        }
    }

    BFS() {
        if (!this.root) return [];
        let visited = [];
        let queue = [];
        queue.push(this.root);
        
        while (queue.length) {
       	    let node = queue.shift();
            visited.push(node.value);
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        return visited;
    }
}

 

BFS는 큐(Queue) 자료구조를 사용하면 쉽게 구현할 수 있다.

 

1. 순회한 요소들을 저장하는 visited 배열 생성

2. 다음 순회할 요소들을 저장하는 queue 배열 생성

3. 루트 노드를 queue에 추가

4. dequeue한 노드 queue가 left, right 있으면 queue에 left, right 노드 추가

5. 4번 과정을 queue가 빈 배열일 때까지 반복 순회

 

이진 검색 트리

 

 

1. visited = [47], queue = [ ]

2. 47 노드의 left(15), right(74) 존재하니 queue = [15, 74]

3. visited = [47, 15] queue = [74]

4. 15 노드의 right(21) 존재하니 queue = [74, 21]

5. visited = [47, 15, 74], queue = [21]

6. 74 노드의 left(68), right(83) 존재하니 queue = [21, 68, 83]

7. visited = [47, 15, 74, 21], queue = [68, 83]

8. 리프노드이므로 visited = [47, 15, 74, 21, 68, 83]

 

 

만약 이진 검색 트리가 아니라면 ?

위 예시에선 이진 검색 트리를 기준으로 BFS를 구현했지만,

자식 노드가 여러개인 모든 트리구조에서도 큐(queue) 자료구조를 사용한 BFS를 구현할 수 있다.

 

class Node {
    constructor(value) {
        this.value = value;
        this.children = []; // 자식 노드를 배열로 저장
    }
}

class GeneralTree {
    constructor() {
        this.root = null;
    }
    
    // 자식 노드를 추가하는 메서드
    addChild(parentNode, value) {
        const newNode = new Node(value);
        parentNode.children.push(newNode);
        return newNode;
    }

    // BFS 메서드
    BFS() {
        let visited = [];
        let queue = [];
        let node = this.root;
        queue.push(node);

        while(queue.length) {
            node = queue.shift();
            visited.push(node.value);
            node.children.forEach(child => queue.push(child)); // 모든 자식 노드를 큐에 추가
        }
        return visited;
    }
}

 

만약, 자식 노드가 여러개여서 Node 기본 프로퍼티로 children이라는 배열을 가진다면,

left, right만 추가해주는 것이 아닌 Node의 children 배열의 모든 요소를 순차적으로 queue에 추가해주면 된다.

 

 

 

DFS 구현

DFS는 전위 순회, 후위 순회, 중위 순회 총 3가지 방법으로 순회할 수 있다.

한 가지 순회 방법만 알면 나머지는 코드 1줄의 순서만 바꾸면 되므로 겁먹지 말자.

 

 

전위 순회

전위 순회는 최상위 노드부터 가장 깊은 노드를 탐색할 때,

거쳐가는 노드를 우선적으로 방문하는 순회방법이다.

class BinarySearchTree {
    ... 생략

    DFS_preOrder() {
        let visited = [];

        function traverse(node) {
            visited.push(node);
            if (node.left) traverse(node.left);
            if (node.right) traverse(node.right);
        }
        traverse(this.root);
        return visited;
    }
}

 

1. 방문한 노드를 저장하는 visited 배열 생성

2. 노드를 순회할 재귀 helper 함수 생성

3. 재귀 helper 함수에서 노드를 visited에 추가하고 left 노드부터 재귀함수 호출

4. left 노드 순회 끝나면 이어서 right 노드 재귀 순회

 

이진 검색 트리

 

1. visited = [47]

2. 47 노드의 left(15) 노드 재귀 호출

    1. visited = [47, 15]

    2. 15 노드의 right(21) 노드 재귀 호출

        1. visited = [47, 15, 21]

        2. 재귀 종료

    3. 재귀 종료

3. 47 노드의 right(74) 노드 재귀 호출

    1. visited = [47, 15, 21, 74]

    2. 74 노드의 left(68) 노드 재귀 호출

        1. visited = [47, 15, 21, 74, 68]

        2. 재귀 종료

    3. 74 노드의 right(83) 재귀 호출

        1. visited = [47, 15, 21, 74, 68, 83]

        2. 재귀 종료

    4. 재귀 종료

4. 재귀 종료

 

 

후위 순회

후위 순회는 가장 최하단 노드 부터 순회하는 방법이다.

전위 순회의 순서 약간만 변형 하면 된다.

DFS_postOrder() {
        let visited = [];

        function traverse(node) {
            if (node.left) traverse(node.left);
            if (node.right) traverse(node.right);
            visited.push(node);
        }
        traverse(this.root);
        return visited;
    }

 

visited = [21, 15, 68, 83, 74, 47]

 

중위 순회

중위 순회는 왼쪽 노드 우선 최하단 까지 순회한 뒤 오른쪽 노드 순회하는 방법이다.

DFS_inOrder() {
        let visited = [];

        function traverse(node) {
            if (node.left) traverse(node.left);
            visited.push(node);
            if (node.right) traverse(node.right);
        }
        traverse(this.root);
        return visited;
    }

 

visited = [15, 21, 47, 68, 74, 83]

 

 

BFS, DFS는 언제 사용해야 할까?

BFS, DFS 둘다 모든 요소를 순회해야하므로 시간복잡도는 O(n)이다.

하지만 이 둘의 공간 복잡도는 상황에 따라 다를 수 있다.

 

예를 들어, 너비가 넓은 트리구조를 보자.

너비가 큰 트리

위와 같이 너비가 큰 트리구조에서 BFS를 사용할 경우, queue에 저장해야할 자식 노드들이 많아져

공간 복잡도가 늘어나 더 많은 메모리를 차지한다.

 

하지만 위 경우에서 DFS를 사용할 경우 재귀를 통해 진행하기 때문에

공간 복잡도는 크지 않다.

 

전위 순회, 후위 순회, 중위 순회는 왜 알아야할까?

사실 이를 구분해서 사용하는 경우는 많지 않다. 알아두면 좋기 때문이다.

그래도 이유를 생각해보자면,

 

중위 순회의 경우 정렬된 이진 검색 트리를 반환 시 정렬을 유지하여 반환하므로 이해하기 쉽다.

전위 순회의 경우, DB에 배열로 저장 후 나중에 다시 트리 자료구조로 변환 시 루트 노드부터 시작하기 때문에

트리 구조로 전환 시 용이하다는 장점이 있다.

 

 

참조

Udemy - Js 알고리즘 & 자료구조 강의