二分木と二分探索木
意思の疎通が上手くいかなかったりするので、ちゃんと区別したい。で記事にした。゜(´□｀｡)°゜
■二分木（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ﾟ▽ﾟ)♡
TrackBack URL :
Comments (0)