this section presents simplecompact implementation for complete binary trees recall that complete binary trees have all levels except the bottom filled out completelyand the bottom level has all of its nodes filled in from left to right thusa complete binary tree of nodes has only one possible shape you might think that complete binary tree is such an unusual occurrence that there is no reason to develop special implementation for it howeverthe complete binary tree has practical usesthe most important being the heap data structure discussed in section heaps are often used to implement priority queues (section and for external sorting algorithms (section we begin by assigning numbers to the node positions in the complete binary treelevel by levelfrom left to right as shown in figure (aan array can store the tree' data values efficientlyplacing each data value in the array position corresponding to that node' position within the tree figure (blists the array indices for the childrenparentand siblings of each node in figure (afrom figure ( )you should see pattern regarding the positions of node' relatives within the array simple formulae can be derived for calculating the array index for each relative of node from ' index no explicit pointers are necessary to reach node' left or right child this means there is no overhead to the array implementation if the array is selected to be of size for tree of nodes the formulae for calculating the array indices of the various relatives of node are as follows the total number of nodes in the tree is the index of the node in question is rwhich must fall in the range to parent(rb( )/ if left child( if right child( if left sibling(rr if is even right sibling(rr if is odd and binary search trees section presented the dictionary adtalong with dictionary implementations based on sorted and unsorted lists when implementing the dictionary with an unsorted listinserting new record into the dictionary can be performed quickly by putting it at the end of the list howeversearching an unsorted list for particular record requires th(ntime in the average case for large databasethis is probably much too slow alternativelythe records can be stored in sorted list if the list is implemented using linked listthen no speedup to the search operation will result from storing the records in sorted order on the other handif we use sorted