Binary Trees

Notes

Skiena Chapter 3 Data Structures

Question 3-5

Question 3-5) Find the overhead fraction (data space/total space) for each binary tree implementation on n nodes given the following conditions:

• All nodes store data, 2 child pointers, and 1 parent pointer. Data fields are 4 bytes, pointers are 4 bytes.
• Only leaf nodes store data; internal nodes store 2 child pointers. Data field requires 4 bytes, 2 bytes per pointer.

First case:

• Binary tree with n nodes -> n-1 edges
• Child/parent ppointers means 2x edges
• 2(n-1) edges, 2(n-1) pointers
• Alternatively, here's the analysis:

n nodes x (4 bytes of data/node) = 4n bytes data

n nodes x (12 bytes of pointers/node) = 12 n bytes

Total space is 16 n bytes, so overhead fraction is 1/4, i.e., the data space to total space ratio is 1/4

Second case:

• If we have n nodes, we have ~n/2 leaves
• n nodes total x (1 leaf node / 2 nodes) ~ n/2 lleaf nodes

n/2 empty nodes x (2 pointers/1 empty node) x (2 bytes/pointer) = 2n bytes for empty nodes with pointers

n/2 data nodes x (4 bytes/1 empty node) = 2n bytes data

The overhead fraction is thus 1/2: half the bytes are for data, half the bytes are for pointers.

Question 3-6

Question 3-6) Modifying balance d search tree to have O(1) successor/predecessor methods?