Binary Search Tree에 대한 이해 Javascript

문제

Tree 구현을 위한 기본적인 코드가 작성되어 있습니다. Binary Search Tree 자료구조의 특성을 이해하고 FILL_ME_IN 을 채워 테스트를 통과해주세요.

메소드

• insert(value): 입력받은 value를 Binary Search에 맞게 Tree에 계층적으로 추가할 수 있어야 합니다.
• contains(value): 트리에 포함된 데이터를 찾을 수 있어야 합니다.
• preorder(callback): 전위 순회를 통해 트리의 모든 요소에 callback을 적용할 수 있어야 합니다.
• inorder(callback): 중위 순회를 통해 트리의 모든 요소에 callback을 적용할 수 있어야 합니다.
• postorder(callback): 후위 순회를 통해 트리의 모든 요소에 callback을 적용할 수 있어야 합니다.

주의사항

value는 어떠한 값도 들어갈 수 있지만 현재 구현하는 Tree는 숫자로 제한합니다.

사용 예시

const rootNode = new BinarySearchTree(10);
rootNode.insert(7);
rootNode.insert(8);
rootNode.insert(12);
rootNode.insert(11);
rootNode.left.right.value; // 8
rootNode.right.left.value; //11

let arr = [];
rootNode.preorder((value) => arr.push(value * 2));
arr; // [20, 14, 16, 24, 22]
...

풀이

class BinarySearchTree {
	constructor(value){
    	this.value = value;
        this.left = null;
        this.right = null;
    }
    
    insert(value){
    	if(value < this.value){
        	if(this.left === null){
            	this.left = new BinarySearchTree(value);
            } else {
            	this.left.insert(value);
            }
        } else if(value > this.value){
        	if(this.right === null){
            	this.right = new BinarySearchTree(value);
            } else {
            	this.right.insert(value);
            }
        } else {
        	return false;
        }
    }
    
    contains(value){
    	if(this.value === value){
        	return true;
        }
        
        if(value < this.value){
        	return !!(this.left && this.left.contains(value));
        }
        
        if(value > this.value){
        	return !!(this.right && this.right.contains(value));
        }
        return false;
    }
    
    // 전위 순회 (preorder);
    preorder(callback){
    	callback(this.value);
        if(this.left){
        	this.left.preorder(callback);
        }
        if(this.right){
        	this.right.preorder(callback);
        }
    }
    
    // 중위 순회 (inorder)
    inorder(callback){
    	if(this.left){
        	this.left.inorder(callback);
        }
        callback(this.value);
        if(this.right){
        	this.right.inorder(callback);
        }
    }
    
    // 후위 순회 (postorder);
    postorder(callback){
    	if(this.left){
        	this.left.postorder(callback);
        }
        if(this.right){
        	this.right.postorder(callback);
        }
        callback(this.value);
    }
}

특정값을 빠르게 찾을 수 있는 이진 탐색 트리입니다.
root(노드)에서 하위 노드로 계층 구조를 갖는 것을 트리라고 봅니다.

이진 탐색 트리에서는 root(노드)를 기준으로 작은 값(value)의 경우 왼쪽 하위 노드로, 큰 값(value)는 오른쪽 하위 노드가 됩니다. 이때 기준은 this.value입니다.