Skip to content

Instantly share code, notes, and snippets.

@kenwebb
Last active August 12, 2023 19:11
Show Gist options
  • Save kenwebb/a1e37498ab2f56181d1a62c7c96a09e2 to your computer and use it in GitHub Desktop.
Save kenwebb/a1e37498ab2f56181d1a62c7c96a09e2 to your computer and use it in GitHub Desktop.
Complete Binary Structures
<?xml version="1.0" encoding="UTF-8"?>
<!--Xholon Workbook http://www.primordion.com/Xholon/gwt/ MIT License, Copyright (C) Ken Webb, Sat Aug 12 2023 15:11:05 GMT-0400 (GMT-04:00)-->
<XholonWorkbook>
<Notes><![CDATA[
Xholon
------
Title: Complete Binary Structures
Description:
Url: http://www.primordion.com/Xholon/gwt/
InternalName: a1e37498ab2f56181d1a62c7c96a09e2
Keywords:
My Notes
--------
11 August 2023
This workbook builds and explores Complete Binary Trees (CBT) and other complete binary structures (CBS).
As a first exercise, I will? write a function that transforms a power N of 2 into a CBT with N levels, where the root or top level is level 0.
example: if level == 0, then the leftmost node is 2^0 = 1
level leftmost node
----- -------------
0 2^0 = 1
1 2^1 = 2
2 2^2 = 4
3 2^3 = 8
4 2^4 = 16
5 2^5 = 32
...
// how it will work
var level = 3;
buildBTree(level);
// will build a Xholon Tree out of Nodes
One way to build CBTs, is to use my previous workbook "Path Following Tree Builder - Config A".
This is abbreviated PFTB.
I will first generate a Generating Set from the level number.
Each generating set is a sequence or set of odd numbers, that can be expressed as binary strings, decimal integers, binary numbers, etc.
level generating set (dec) (bin)
----- -------------------- -----
0 1 1
1 3 11
2 5,7 101,111
3 9,11,13,15 1001,1011,1101,1111
4 17, ..., 31 10001,10011,10101,10111,11001,11011,11101,11111
5 100001,100011,100101,100111,101001,101011,101101,101111,110001,110011,110101,110111,111001,111011,111101,111111
6 1000001,1000011,1000101,1000111,1001001,1001011,1001101,1001111,1010001,1010011,1010101,1010111,1011001,1011011,1011101,1011111,1100001,1100011,1100101,1100111,1101001,1101011,1101101,1101111,1110001,1110011,1110101,1110111,1111001,1111011,1111101,1111111
7
...
### 2 different patterns - Why ?
The subtrees obtained by PftbCbt have different patterns from the Node subtrees.
Why is this?
Complete BT vs Complete BS ?
nodes vs paths?
two ways of doing first and next?
perhaps these are two differeent ways of processing the same binary strings?
TODO
- try doing the CBT as a recursive structure
- a Recursion Directed Tree Builder
### References
--------------
(1) https://gist.github.com/kenwebb/8d8fdb1c3c935ffc9c995d4716044398
Path Following Tree Builder - Config A
(2) see my notebook for 7 August 2023
(3) search: javascript complete binary tree builder
(4) https://stackoverflow.com/questions/37419261/how-to-create-a-full-binary-tree-with-specified-depth-in-javascript
see example below
(5)
]]></Notes>
<_-.XholonClass>
<PhysicalSystem/>
<Node/>
<Pftb/>
<PathFollowingTreeBuilder superClass="Script">
<PftbCbt/> <!-- Path Following Tree Builder - Complete Binary Tree -->
<PftbAbc/>
</PathFollowingTreeBuilder>
</_-.XholonClass>
<xholonClassDetails>
<!--<Block>
<port name="height" connector="Height"/>
</Block>-->
<Chameleon><Color>white</Color></Chameleon>
<PhysicalSystem><Color>white</Color></PhysicalSystem>
<Pftb><Color>white</Color></Pftb>
<PftbCbt><Color>yellow</Color><DefaultContent><![CDATA[
var me, arr, ix, nodename, level, bstr, beh = {
postConfigure: function() {
me = this.cnode;
me.println(me.name());
bstr = this.buildgset(me.level);
me.println(`level: ${me.level} bstr: ${bstr}`);
arr = bstr.split(",");
ix = 0;
nodename = "Вузол"; // Ukrainian word for "Node", pronounced "Vuzol"
},
act: function() {
me.println(me.name());
if (ix < arr.length) {
this.buildtree(arr[ix]);
ix++;
}
else {
me.remove();
}
},
buildgset: function(level) {
// hard-code for initial test
//return "1001,1011,1101,1111"; // level 3
var arr = [];
var num1 = Math.pow(2, level) + 1; // first number in the gset
var incr = 2; // increment for each successive number
var numnums = Math.pow(2, level-1); // number of numbers in the gset
for (var i = 0, num = num1; i < numnums; i++, num += 2) {
arr.push(Number(num).toString(2));
}
var gset = arr.join(",");
return gset;
},
buildtree: function(bstr) {
me.println(bstr);
var node = me;
for (var i = 0; i < bstr.length; i++) {
var bit = bstr[i];
switch(bit) {
case "0":
if (!node.first()) {
node.append(`<${nodename} roleName="0"><Color>red</Color></${nodename}>`);
}
node = node.first();
break;
case "1":
if (!node.next()) {
node.after(`<${nodename} roleName="1"><Color>green</Color></${nodename}>`);
}
node = node.next();
break;
default: break;
}
}
}
}
//# sourceURL=PftbCbt.js
]]></DefaultContent></PftbCbt>
<PftbAbc><DefaultContent><![CDATA[
// https://stackoverflow.com/questions/37419261/how-to-create-a-full-binary-tree-with-specified-depth-in-javascript
// Full Binary Tree / complete Binary Tree can be created by using 2 concepts
// Find the Node
// compute the left and right child of the node using 2*i+1, 2*i+2
(() => {
class Node {
constructor(data, left, right) {
this.data = data;
this.left = left;
this.right = right;
}
}
class BinaryTree {
constructor() {
this.root = null
this.storage = [];
}
find = (data, root) => {
if (root) {
this.find(data, root.left);
if (root.data == data) {
this.storage.push(root);
}
this.find(data, root.right);
}
}
insert = (data) => {
if (!this.root) {
this.root = new Node(data[0]);
}
for (let i = 0; i < data.length; i++) {
this.find(data[i], this.root);
let parent = this.storage.pop();
parent.left = new Node(data[2 * i + 1]);
parent.right = new Node(data[2 * i + 2]);
}
}
show = () => {
console.log(this.root);
console.log(JSON.stringify(this.root, null, 2));
}
}
var bt = new BinaryTree();
bt.insert("a"); // 1 item
bt.show();
bt = new BinaryTree();
bt.insert("abc"); // 3 items
bt.show();
bt = new BinaryTree();
bt.insert("abcdefg"); // 7 items
bt.show();
bt = new BinaryTree();
bt.insert("abcdefghijklmno"); // 15 items
bt.show();
bt = new BinaryTree();
bt.insert("abcdefghijklmnopqrstuvwxyzABCDE"); // 31 items
bt.show();
})()
//# sourceURL=PftbCbt.js
]]></DefaultContent></PftbAbc>
<!-- results
{
"data": "a",
"left": {},
"right": {}
}
{
"data": "a",
"left": {
"data": "b",
"left": {},
"right": {}
},
"right": {
"data": "c",
"left": {},
"right": {}
}
}
{
"data": "a",
"left": {
"data": "b",
"left": {
"data": "d",
"left": {},
"right": {}
},
"right": {
"data": "e",
"left": {},
"right": {}
}
},
"right": {
"data": "c",
"left": {
"data": "f",
"left": {},
"right": {}
},
"right": {
"data": "g",
"left": {},
"right": {}
}
}
}
...
-->
</xholonClassDetails>
<PhysicalSystem>
<!-- level 0 has number 2^0 as it's left-most node -->
<Node roleName="1"/>
<!-- level 1 has number 2^1 as it's left-most node -->
<Node roleName="1">
<Node roleName="2"/>
<Node roleName="3"/>
</Node>
<!-- level 2 has number 2^2 as it's left-most node -->
<Node roleName="1">
<Node roleName="2">
<Node roleName="4"/>
<Node roleName="5"/>
</Node>
<Node roleName="3">
<Node roleName="6"/>
<Node roleName="7"/>
</Node>
</Node>
<Pftb>
<PftbCbt level="3"/>
</Pftb>
<Pftb>
<PftbAbc/>
</Pftb>
</PhysicalSystem>
<Blockbehavior implName="org.primordion.xholon.base.Behavior_gwtjs"><![CDATA[
var a = 123;
var b = 456;
var c = a * b;
if (console) {
console.log(c);
}
//# sourceURL=Blockbehavior.js
]]></Blockbehavior>
<Heightbehavior implName="org.primordion.xholon.base.Behavior_gwtjs"><![CDATA[
var myHeight, testing;
var beh = {
postConfigure: function() {
testing = Math.floor(Math.random() * 10);
myHeight = this.cnode.parent();
},
act: function() {
myHeight.println(this.toString());
},
toString: function() {
return "testing:" + testing;
}
}
//# sourceURL=Heightbehavior.js
]]></Heightbehavior>
<Brickbehavior implName="org.primordion.xholon.base.Behavior_gwtjs"><![CDATA[
$wnd.xh.Brickbehavior = function Brickbehavior() {}
$wnd.xh.Brickbehavior.prototype.postConfigure = function() {
this.brick = this.cnode.parent();
this.iam = " red brick";
};
$wnd.xh.Brickbehavior.prototype.act = function() {
this.brick.println("I am a" + this.iam);
};
//# sourceURL=Brickbehavior.js
]]></Brickbehavior>
<Brickbehavior implName="org.primordion.xholon.base.Behavior_gwtjs"><![CDATA[
console.log("I'm another brick behavior");
]]></Brickbehavior>
<SvgClient><Attribute_String roleName="svgUri"><![CDATA[data:image/svg+xml,
<svg width="100" height="50" xmlns="http://www.w3.org/2000/svg">
<g>
<title>Node</title>
<rect id="PhysicalSystem/Node" fill="#98FB98" height="50" width="50" x="25" y="0"/>
<g>
<title>Node</title>
<rect id="PhysicalSystem/Node" fill="#6AB06A" height="50" width="10" x="80" y="0"/>
</g>
</g>
</svg>
]]></Attribute_String><Attribute_String roleName="setup">${MODELNAME_DEFAULT},${SVGURI_DEFAULT}</Attribute_String></SvgClient>
</XholonWorkbook>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment