Question

The linked implementation is used in the coding of a Binary Search Tree structure. Calculate the structure's density assuming that it contains 200 nodes and:

a.  Each node contains 10 bytes of information.

b.  Each node contains 300 bytes of information.

Then, repeat the above exercise for the array implementation of the Binary Search Tree, assuming it is:

a.  Left balanced.

b.  Skewed to the right.

Answer 1

Consider the data:

                    The number of nodes (n) =200

a) The number of bytes per node (w) = 10

     Therefore, the information bytes = 200 * 10 =2000.

      The total bytes = 2000+200 =2200

To calculate the density D,

                           D= (information bytes)/ (total bytes).

                              = 2000/2200

                              = 0.909

b) The number of bytes per node(w) = 300

     Therefore, the information bytes = 200 * 300 =60000.

     The total bytes = 60000+300 =60300

    To calculate the density D,

                           D= (information bytes)/ (total bytes).

                              =60000/(60300)

                              =0.995