Question

5. [15 pts.] Consider a version of a binary search tree (BST) for sorted maps with integer keys that stores additional information as data members of each node w of the tree to account for the smallest and largest integer keys in the subtree rooted at w. Suppose that we can access this information using w.min, for the smallest integer key, and w.max, for the largest. Algorithm 4 provides the pseudocode for the constructor of a node in a binary tree with the additional information.

Algorithm 4 Node(k,v,left,right,parent)

1: w ← new node

2: w.key ← k

3: w.value ← v

4: w.left ← left

5: w.right ← right

6: w.parent ← parent

7: w.min ← k

8: w.max ← k

9: return w

(One can adapt the find operation to account for this information and potentially stop the search early. Algorithm 5 provides the pseudocode for the new implementation of the find function.)

Algorithm 5 find(T,k)

1: w ← T.root

2: while w 6= NULL and k 6= w.key do

3:                      if k < w.min or k > w.max then return NULL

4:                 if k < w.key then

5:                        w ← w.left

6:              else

7:                        w ← w.right

8: return w

(Note that the data structure must maintain the invariant w.min ≤ w.key ≤ w.max. Hence, both the insert and delete operations must be properly adapted.)

(Your task is to complete the pseudocode for the insert function, started for you in the partial pseudocode given in Algorithm 6, by writing the missing statements.)

(NOTE: The missing statements you are asked to write for the insert function in Algorithm 6 only require simple accesses or changes to node w’s data members or appropriate reassignment of the variable w itself.)

Algorithm 6 insert(T,k,v)

1: w ← T.root 2: while w 6= NULL and k

6= w.key do

3: 4:	if k < w.min then
5: 6:	if k > w.max then
7:	if k < w.key then
8:	if w.left = NULL then
9: 10:	x ← Node(k,v,NULL,NULL,w)
11: 12:	return x
13:	else
14:	if w.right = NULL then
15: 16:	x ← Node(k,v,NULL,NULL,w)

17:

return x

18:

19: if w 6= NULL then

20:

21: return w

Answer 1

IF YOU HAVE ANY DOUBTS COMMENT BELOW I WILL BE THERE TO HELP YOU

ANSWER:

EXPLANATION:

I AM GIVING YOU THE ANSWERS FOR THE BLANKS

line 4: w.min = k // updating smallest key rooted under w

line 6: w.max = k // updating largest key rooted under w

line 10: w.left = x // updating left node of w as x

line 12: w = w.left // going left subtree

line 16: w.right = x // updating right node of w as x

line 18: w = w.right // going right subtree

line 20: w.value = v // updating value of node incase inserted key is duplicate

RATE THUMBSUP PLEASE