Consider a version of a binary search tree (BST) for sorted maps that stores additional information...

Transcribed Image Text:

Consider a version of a binary search tree (BST) for sorted maps that stores additional information as data members of each node w of the tree to account for the smallest and largest 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 6 (Node), given below, provides the pseudocode for the constructor of a node in a binary tree with the additional information. Algorithm 6 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 Algorithm 7 FIND (T, k) 1: 2: while w NULL and kw.key do if k w.max then 3: 4: 'No value for key k' 5: 6: 7: 8: Statement 1 9: 10: if w NULL then 11: 12: 13: Statement 7 Statement 9 Statement 11 return if kw.key then Statement 13 else return [Choose ] [Choose w Consider a version of a binary search tree (BST) for sorted maps that stores additional information as data members of each node w of the tree to account for the smallest and largest 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 6 (Node), given below, provides the pseudocode for the constructor of a node in a binary tree with the additional information. Algorithm 6 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 Algorithm 7 FIND (T, k) 1: 2: while w NULL and kw.key do if k w.max then 3: 4: 'No value for key k' 5: 6: 7: 8: Statement 1 9: 10: if w NULL then 11: 12: 13: Statement 7 Statement 9 Statement 11 return if kw.key then Statement 13 else return [Choose ] [Choose w

Answer rating: 100% (QA)

Answ... View the full answer