Skybuck Flying
2023-02-17 21:31:36 UTC
Problem description:
Each computer has it's own binary tree. (Merkle Hash Tree).
The computers want to communicate with each other. However each BinaryTree can grow in number of nodes, size, height, etc.
Still the computers want to communicate with each other.
They want to address each other's node data, the same data basically, each node has data.
I can imagine two solutions for this problem:
1. Either a stable numbering system/scheme in which each node keeps the same number as it moves through the tree as it grows.
or
2. A translation algorithm, which translates the node number from one tree to the other tree.
It is possible to compute node numbers mathematical/virtually without memory consumption that would be ideal, for example by using formulas.
The objective is to keep communication to a minimum and to keep the ammount of memory used also to a minimum.
So it would be preferered if both trees are completely "virtual" in math basically.
Not sure if translation is possible, most likely yes, there are many ways to do it, the easiest way is to simply allocate all nodes and traverse the nodes and record it's traversal path and then send the traversal path to the other computer. Maybe this could be used, many not, maybe it's flawed.
Another way would be to do some kind of lookup table.
Or a combination of math.
Basically the information given/available for the tree would ideally be limited to the basic information about the tree, not the nodes:
structure for TBinaryTree
private
mRoot : TTreeNode;
mTotalNumberOfNodes : uint64;
end;
The height could be computed from this total number of nodes as well.
Now the final objective:
Write a routine which can convert a BinaryTreeNodeNumber to another BinaryTreeNodeNumber.
routine TranslateNodeNumber( in TBinaryTree A, in TBinaryTree B, in NodeNumberA, out NodeNumberB )
Developed an algorithm, implement it in your favorate language and post it here !
(You can also ask ChatGPT to see if it can generate it for you ! ;))
Bye for now,
Skybuck.
Each computer has it's own binary tree. (Merkle Hash Tree).
The computers want to communicate with each other. However each BinaryTree can grow in number of nodes, size, height, etc.
Still the computers want to communicate with each other.
They want to address each other's node data, the same data basically, each node has data.
I can imagine two solutions for this problem:
1. Either a stable numbering system/scheme in which each node keeps the same number as it moves through the tree as it grows.
or
2. A translation algorithm, which translates the node number from one tree to the other tree.
It is possible to compute node numbers mathematical/virtually without memory consumption that would be ideal, for example by using formulas.
The objective is to keep communication to a minimum and to keep the ammount of memory used also to a minimum.
So it would be preferered if both trees are completely "virtual" in math basically.
Not sure if translation is possible, most likely yes, there are many ways to do it, the easiest way is to simply allocate all nodes and traverse the nodes and record it's traversal path and then send the traversal path to the other computer. Maybe this could be used, many not, maybe it's flawed.
Another way would be to do some kind of lookup table.
Or a combination of math.
Basically the information given/available for the tree would ideally be limited to the basic information about the tree, not the nodes:
structure for TBinaryTree
private
mRoot : TTreeNode;
mTotalNumberOfNodes : uint64;
end;
The height could be computed from this total number of nodes as well.
Now the final objective:
Write a routine which can convert a BinaryTreeNodeNumber to another BinaryTreeNodeNumber.
routine TranslateNodeNumber( in TBinaryTree A, in TBinaryTree B, in NodeNumberA, out NodeNumberB )
Developed an algorithm, implement it in your favorate language and post it here !
(You can also ask ChatGPT to see if it can generate it for you ! ;))
Bye for now,
Skybuck.