[알고리즘] 트리(Tree)와 트리 순회 , 백준 5639

이번엔 트리 순회에 대해 알아보겠습니다.

⭐️ 트리란 무엇인가 ?

트리는 나무를 거꾸로 뒤집어 놓은 모양과 같아서 트리라는 이름이 지어졌는데요.
트리란 노드들이 연결된 비선형 계층적 자료구조입니다. 하나의 루트 (root) 노드에서 시작하여 여러 개의 자식 노드를 가질 수 있는 구조를 말합니다. 트리는 트리 내에 다른 하위 트리가 있고 , 그 하위 트리 안에는 또 다른 하위 트리가 있는 재귀적 자료 구조이기도 합니다.

⭐️ 트리의 종류

트리에도 많은 종류들이 있습니다.

1. 이진 트리 (Binary Tree)
이진 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리입니다. 각 노드는 최대 한 개의 부모 노드를 가집니다.

이미지 출처

이진 트리에도 여러 가지 종류가 있는데요.

1) 정 이진 트리 (Full Binary Tree) : 모든 트리의 자식은 0개나 2개입니다.
2) 완전 이진 트리 (Complete Binary Tree) : 마지막 레벨을 제외한 모든 레벨이 완전히 채워진 트리입니다. (모든 노드가 왼쪽으로 밀려 있습니다.)
3) 포화 이진 트리 (Perfect Binary Tree) : 모든 리프 노드의 높이가 같고 , 리프 노드가 아닌 노드는 모두 2개의 자식을 갖습니다.

이미지 출처

2. 이진 탐색 트리 (Binary Search Tree)
이진 탐색 트리는 모든 노드가 특정한 순서로 정렬되어 있습니다. 각 노드는 왼쪽 서브 트리의 모든 노드의 값보다 크고 , 오른쪽 서브 트리의 모든 노드의 값보다 작습니다. 이러한 정렬된 구조 덕분에 데이터의 검색 시간은 O(log n)입니다.

• BST 구현 코드

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

class BinaryTree {
    constructor() {
        this.root = null;
    }

    insert(value) {
        const newNode = new Node(value);
        if (this.root === null) {
            this.root = newNode;
            console.log(newNode);
            console.log("root설정");
        } else {
            this.insertNode(this.root, newNode);
        }
    }
    // 재귀로 돌아가는 구조
    insertNode(node, newNode) {
        if (newNode.value < node.value) {
            if (node.left === null) {
                node.left = newNode;
            } else {
                this.insertNode(node.left, newNode);
            }
        } else {
            if (node.right === null) {
                node.right = newNode;
            } else {
                this.insertNode(node.right, newNode);
            }
        }
    }
    
    searchNode(node, value) {
        if (node === null) {
            return false;
        }

        if (value < node.value) {
            return this.searchNode(node.left, value);
        } else if (value > node.value) {
            return this.searchNode(node.right, value);
        } else {
            return true;
        }
    }
}

const tree = new BinaryTree();
tree.insert(10);
tree.insert(5);
tree.insert(15);
tree.insert(3);
tree.insert(7);

트리에 있는 값들을 알아보기 위해서 트리를 순회할 수 있는데 ,root 노드의 방문 순서에 따라 크게 3가지의 순회 방법이 있습니다.
1) 전위 순회 (pre-order) : root를 먼저 방문
2) 중위 순회 (in-order) : 왼쪽 하위 트리 - root - 오른쪽 하위 트리
3) 후위 순회 (post-order): 왼쪽 하위 트리 - 오른쪽 하위 트리 - root

이 트리 구조로 순회 방법에 대한 예시를 들어보겠습니다.
1) 전위 순회 : 8-3-1-6-4-7-10-14-13
2) 중위 순회 : 1-3-4-6-7-8-10-13-14
3) 후위 순회 : 1-4-7-6-3-13-14-10-8

⭐️ 백준 5639번 : 이진 검색 트리

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

class BST {
    constructor() {
        this.root = null;
    }

    insert(value) {
        const newNode = new Node(value);
        if (this.root === null) {
            this.root = newNode;
        } else {
            this.insertNode(this.root, newNode);
        }
    }
    insertNode(curNode, newNode) {
        if (newNode.value < curNode.value) {
            if (curNode.left === null) {
                curNode.left = newNode;
            } else {
                this.insertNode(curNode.left, newNode);
            }
        } else {
            if (curNode.right === null) {
                curNode.right = newNode;
            } else {
                this.insertNode(curNode.right, newNode);
            }
        }
    }
    getRoot() {
        return this.root;
    }
	// preOrder과 inOrder은 console.log(node.value)의 순서만 바꿔주면 됨.
    postOrder(node) {
        if (node.left) this.postOrder(node.left);
        if (node.right) this.postOrder(node.right);
        console.log(node.value);
    }
}

function solution(input) {
    const preOrder = input.slice();

    // 트리를 구성한 후 , postOrder 진행
    const bst = new BST();
    for (let i = 0; i < preOrder.length; i++) {
        bst.insert(preOrder[i]);
    }
    const root = bst.getRoot();

    bst.postOrder(root);
}

const rl = require("readline").createInterface({
    input: process.stdin,
    output: process.stdout,
});

const input = [];
rl.on("line", (line) => {
    input.push(parseInt(line));
}).on("close", () => {
    solution(input);
    process.exit();
});

트리 구조에는 이 외에도 AVL 트리 (Adelson-Velsky and Landis Tree -> 발명자 이름) 자가 균형 이진 탐색 트리 , 레드 블랙 트리 (Red Black Tree) , B 트리 (B-Tree) 등의 트리 종류가 있습니다.