二分木と二分探索木

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

■二分木（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）n_rを含む。節点nは、2つの二分探索木T_lとT_rとを持ち、節点nのキーをkとしたら、T_lのすべてのキーが≦kで、T_rのすべてのキーが≧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ﾟ▽ﾟ)♡

TrackBack URL :

Comments (0)

@blog.justoneplanet.info