1
$\begingroup$

This describes how one can neatly store a binary search tree as an array. I'm looking for a way to store a BST that will allow me to traverse any root to leaf path by loading $\mathcal{O}(log_kn)$ blocks. I call a bunch of nodes a block, the blocks are of size $k$.

My goal is to store a perfectly balanced binary search tree with $n$ nodes as an array and be able to traverse any root to leaf path in a small number of steps. To achieve this I want to read blocks of $k$ elements and upon seeing those $k$ elements I should be able to decide where in the array I need to read the next $k$ elements from. I want to repeatedly read $k$ elements and traverse from root to leaf node in such a way that everytime I read $k$ elements I know where to move next inside of the array. A larger $k$ would mean more "branches" and a smaller number of steps. This sounds like a B-tree to me.

I want to store a perfectly balanced binary search tree as an array but in such a way that I can traverse any root to leaf path by loading $\mathcal{O}(log_kn)$ blocks.

Such an approach minimizes the number of blocks read and can be used to minimize memory accesses which is my final goal.

Does anyone have any resources where I could learn more about or how could I approach this?

$\endgroup$
  • $\begingroup$ I'm not sure asking for recommendations on resources, books, tutorials, etc. is on-topic here. Also, doesn't the fact that you can go from root node at position $i$ to child node at positions $2i$ and $2i + 1$ already give you the paths you're looking for? I'm not sure if I'm following what you're trying to get at. $\endgroup$ – code_dredd Oct 9 '17 at 9:12
  • $\begingroup$ Usually, in asymtotics, base of logarithm is excluded (since it does not make sence). $\endgroup$ – rus9384 Oct 9 '17 at 9:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.