0
$\begingroup$

Usually we use the tree data structure when we care about time complexity for ins/del/...

-In this special case problem, space saving is mandatory too that is 2 pointers for each node is unaffordable; actual data are in leaves so infact even the internal nodes are considered overhead

-So, I thought of storing it as a 2D array with variable row size, we can assume the tree is almost always full complete power of 2, something like

R[0]= N leaf nodes

R[1]= N/2 level-1 nodes

R[2]= N/4 nodes

.. ..

R[logN]= root

-I can derive the formulas for del/ins/... as the tree is easily mind-vewable from this presentation, without any pointers at all.

-Now, did I miss something???

-Is there any flaw in this?

-I'm checking for brainstorming or some opinions.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ If a dynamic structure is not necessary, why not just use an array for the leaf nodes? $\endgroup$
    – Yehuda Klein
    Sep 12, 2021 at 7:26
  • $\begingroup$ The tree is necessary to augment a hash function on the leaves, I'm talking about a Merkle Tree where hashes are stored in the leaves & accumulated above; didn't say it explicitly because a previous knowledge of blockchains is not necessary to give a correct answer, in fact could direct your mind to what is usually done there $\endgroup$
    – ShAr
    Sep 12, 2021 at 9:05

2 Answers 2

Reset to default
1
$\begingroup$

Whether or not this is an efficient representation depends on what the binary tree means. A heap (in the priority queue sense) uses precisely this idea to represent a binary tree with an array.

The situation would be a little more difficult if you needed to implement, say, a dynamic binary search tree this way. A full binary search tree represented as an array is essentially the same thing as a sorted array.

Improve this answer
$\endgroup$
3
  • $\begingroup$ The real data are just on the leaf nodes, and appended to the right; to be specific, I'm talking about a way to store Merkle Tree of hashes. This way I save 2N pointers of the internal node hashes, and this way insertion/deletion/proof extraction are all the same difficulty; it's known to be noisy & annoying whether to adjust pointers normally to facilitate ins/del and then suffer in proof extraction, or to direct them to what is called niece/aunt depending on the direction to facilitate proof fetching then be careful & visualize in ur head to do ins/del with pointers not directed normally. $\endgroup$
    – ShAr
    Sep 12, 2021 at 8:45
  • $\begingroup$ This way I don't need any niece or aunt, the proof is fetched thru a simple loop, after fetching the 1st sibling R[0, i+drct], just the loop: For(j=1; j≤logN; j++) { index= i/(2^j)+drct; proof[i]=Add(R[j,index]); } ("drct" is the direction left or right could be viewed as IsEven?). Some methods work on just full trees, but even if not completing the tree to next power of2 is always less than adding 2N $\endgroup$
    – ShAr
    Sep 12, 2021 at 8:59
  • $\begingroup$ I should have added in the 1st Comment that this has nothing to do with heaps; Internal nodes (in my presentation R[i≥1]) are a function of their children not necessarily larger or smaller in value. The Q is whether I missed something, a flaw in the presentation or possibility/time of any operation? $\endgroup$
    – ShAr
    Sep 12, 2021 at 20:27
0
$\begingroup$

I think I found a confirmation to my method from this MIT lecture about heaps (although it is not heaps the solution, but it is mentioned in the lecture) From PDF lecture 8 in here https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-spring-2020/lecture-notes/index.htm

You can find he specifically says when we want to save the pointers space of a full binary tree, we can store it as an array & access it using the following equations enter image description here

Only, I made it variable size 2D array to make it more easy to visualize the tree view, besides it's more easier to fetch proofs this way; a detail specific to our problem

(and reversed their order, in my presentation R[0] contain the leaves, in his representation R[0] is the root), and thus my equations are just a little different, but the idea is still the same enter image description here

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.