Binary Search Tree - javascript

이번 글에서는 Binary Search Tree (이진 탐색 트리) 구조에 대하여 알아보고자 한다. 이 글에서는 숫자를 담을 것이고 Node라는 객체 안에다가 저장해서 Node 자체를 넣으려고 한다. 일단 기본 원리에 대하여 살펴보자.

 

아래의 사진은 각 원이 Node이고 각 Node안에 숫자가 담겨 있다. 각 Node 는 key, left, right 이라는 속성을 가지고 있다. "이진" 트리 구조 이여서 각 노드는 최대 다른 두개의 노드를 포인트 할 수 있다. 

주의 깊게 보면 이 구조는 정렬에 최적화된 패턴을 가지고 있다. 각 노드가 포인트 하는 다른 노드들을 보면 왼쪽노드가 그 위의 노드보다 항상 작고 반대로 오른쪽 노드는 항상 크다는 것을 알 수 있다.

 

코드

class Node {

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

}

class BST {

    constructor() {
        this.root = null;
    }

    insert(value) {
        let node = new Node(value);
        if(this.root === null) {
            this.root = node;
            return this;
        }
        let current = this.root;
        while(current){
            if(current.value === value){
                return this;
            }else {
                if(value < current.value){
                    if(current.left === null){
                        current.left = node;
                        return this;
                    }
                    
                    current = current.left;
                    
                }else{
                    if(current.right ===  null) {
                        current.right = node;
                        return this;
                    }

                    current = current.right;
                }
            }
        }
    }

    find(value) {
        if(!this.root) {
            return false;
        }

        let current = this.root;
        let found = false;

        while(current && !found){
            if(value < current.value) {
                current = current.left;
            }else if(value > current.value) {
                current = current.right;
            }else{
                found = current;
            }
        }

        if(!found) return undefined;
        return found;
    }
}


module.exports = BST;

 

root는 최상위 노드이며 가장 먼저 삽입된 노드이다. 이번 예제에서는 insert 와 find 두가지만 구현해보았다.

 

BST(이진 탐색 트리) 구조는 space-time trade off 를 잘보여주는 예시 중 하나이다. 굉장히 빠른 속도로 정렬을 구현 할 수 있지만, 그 만큼 공간적인 타협을 봐야한다.