[ Data Structures with Java ] Section 22.1 : Array-Based Binary Trees

Preface : 
In Chapter 16, we build binary trees by using tree nodes. Each node has a data value and left/right references that identify the left and right subtrees of the node. Insertions and deletions involve allocating nodes and assigning the references to the subtrees. This representation handles trees ranging from degenerate to complete trees. In this section, we introduce a tree that uses an array to store the data and indices to identify the nodes. We use the termarray-based tree to describe the data structure. We can derive a very powerful relationship between the array and a complete binary tree. 
Recall from Chapter 16 that a complete binary tree of depth d contains all possible nodes through level d-1 and that nodes at level d occupy the leftmost positions in the tree. We can view an array arr, with its indexed structure, as a complete binary tree. The root is arr[0], the first level children are arr[1] and arr[2] and so forth. Below figure illustrates a 10-elements array viewed as a complete tree : 
 

The power of array-based trees becomes evident then an application requires access to node data. There are simply index calculations that identify the children and the parent of nodes. For each node arr in an [i]n-element array, the following formulas compute the indices of the child nodes and parent node as well : 
 

Note that we can start at any node and move up the tree along the path of parents until we arrive at the root. This feature was not available with TNode implementation of a binary tree. An STree collection with its STNode objects could scan the path of parents by using the parent reference field. 
Below is a example demonstrating the formula : 
Example 22.1 
Let us see how these index calculations apply to the array-based tree. 
1. The root is arr[0] with value 5. Its left child has index 2*0 + 1 = 1 and its right child has index 2*0+2 = 2. The values for the children are arr[1] = 1 and arr[2] = 3 
2. Start at the root and select the path of left children : 

root index = 0
left child of arr[0] has index = 2 * 0 + 1 = 1
left child of arr[1] has index = 2 * 1 + 1 = 3
left child of arr[3] has index = 2 * 3 + 1 = 7
left child of arr[7] has index = 2 * 7 + 1 = 15 which is undefined (15 >= 10)

The path of left child is : arr[0]=5, arr[1] = 1, arr[3] = 9, arr[7] = 7. 
3. To identify the path of parents from any node arr, evaluate successive parent indices as (i-1)/2. Assume we start at arr[8] = 0. Successive parent indices are : 

(8-1)/2 = 3
(3-1)/2 = 1
(1-1)/2 = 0, which is root

The path of parents starting at arr[8] is arr[8] = 0, arr[3] = 9, arr[1] = 1, arr[0] = 5 

We can associate with any array a binary tree representation. In general, the representation is not useful because the values that happen to be sorted in the array may not match the tree structure in a meaningful way. In section 22.3, we will organize an array by placing an ordering on its elements. The resulting array, called a heap, is best illustrated as a binary tree. A heap has very efficient inserting and deletion operations. We will use the array as the underlying storage structure for an implementation of the priority queue. The heap ordering will be exploited to create a fast sort algorithm called the heapsort.