2
$\begingroup$

So I know that arrays use a block on contiguous memory addresses to store data to memory, and lists (not linked lists) make use of static arrays and when data is appended to the list, if there is no room, a new static array is created elsewhere in memory larger in size so more data can be stored.

My question is, how do binary trees use memory to store data? Is each node a memory location which points to two other memory locations elsewhere...not necessarily contiguous locations? Or are they stored in contiguous blocks of memory too like a static array or dynamic list?

$\endgroup$
  • 4
    $\begingroup$ This highly depends on the implementation, most languages don't even have predefined trees. If you make them using classes/structs with references to child nodes your first guess would be fitting, but you could also interpret an array as binary tree, storing one level of the tree after the other. $\endgroup$ – Benjoyo Jul 2 '15 at 8:31
  • $\begingroup$ You may want to google "succinct data structures". $\endgroup$ – Raphael Jul 2 '15 at 9:18
  • 2
    $\begingroup$ I suggest reading Knuth's The Art of Computer Programming, Volume 1 for a good pragmatic understanding of the low level implementation details of numerous algorithms. $\endgroup$ – Jim Balter Aug 2 '15 at 19:19
3
$\begingroup$

We use implicit array representation to store Binary Heaps, where if a node has an index $i$, its children are found at indices $2i + 1$ (for the left child) and $2i +2$ (for the right), assuming indices start at 0.

Now this is not wasteful for Binary Heaps since nodes are added in Breadth First method. However for normal Binary Trees implicit array representation is very expensive to grow and wastes space in the order of $O(2^h)$ where $h$ is the height of the tree (Consider skewed binary trees).

For trees having a large number of nodes we use Succint Data Structures as pointed out by Raphael. A normal binary tree of $n$ nodes is stored using $O(nlogn)$ bits (pointer representation), but succinct representations require just $2n + o(n)$ bits and carry out many sophisticated operations in constant time. This link gives us a good overview of a simple representation of succint representations.

$\endgroup$

Your Answer

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

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