Binary Trees/ArrayBinTree

Array memory structure binary tree

Notes

We can number the positions sequentially according to their level - called level numbering. This is a function of position as follows.

If p is the root of the tree, then f(p) = 0.

If p is the left child of position q, then f(p) = 2 f(q) + 1.

If p is the right child of position q, then f(p) = 2 f(q) + 2.

Level numbering is based on potential position in the tree, so tree nodes may not all be consecutive.

Advantages

Why an array-based representation? Position can be represented by the single integer f(p)

Position based methos like root, parent, left, and right can be implemented using simple arithmetic

Left child of p has index 2f(p) + 1, the right child of p has index 2 f(p) + 2, parent has index (f(p)-1)/2

Disadvantages

Space usage is not great - there may be a number of empty cells that do not refer to existing nodes of T. The maximum number of "empty" slots for nodes can be as high as $N=2^{n}-1$, an exponential cost.

For general binary trees, the exponential worst-case space requirements of array-based representations are prohibitive.

Deleting an node and promoting its child takes O(n) time because it is not just the child that moves locations within the array, but all descendants o that child.