CptS 223 Homework #2

Description

CptS 223 Homework #2
Please complete the homework problems on the following page using a separate
piece of paper. Note that this is an individual assignment and all work must
be your own. Be sure to show your work when appropriate. This assignment is
due end of day on Friday, February 24, 2017.
Yes, this is many pages, but each one is a relatively small amount of work.
Normally, it’s structure manipulations and some calculations.
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).
A
E
D G
B
F
I
C
5
5
10
0
9
5
10
0
2
5
2 10
0
5
10
0
9
2
1
5
10
9
2
1 3
3
10
9
2
1
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).
10 10
5
10
23
10
5
10
10
23
10
5
4
10
23
19
5
4
10
23
19
5
4 7
10
5
4 7
9
19
23
23
10
23
19
9
7
5
4
6
10
6
7
9
4 19
4. Given the following binary tree (where nullptr height == -1):
A. [1] What is the height of the tree?
4
B. [1] What is the depth of node 90?
3
C. [1] What is the height of node 90?
1
D. [3] Give the pre-order, in-order, and post-order traversal of this tree
Pre-order: 100, 50, 3, 1, 20, 80, 52, 90, 83, 99, 150, 125, 152
In-order: 1, 3, 20, 50, 52, 80, 83, 90, 99, 100, 125, 150, 152
Post-order: 1, 20, 3, 52, 83, 99, 90, 80, 125, 152, 150, 100
5. [3] Remove 5 from the following AVL tree; draw the results:
20
10
20
15
20
25
20
6. [3] Insert the value “8” into the following AVL tree; draw the result:
4
20
8
20
10
7
20 20
2
20
3
20
1
20
7. [3] Insert the value “12” into the following AVL tree; draw the result:
15
20
10
20
12
20
5
20
20
20
25
20
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.
Solution
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.
Solution
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 d draw the
new tree:
10 53
5
8
9
1
1
3
5
9
1
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:
3 nodes
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:
6 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?
Height is N^M + M
If we insert 30,000 CustomerData records, how tall will be tree be?
5
If we insert 2,500,000 customers how tall will the tree be?
12