@blog.justoneplanet.info

日々勉強

二分木と二分探索木

意思の疎通が上手くいかなかったりするので、ちゃんと区別したい。で記事にした。゜(´□`。)°゜

■二分木(binary tree)

各ノードの子要素が2以下で通常は左と右と呼ばれる。

var BT = function(value){
    var self = this;
    self._left  = null;
    self._right = null;
    self.value = value;
    self.appendChild = function(child, location){
        if(location === 'left' && self._left === null){
            self._left = child;
            return true;
        }
        else if(location === 'right' && self._right === null){
            self._right = child;
            return true;
        }
        else{
            return false;
        }
    }
}

// test code
var root  = new BT(5);
var leaf1 = new BT(7);
var leaf2 = new BT(2);
var leaf3 = new BT(10);
var leaf4 = new BT(6);
var leaf5 = new BT(1);
var leaf6 = new BT(8);

root.appendChild(leaf1, 'left');
root.appendChild(leaf2, 'right');

leaf1.appendChild(leaf3, 'left');
leaf1.appendChild(leaf4, 'right');
leaf2.appendChild(leaf5, 'left');
leaf2.appendChild(leaf6, 'right');

console.log(root);
console.log(JSON.stringify(root));

■二分探索木(binary search tree)

二分木の一種だが要素の大小に『left < parent < right』という順序が成立する。

var BST = function(value){
    var self = this;
    self._left  = null;
    self._right = null;
    self.value = value;
    self.appendChild = function(child){
        if(child.value < self.value){
            if(self._left){
                self._left.appendChild(child);
            }
            else{
                self._left = child;
            }
        }
        else{
            if(self._right){
                self._right.appendChild(child);
            }
            else{
                self._right = child;
            }
        }
    }
}

// test code
var root  = new BST(5);
var leaf1 = new BST(7);
var leaf2 = new BST(2);
var leaf3 = new BST(10);
var leaf4 = new BST(6);
var leaf5 = new BST(1);
var leaf6 = new BST(8);

root.appendChild(leaf1);
root.appendChild(leaf2);
root.appendChild(leaf3);
root.appendChild(leaf4);
root.appendChild(leaf5);
root.appendChild(leaf6);

console.log(root);
console.log(JSON.stringify(root));

つまり要素の大小関係に基づいて位置が決まるのがbinary search treeであって、binary treeではないよね。ちなみに以前はめんどいから配列で実装した。配列で実現することも可能だが、木が平衡でない場合に無駄な空きができてしまう。

■文献

まぁ、色々読んだほうが早いかもしれん。

Binary tree

Binary trees are commonly used to implement binary search trees and binary heaps.

Binary search tree

In computer science, a binary search tree (BST) or ordered binary tree is a node-based binary tree data structure which has the following properties:[1]

  • The left subtree of a node contains only nodes with keys less than the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.
  • Both the left and right subtrees must also be binary search trees.

アルゴリズムクイックリファレンス(p143)

二分探索木Tは、順序特性を持つ、すなわちキーによって識別される節点の有限集合となる。節点集合は空でなければ、根節点(root node)nrを含む。節点nは、2つの二分探索木TlとTrとを持ち、節点nのキーをkとしたら、Tlのすべてのキーが≦kで、Trのすべてのキーが≧kであるという性質を保持する。この性質は、二分探索木の性質(binary-search-tree property)と呼ばれる(Cormen et al., 2001)。

■canvas

つーかさ、console.logで確認するのめんどいよね!そういうわけでcanvasで表示させます。

var BST = function(value){
    var self = this;
    self._left  = null;
    self._right = null;
    self.value = value;
    
    /**
     * appendChild
     * @param {Object} child
     */
    self.appendChild = function(child){
        if(child.value < self.value){
            if(self._left){
                self._left.appendChild(child);
            }
            else{
                self._left = child;
            }
        }
        else{
            if(self._right){
                self._right.appendChild(child);
            }
            else{
                self._right = child;
            }
        }
    }
    
    /**
     * draw
     * @param {Object} context
     * @param {int} left
     * @param {int} top
     * @param {int} center
     * @param {int} depth
     */
    self.draw = function(context, left, top, center, depth){
        if(self._left !== null){
            var cl = left - (center / Math.pow(2, depth + 1));
            var ct = top + 50
            context.fillStyle = 'black';
            context.beginPath();
            context.moveTo(left, top);
            context.lineTo(cl, ct);
            context.stroke();
            var lp = self._left.draw(context, cl, ct, center, depth + 1);
        }
        if(self._right !== null){
            var cl = left + (center / Math.pow(2, depth + 1));
            var ct = top + 50
            context.fillStyle = 'black';
            context.beginPath();
            context.moveTo(left, top);
            context.lineTo(cl, ct);
            context.stroke();
            var lp = self._right.draw(context, cl, ct, center, depth + 1);
        }
        context.fillStyle = 'red';
        context.beginPath();
        context.arc(left, top, 10, 0, Math.PI * 2, false);
        context.fill();
        
        context.font = "15px Arial bold";
        context.textAlign = "center";
        context.textBaseline = "middle";
        context.fillStyle = 'white';
        context.fillText(self.value, left, top, 30);
        return {"left" : left, "top" : top};
    }
}

// test code
var root  = new BST(5);
root.appendChild(new BST(7));
root.appendChild(new BST(2));
root.appendChild(new BST(10));
root.appendChild(new BST(6));
root.appendChild(new BST(1));
root.appendChild(new BST(8));
root.appendChild(new BST(12));
root.appendChild(new BST(11));
root.appendChild(new BST(9));
root.appendChild(new BST(4));
root.draw(document.getElementById("canvas").getContext('2d'), 200, 50, 200, 0);

おや、まぁ、なんと素敵なことでしょう!(o゚▽゚)♡

JavaScriptで二分探索木

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

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

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

JavaScriptでハッシュに基づいた探索

■実装

var a =  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19];

/**
 * hash
 * ハッシュ関数
 * 解説用に衝突しやすい関数を使用
 * @param {int} x
 */
var hash = function(x){
    return x % 5;// tableのサイズを5とした(=メモリに応じたサイズ)
}

/**
 * setTable
 * 要素のハッシュ値をキーにした配列に変換
 * @param {Array} ary
 */
var setTable = function(ary){
    var table = [];
    for(var i = 0; i < a.length; i++){
        var key = hash(a[i]);
        if(!table[key]){// 衝突した場合
            table[key] = [];// 通常は連結リストを使用するが簡略化のため配列を使用
            table[key].push(a[i]);// (要素の追加・削除の用途が多いので)
        }
        else{
            table[key].push(a[i]);
        }
    }
    return table;
}

/**
 * search
 * 探索用関数
 * @param {Array} table
 * @param {int} elm
 */
var search = function(table, elm){
    var key = hash(elm);// 要素のハッシュ値を求めてハッシュテーブルから探索する
    if(table[key]){
        for(var i = 0; i < table[key].length; i++){
            if(table[key][i] === elm){
                return true;
            }
        }
        return false;
    }
    else{
        return false;
    }
};


var table = setTable(a);
console.log(JSON.stringify(table));// [[0,5,10,15],[1,6,11,16],[2,7,12,17],[3,8,13,18],[4,9,14,19]]
console.log(search(table, 6));// true
console.log(search(table, 39));// false

■特性

  • 最良時と平均時の計算コストはO(1)
  • 最悪時は全ての要素のハッシュ値が衝突した場合で線形時間の探索が必要になりO(n)

■ポイント

  • ハッシュ関数には性能が良く衝突が少ないものを使う
  • 衝突は起こるものとして考える

■参考

文字列のハッシュ値の計算として以下のようなものもあるらしい。

var key = function(str){
    var hash = 0;
    for(var i = 0; i < str.length; i++){
        hash += Math.pow(31, str.length - i - 1) * str[i].charCodeAt(0);
    }
    return hash;
}

しかし上述の関数でも20万語を通すと衝突が発生し、最大で7単語が衝突する。

JavaScriptで二分探索

集団が予め整列されている時の探索。

■実装

var a =  [0, 3, 6, 9, 12, 15, 18, 21, 24, 27];


var search = function(ary, elm){
    low  = 0;
    high = ary.length - 1;
    while(low <= high){
        var i = Math.floor((low + high) / 2);
        if(ary[i] === elm){
            return i;
        }
        else if(ary[i] > elm){
            high = i - 1;
        }
        else{
            low = i + 1;
        }
    }
    return -1;
};


console.log(a.toString());
console.log(search(a, 6));

■特性

  • 電話帳や名簿など予め整列された集合に対して有用である
  • 最良時にO(1)、平均と最悪時の計算コストはO(log n)となる

JavaScriptでシーケンシャル探索

■実装

まぁ、簡単すぎるけど一応書いておく。

var n = 10;
var a = [];
for(var i = 0; i < n; i++){
    a[i] = Math.round(Math.random() * n);
}


var search = function(ary, elm){
    for(var i = 0; i < ary.length; i++){
        if(ary[i] === elm){
            return i;
        }
    }
    return -1;
};


console.log(a.toString());
console.log(search(a, 5));

■特性

  • 整列していない要素の少ない配列に対して有効
  • 殆どの場合で-1を返すような場合、違ったアルゴリズムを検討するべき
  • 最良時は配列の先頭に要素がある場合で計算量はO(1)
  • 最悪時は配列の最後尾に要素がある場合で計算量はO(n)
  • 平均すると配列の中央まで探索することになり計算量はO(n)
  • 探索が成功した場合に要素を先頭や最後尾に移動させることにより、複数回の探索時の性能をあげられる可能性がある