Last active
August 12, 2023 19:11
-
-
Save kenwebb/a1e37498ab2f56181d1a62c7c96a09e2 to your computer and use it in GitHub Desktop.
Complete Binary Structures
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<?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