The properties of a complete tree lead to a very efficient storage mechanism using n sequential locations in an array.
-
An important benefit of the array representation is that we can move around the tree, from parent to children or from child to parent, by simple arithmetic. If we number the nodes from 1 at the root then
- the left and right children of node
i, if they are present, are at 2i and 2i+1
- the parent of node
i is at i/2 (truncated to an integer)
If items is the array, the root corresponds to Items[1]; subsequent slots in the array store the nodes in each consecutive level from left to right.
- In a Java implementation, it is convenient to leave
Items[0] unused. With this numbering of nodes, the children of the node Items[i] can be found in Items[2*i] and Items[2*i+1], and the parent of Items[i] is in Items[i/2].
