0
$\begingroup$

This question already has an answer here:

I have been struggling to visualize how is the AVL tree is stored in memory? Does it store data in array or list, If so how is it connected with its child and parents.

$\endgroup$

marked as duplicate by Evil, Yuval Filmus, Juho, Rick Decker, Kyle Jones Nov 1 '17 at 18:21

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

2
$\begingroup$

If I wanted to be really pedantic, the question would be unanswerable, as it depends on the particular implementation.

In most cases, however, the individual nodes of the tree are stored in one sequential chunk of memory that's allocated by whatever method your system/language provides (most common being malloc and/or new), each containing the key and the two pointers to child nodes, either of which can be a special value NULL, if a child is not present.

The individual nodes are usually scattered around the memory, with no clear relation between how/where they are located. We leave this for the memory allocator of the environment to handle. When we allocate a new node, we place its address (a pointer to it) in an existing node (or, as a special case, in the root pointer), so we can navigate to it.

Think of this as a linked list, where each item can have not only one, but two successors.

$\endgroup$

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