Complete Binary Structures

xholonWorkbook.xml

<?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>