October 8th, 2011, 06:26 PM
Binary Tree Array
I've suggested a data structure I call a Binary Tree Array:
I think it's novel but if anyone recognises it I would be interested in knowing.
Also I vaguely recognize the 'sweet problem' in the form of a 'Viking problem' or maybe a 'Roman soldier decimation problem' or something. The difference is that instead of passing a sweet a death sentence is passed and the question is where should you position yourself in the original lineup to be the last man standing walking away unharmed.
So maybe there's a known optimal solution?
Last edited by nuzzle; October 8th, 2011 at 08:39 PM.
October 11th, 2011, 02:20 AM
Re: Binary Tree Array
Further more to the BTA data structure in my previous post. An example. Say you have an array with 8 elements. Initially the binary tree would look like this,
2 2 2 2
1 1 1 1 1 1 1 1
The numbers reflect the number of array elements below each node of the tree. To remove an array element, say the fifth, you set the corresponding 1 in the leaf row to 0 and adjust all parent nodes accordingly, like
2 2 1 2
1 1 1 1 0 1 1 1
This makes array element removal an O(log N) operation.
To move M elements forward in the array you walk upwards in the tree from the current element until you find a node where the right child has M elements or more. Then from there you follow the path downwards that results in skipping M elements. You end up M elements away from the current element. Moving M elements backward is analogical. So moving M elements away from the current position is an O(log N) operation.
The BTA data structure allows the 'sweet problem' to be solved with O(N * log N) complexity. A solution may look like this,
0 1 0 0
0 0 0 1 0 0 0 0
The root node indicates there's just one element left in the array. Following the path of ones down from the root to the leaf level reveals the fourth child is the winner.
Last edited by nuzzle; October 20th, 2011 at 04:53 AM.
Click Here to Expand Forum to Full Width