@blog.justoneplanet.info

二分探索木とは二分木と同じ構造で、左の子＜親＜右の子となっているものですな。

■二分探索木に対する挿入

以下のようにして、二分探索木（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)となる