이진탐색트리 with 자바스크립트

참고자료: 컴공 자바스크립트 : 이진트리기법 Part 1

이진탐색트리는 계층적 트리구조로 되어있다.
첫 번째 item이 root node가 되고 그 다음 추가적인 값들은 root node의 자식으로 들어간다. 대신 규칙이 있다.

root node의 왼쪽 자식은 항상 부모보다 작은 값이어야한다. 또 오른쪽 자식은 부모보다 항상 값이 커야한다. 따라서 이진탐색트리에서는 값을 찾기가 쉽다 -> 부모보다 작은 값을 찾으려면 왼쪽에서 찾으면되고 큰 값을 찾으려면 오른쪽에서 찾으면 된다.

중복값은 이진탐색트리의 관계도에 문제가 생기므로 절대 올수 없다.

이진탐색트리를 이용해서 아래와 같은 기능을 하는 함수들을 구현해보자.

function BinarySearchTree() {
    this._root = null;
}

BinarySearchTree.prototype = {

    //restore constructor
    constructor: BinarySearchTree,

    add: function (value){
    },

    contains: function(value){
    },

    remove: function(value){
    },

    size: function(){
    },

    toArray: function(){
    },

    toString: function(){
    }

};

contains()

contains() 메서드는 값을 인자로 받고 값의 존재 유무에 따라 boolean값을 리턴한다.

BinarySearchTree.prototype = {

    //more code

    contains: function(value){
        var found       = false,
            current     = this._root

        //make sure there's a node to search
        while(!found && current){

            //if the value is less than the current node's, go left
            if (value < current.value){
                current = current.left;

            //if the value is greater than the current node's, go right
            } else if (value > current.value){
                current = current.right;

            //values are equal, found it!
            } else {
                found = true;
            }
        }

        //only proceed if the node was found
        return found;
    },

    //more code

};

add()

containes() 접근 방식을 이용해서 add() - 새로 value를 추가하는 것을 할 수 있다. contains()와 다른 것은 이진트리에서 해당값을 찾는 것이 아니라 새로운 값이 들어갈 자리를 찾는 다는 것!!

BinarySearchTree.prototype = {

    //more code

    add: function(value){
        //create a new item object, place data in
        var node = {
                value: value,
                left: null,
                right: null
            },

            //used to traverse the structure
            current;

        //special case: no items in the tree yet
        if (this._root === null){
            this._root = node;
        } else {
            current = this._root;

            while(true){

                //if the new value is less than this node's value, go left
                if (value < current.value){

                    //if there's no left, then the new node belongs there
                    if (current.left === null){
                        current.left = node;
                        break;
                    } else {
                        current = current.left;
                    }

                //if the new value is greater than this node's value, go right
                } else if (value > current.value){

                    //if there's no right, then the new node belongs there
                    if (current.right === null){
                        current.right = node;
                        break;
                    } else {
                        current = current.right;
                    }       

                //if the new value is equal to the current one, just ignore
                } else {
                    break;
                }
            }
        }
    },

    //more code

};

traverse() - 이진탐색트리 순회방식

1. 전위 순회(Preorder Traversal): root -> left -> right
2. 중위 순회(Inorder Traversal): left -> root -> right
3. 후위 순회(Postorder Traversal): left -> right -> root

BinarySearchTree.prototype = {

    //more code

    traverse: function(process){

        //helper function
        function inOrder(node){
            if (node){

                //traverse the left subtree
                if (node.left !== null){
                    inOrder(node.left);
                }            

                //call the process method on this node
                process.call(this, node);

                //traverse the right subtree
                if (node.right !== null){
                    inOrder(node.right);
                }
            }
        }

        //start with the root
        inOrder(this._root);
    },

    //more code

};

size(), toArray(), toString()

traverse()함수를 활용하여 다음 함수들을 만들 수 있다.

BinarySearchTree.prototype = {

    //more code

    size: function(){
        var length = 0;

        this.traverse(function(node){
            length++;
        });

        return length;
    },

    toArray: function(){
        var result = [];

        this.traverse(function(node){
            result.push(node.value);
        });

        return result;
    },

    toString: function(){
        return this.toArray().toString();
    },

    //more code

};