意思の疎通が上手くいかなかったりするので、ちゃんと区別したい。で記事にした。゜(´□`。)°゜
■二分木(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゚▽゚)♡