二分探索木とは二分木と同じ構造で、左の子<親<右の子となっているものですな。
■二分探索木に対する挿入
以下のようにして、二分探索木(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)となる