[10] [알고리즘 - 자료구조] 트리(tree)란? (비선형구조) javascript 구현

트리(tree)란?

 

나무가 하나의 뿌리에서 줄기가 나와

가지로 나누어지는 것처럼

나무를 거꾸로 뒤집어 놓은 형태로,

자료가 가지처럼 나뉘어서 계속 뻗어 나가는

계층구조를 트리 구조라고 합니다.

 

루트노드(root node) - 부모가 없는 최상위 노드

부모노드(parent node) - 노드에 연결된 한 단계 상위 레벨 노드

형제노드(sibling node) - 같은 부모를 가지는 노드

단말노드(leaf node) - 자식이 없는 노드

높이(height) - 깊이 최댓값

크기(size) - 모든 노드의 개수

깊이(depth) - 루트 노드로부터의 거리

차수(degree) - 각 노드의 간선 개수

레벨(level) - 노드의 특정 깊이를 가지는 노드의 집합

* 전체 간선의 개수는 (트리가 N개 일 때) N - 1 개

 

---

트리 종류

 

 

---

이진트리 탐색

 

이진트리의 모든 노드를 방문하는 것 혹은

방문하여 어떤 작업을 하는 것을 이진 트리 탐색이라고 합니다.

1. in-order(중위 순회) : 왼쪽 자식 노드(L), 내 노드(P), 오른쪽 자식노드(R) 순서로 방문.
2. pre-order(전위 순회) : 내 노드(P), 왼쪽 자식노드(L), 오른쪽 자식노드(R) 순서로 방문.
3. post-order(후위 순회) : 왼쪽 자식노드(L), 오른쪽 자식 노드(R), 내 노드(P) 순서로 방문.
4. level-order(레벨 순회) : 내 노드(P), 내 노드로부터 깊이 1인 노드들, 내 노드로부터 깊이 2인 노드들,... , 내 노드로부터 깊이 N인 노드들 (N: 나(트리)의 깊이)

 

---

이진 탐색 트리

 

값을 찾는 것에 특화된 자료구조로써

특정한 조건을 가진 이진트리입니다.

 

쉽게 말해서,

이진 트리에 값을 추가할 때,

비교하여

왼쪽에는 작은 값,

오른쪽에는 큰 값을

넣음으로써,

값을 찾을 때 정말 빠르게 찾을 수

있도록한이진트리입니다.

 

이를 javascript로 구현을 해봅시다.

 

class BSTNode {
    constructor(data, left = null, right = null) {
        this.data = data;
        this.left = left;
        this.right = right;
    }
}

 

우선 먼저 이진트리 노드를 정의해주겠습니다.

 

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

    // 현재 트리 불러오기
    get() {
        return this.root;
    }
    // 트리 데이터 추가
    add(data) {
        const node = this.root;
        // 최초 등록일 경우
        if (node === null) {
            this.root = new BSTNode(data);
            return;
        } else { // 이미 데이터가 존재 하는 경우
            
            const addTree = (node) => {
                if (data < node.data) { // 노드의 값보다 작은 값인 경우 왼쪽
                    if (node.left === null) {
                        node.left = new BSTNode(data);
                        return;
                    } else if (node.left !== null) {
                        return addTree(node.left); // 재귀 호출
                    }
                } else if (data > node.data) { // 노드의 값보다 큰 값인 경우 오른쪽
                    if (node.right === null) {
                        node.right = new BSTNode(data);
                        return;
                    } else if (node.right !== null) {
                        return addTree(node.right); // 재귀 호출
                    }
                } else {
                    return null;
                }
            };

            return addTree(node);
        }
    }

    // 가장 낮은 값 찾기
    // 가장 왼쪽에 존재하는 단말 노드
    findMin() {
        let current = this.root;
        while (current.left !== null) {
            current = current.left;
        }
        return current.data;
    }

    // 가장 높은 값 찾기
    // 가장 오른쪽에 존재하는 단말 노드
    findMax() {
        let current = this.root;
        while (current.right !== null) {
            current = current.right;
        }
        return current.data;
    }

    // 값 찾기
    find(data) {
        let current = this.root;
        while (current.data !== data) {
            // 탐색 데이터가 낮을 경우 왼쪽부터 탐색
            if (data < current.data) {
                current = current.left;
            } else {
                current = current.right;
            }
            // 존재하지 않으면 null
            if (current === null) {
                return null;
            }
        }
        return current;
    }

    // 존재여부 확인
    isPresent(data) {
        let current = this.root;
        while (current) {
            // 탐색 데이터가 낮을 경우 왼쪽부터 탐색
            if (data === current.data) {
                return true;
            }
            if (data < current.data) {
                current = current.left;
            } else {
                current = current.right;
            }
        }
        return false;
    }

    // 값 삭제
    remove(data) {
        const removeNode = (node, data) => {
            // 데이터가 비어있는 경우 처리 X
            if (node == null) return null;

            // 값을 찾은 경우 삭제 처리
            if (data == node.data) {

                // case1 단말 노드인 경우
                if (node.left == null && node.right == null) {
                    return null;
                }
                // case2 왼쪽 자식이 없는 경우
                if (node.left == null) {
                    return node.right;
                }
                // case3 오른쪽 자식이 없는 경우
                if (node.right == null) {
                    return node.left;
                }
                // case4 왼쪽 오른쪽 자식이 모두 있는 경우
                var tempNode = node.right;
                while (tempNode.left !== null) {
                    tempNode = tempNode.left;
                }
                node.data = tempNode.data;
                node.right = removeNode(node.right, tempNode.data);
                return node;
            } 
            // 작은 값인 경우 왼쪽
            else if (data < node.data) {
                node.left = removeNode(node.left, data);
                return node;
            } 
            // 큰 값인 경우 오른쪽
            else {
                node.right = removeNode(node.right, data);
                return node;
            }
        }
        this.root = removeNode(this.root, data);
    }
}

add에 대해서는 별로 어렵지 않습니다.

먼저 root 노드부터 값을 비교하며

작으면 왼쪽 노드로,

값이 크면 오른쪽 노드로

반복하여 마지막 값이 없는 것을

찾을 때까지 확인하면 됩니다.

 

반면에 삭제의 경우는

4가지의 경우를 생각해봐야 합니다.

 

1(단말 노드), 2(오른쪽 자식 존재), 3(왼쪽 자식 존재) 번 케이스 인경우

그대로 데이터만 삭제 또는 위로 당겨주면 됩니다.

 

반면에, case 4처럼 아래로 자식이 모두 있을 경우에

오른쪽 자식의 가장 작은 데이터와 자리를

변경해주면 됩니다.

 

 

이다음은

중위 순회, 전위 순회, 후위 순회, 레벨 순회를

각각 구현해보겠습니다.

 

/* 중위 순회 */
    // 왼쪽, 나, 오른쪽 순서로 방문
    inOrder() {
        
        if (this.root == null) return null; 
        else {
            let result = [];

            const traverseInOrder = (node) => {
                // 왼쪽이 존재하는 경우, 현재 노드를 기준 재귀
                node.left && traverseInOrder(node.left);
                // 현재 노드 push
                result.push(node.data);
                // 오른쪽이 존재하는 경우, 현재 노드를 기준 재귀
                node.right && traverseInOrder(node.right);
            }
            traverseInOrder(this.root);
            return result;
        };
    }

    /* 전위 순회 */
    // 나, 왼쪽, 오른쪽 순서로 방문
    preOrder() {
        if (this.root == null) return null;  
        else {
            let result = [];
            const traversePreOrder = (node) => {
                // 방문 하는 대로 나 자신 push
                result.push(node.data);
                // 왼쪽이 존재하는 경우, 현재 노드를 기준 재귀
                node.left && traversePreOrder(node.left);
                // 오른쪽이 존재하는 경우, 현재 노드를 기준 재귀
                node.right && traversePreOrder(node.right);
            };
            traversePreOrder(this.root);
            return result;
        };
    }

    /* 후위 순회 */
    // 왼쪽, 오른쪽, 나 순서로 방문
    postOrder() {
        if (this.root == null) return null; 
        else {
            let result = [];
            const traversePostOrder = (node) => {
                // 왼쪽이 존재하는 경우, 현재 노드를 기준 재귀
                node.left && traversePostOrder(node.left);
                // 오른쪽이 존재하는 경우, 현재 노드를 기준 재귀
                node.right && traversePostOrder(node.right);
                // 마지막으로 나 자신 push
                result.push(node.data);
            };
            traversePostOrder(this.root);
            return result;
        }
    }

    /* 레벨 순회 */
    // 루트, 1레벨 노드, 2레벨 노드 순서로 방문
    levelOrder() {
        let result = [];
        let temp = [];
        if (this.root == null) return null;
        else {
            temp.push(this.root);
            while (temp.length > 0) {
                const node = temp.shift(); // 첫 번째 요소 제거 후 반환
                result.push(node.data); // 루트 값 작성
                // 왼쪽 노드가 있는 경우
                if (node.left != null) temp.push(node.left);
                // 오른쪽 노드가 있는 경우
                if (node.right != null) temp.push(node.right);
            };
            return result;
        }
    };

 

 

이제 그림처럼 값을 넣어 넣고

확인을 한번 해보겠습니다!

 

const bst = new BST();

bst.add(30);
bst.add(25);
bst.add(59);
bst.add(42);
bst.add(16);
bst.add(29);
bst.add(62);
bst.add(65);
bst.add(6);
bst.add(18);
bst.add(27);

console.log('inOrder: ' + bst.inOrder());
// inOrder: 6,16,18,25,27,29,30,42,59,62,65
console.log('preOrder: ' + bst.preOrder());
// preOrder: 30,25,16,6,18,29,27,59,42,62,65
console.log('postOrder: ' + bst.postOrder());
// postOrder: 6,18,16,27,29,25,42,65,62,59,30
console.log('levelOrder: ' + bst.levelOrder());
// levelOrder: 30,25,59,16,29,42,62,6,18,27,65

bst.remove(6);

console.log('inOrder: ' + bst.inOrder());
// inOrder: 16,18,25,27,29,30,42,59,62,65
console.log('preOrder: ' + bst.preOrder());
// preOrder: 30,25,16,18,29,27,59,42,62,65
console.log('postOrder: ' + bst.postOrder());
// postOrder: 18,16,27,29,25,42,65,62,59,30
console.log('levelOrder: ' + bst.levelOrder());
// levelOrder: 30,25,59,16,29,42,62,18,27,65

잘 나오네요!

 

 

자료구조 트리에서

이진트리가 가장 중요하며,

이진트리에서도 값을 활용한

이진 탐색 트리를 통해서

프로그래밍해보았습니다.

 

트리의 종류도 다양하고,

활용도 정말 폭넓기 때문에

천천히 지속적으로 계속 생각하며

사고력을 넓혀야 할 것 같습니다.