二分探索木とは二分木と同じ構造で、左の子＜親＜右の子となっているものですな。
■二分探索木に対する挿入
以下のようにして、二分探索木（Binary Search Tree）に対する挿入を実装してみた。linked listで再現したほうがイメージしやすい気もするがコード量は増えるので配列を使用した。
Array.prototype.bpush = function(elm){
var ary = this;
var push = function(elm, key){
if(!ary[key]){
ary[key] = elm;
}
else{
if(elm < ary[key]){// left child
push(elm, 2 * key + 1);
}
else{// right child
push(elm, 2 * key + 2);
}
}
}
push(elm, 0);
}
var bst = [];
bst.bpush(5);
bst.bpush(7);
bst.bpush(8);
bst.bpush(3);
console.log(bst);// [5, 3, 7, undefined, undefined, undefined, 8]// ex1
var bst = [];
bst.bpush(7);
bst.bpush(2);
bst.bpush(5);
bst.bpush(1);
console.log(bst);// [7, 2, undefined, 1, 5]// ex2
var bst = [];
bst.bpush(1);
bst.bpush(2);
bst.bpush(3);
bst.bpush(4);
console.log(bst);// [1, undefined, 2, undefined, undefined, undefined, 3, undefined, undefined, undefined, undefined, undefined, undefined, undefined, 4]// ex3
ソート済みの配列を格納した場合、上述ex3に見られるように線形リストとなり下述の探索性能が下がる。
■探索
上述で生成した二分探索木を探索するアルゴリズムを実装した。
Array.prototype.bpush = function(elm){
var ary = this;
var push = function(elm, key){
if(!ary[key]){
ary[key] = elm;
}
else{
if(elm < ary[key]){// left child
push(elm, 2 * key + 1);
}
else{// right child
push(elm, 2 * key + 2);
}
}
}
push(elm, 0);
}
Array.prototype.bsearch = function(elm){
var ary = this;
var search = function(elm, key){
if(!ary[key]){
return -1;
}
if(elm === ary[key]){
return key;
}
else{
if(elm < ary[key]){
return search(elm, 2 * key + 1);
}
else{
return search(elm, 2 * key + 2);
}
}
}
return search(elm, 0);
}
var bst = [];
bst.bpush(5);
bst.bpush(7);
bst.bpush(8);
bst.bpush(3);
console.log(bst);// [5, 3, 7, undefined, undefined, undefined, 8]
console.log(bst.bsearch(3));// 1
var bst = [];
bst.bpush(7);
bst.bpush(2);
bst.bpush(5);
bst.bpush(1);
console.log(bst);// [7, 2, undefined, 1, 5]
console.log(bst.bsearch(3));// -1
var bst = [];
bst.bpush(1);
bst.bpush(2);
bst.bpush(3);
bst.bpush(4);
console.log(bst);// [1, undefined, 2, undefined, undefined, undefined, 3, undefined, undefined, undefined, undefined, undefined, undefined, undefined, 4]
console.log(bst.bsearch(3));// 6
まぁこんな感じ。前述の通りex3は線形リストのシーケンシャル探索と同じとなり性能が低下する。従って、要素の挿入と削除に対して、ツリーの平衡を維持するようなロジックを導入する必要がある。代表的なものとして赤黒木などがある。
■特性
- 最悪時の計算コストはO(n)。平均時はO(log n)となる