참고자료: 컴공 자바스크립트 : 이진트리기법 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()
메서드는 값을 인자로 받고 값의 존재 유무에 따라 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
};
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
};
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
};
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
};