Reference no: EM133185954

Questions 1 - 5 are on binary trees. You will be working with different datasets, specified individually for each student.

Your dataset will consist of a sequence of 15 four letter strings. Follow the instructions below to construct your dataset.

a. Write down your first name and your surname. My name is Juris Barlots

b. Under each letter write the position of that letter in the alphabet, i.e., 1 for A, 2 for B, . . . , 26 for Z.

c. Add up the numbers to get a 3-digit total, say XYZ (if the total is less    than 100 the first digit is 0).

d. Add 1 to YZ to get a line number between 1 and 100.

e. X specifies the position on the line: for X = 0, start at the 1st word;
for X = 1, start at the 5th word (continue on the next line if necessary); for X ≥ 2, start at the 10th word (continue on the next line if necessary).

f. Open the file TEXTE.pdf and start at position X on line YZ+1. Write down the next 15 words, replacing any capital letters by lower-case letters. Ignore all words with fewer than four letters (and also any numbers) and any word for which the first four letters are the same as those for any of your previous words.

g. Write down the sequence of 15 distinct four-letter strings obtained by taking the first four letters of each of the 15 words. This is your personal dataset.

Question 1: Draw the binary search tree obtained by inserting the 15 strings, in the order they occurred in the text, into an initially empty binary search tree.
Add in the threads to turn your tree into a threaded binary tree.

Question 2: Write down the order in which the nodes would be visited if the tree was traversed in postorder.

Question 3: Traverse the tree in preorder using the non-recursive algorithm on p.18 of the notes. Write down the order in which the nodes would be visited and also the stack contents immediately after the 3rd, 6th, 9th and 12th of the 15 nodes have been visited.

Question 4: Starting with your (unthreaded) binary search tree obtained in Question 1, draw the 3 binary trees resulting after deleting in order, one by one, the 1st, 2nd and 3rd of the 15 strings you inserted into the tree, each time deleting from the tree that resulted from the previous deletion. (You must use the deletion algorithm on p.29 of the notes.)

Question 5: Draw the forest corresponding to your original binary search tree obtained in Question 1 using the natural correspondence between forests and binary trees.

Question 6: On p.21 of the notes, two alternative interpretations of right-insertion in a threaded binary tree are depicted. The algorithm given was for the first interpretation. Write down a similar algorithm for the second interpretation, i.e. where the subtree rooted at R becomes the left subtree of the inserted node Q.

7-9 are on B-trees and are in the file: Q789X.pdf Notes for Questions 7, 8 and 9

Question 7:
You must adopt a consistent strategy throughout for splitting and merging pages:

(a) You must split all pages with an odd number of items in a consistent way, i.e. the extra item should either always go in the left-hand page or always go in the right- hand page.

(b) When merging a page having two sibling pages, you must either always merge it with the left-hand sibling page or always with the right-hand sibling page.