Homework #2 - All About Those Trees

CptS 223 Homework #2 - All About Those Trees

Please complete the homework problems on the following page using a separate piece of paper or digitally as you see fit. Note that this is an individual assignment and all work must be your own. Be sure to show your work when appropriate. 
Yes, this is many pages, but each one is a relatively small amount of work. Normally, it’s structure manipulations and some calculations.
Turn in this assignment by making a PDF of it. Then put that PDF into your git repository on the HW2 branch. Commit and push it to the server. On Blackboard, only turn in a file with the commit hash on the HW2 branch with your file. The grader will clone your repository, change to the HW2 branch and checkout your commit.
I suggest removing the original assignment files (I’m giving you the PDF, docx, and odt formats), so it’s obvious to the grader what to grade. Just having the PDF of your answers there will make it clear which file you want them to look at. 
1. [3] Given the following pre-order and in-order traversals, reconstruct the appropriate binary tree.  NOTE: You must draw a single tree that works for both traversals.
Pre-order: A, E, D, G, B, F, I, C
In-order: D, E, B, G, A, F, I, C






2. [3] Starting with an empty BST, draw each step in the following operation sequence.  Assume that all removals come from the left subtree when the node to remove is full.
Insert(5), Insert(10), Insert(2), Insert(9), Insert(1), Insert(3), Remove(5).

 

3. [3] Starting with an empty BST, draw each step in the following operation sequence.  Assume that all removals come from the right subtree when the node to remove is full.
Insert(10), Insert(5), Insert(23), Insert(4), Insert(19), Insert(7), Insert(9), Insert(6), Remove(5).

 

4. Given the following binary tree (where nullptr height == -1):
 
A.    [1] What is the height of the tree?




B.    [1] What is the depth of node 90?




C.    [1] What is the height of node 90?




D.    [3] Give the pre-order, in-order, and post-order traversal of this tree.

 

5.  [3] Remove 5 from the following AVL tree; draw the results:
 

6. [3] Insert the value "8" into the following AVL tree; draw the result:
 

 

7. [3] Insert the value “12” into the following AVL tree; draw the result:
 

 

8. [3] Insert the value "8" into the following Red-Black tree; draw the result.  Use Double-circle to denote red nodes and single circle to denote black nodes.
 

 

9. [3] Delete the value "2" from the following Red-Black tree; draw the result.  Use Double-circle to denote red nodes and single circle to denote black nodes.

 

 

10. [4] Given the following B+ tree (M = 3, L = 3):

 
A) Insert 12 into the tree and draw the resulting B+ Tree:








B) Based on the tree resulting from  part (A), now remove 10 and draw the new tree:

 

11. [6] We are going to design our B+ Tree to be as optimal as possible for our old hard drives (since the management won’t buy new ones, those cheapskates!). We want to keep the tree as short as we can, and pack each disk block in the filesystem as tightly as possible. We also want to access our data in sorted order for printing out reports, so each leaf node will have a pointer to the next one. See figure #1 on next page for a visualization of our tree.
CPU architecture: Intel Xeon with 64 bit cores
Filesystem: Ext4 with 4KB (4096 byte) blocks
The customer records are keyed by a random UUID of 128 bits
Customer’s Data record definition from the header file:
#include <uuid>
struct CustomerData {
    uuid_t uuid;        // Customer 128 bit key
    char[32] name;    // Customer name (char is 1 byte each)
    uint32_t ytd_sales;    // Customer year to date sales
};

Calculate the size of the internal nodes (M) for our B-tree:






Calculate the size of the B-tree leaf nodes (L) for this tree make sure to include the pointer (note CPU architecture!) to keep the list of leaf nodes:





 
Figure #1: Visualization of our B+ Tree of height 2, customer data records, and pointers between the leaf nodes.

How tall (on average) will our tree be (in terms of M) with N customer records?


If we insert 30,000 CustomerData records, how tall will be tree be?



If we insert 2,500,000 customers how tall will the tree be?