Homework 10

Describe a modification of a Binary Search Tree dictionary that can return

the minimum value in the dictionary in Θ(1) time. This change should not

increase the asymptotic complexity of any other dictionary operation.

1. What new field(s) does the data structure need?

2. How does this change impact the min, insert, and delete methods of the

BST? Note that insertion and deletion may change the minimum value in

the BST.

Reference implementations of the min, insert, and delete functions appear

below.

1 Algorithm: BSTDict.min()

2 node = root

3 while node has a left child do

4 node = node.left

5 end

6 return node

1

1 Algorithm: BSTDict.insert(new)

2 node = root

3 while node isn’t NIL do

4 if node.value ≤ new then

5 if node.left = NIL then

6 Add new as left child of node

7 node = node.left

8 end

9 node = node.left

10 else

11 if node.right = NIL then

12 Add new as right child of node

13 node = node.right

14 end

15 node = node.right

16 end

17 end

2

1 Algorithm: BSTDict.delete(node)

2 if node has two children then

3 swapnode = right

4 while swapnode has a left child do

5 swapnode = swapnode.left

6 end

7 Swap node’s parent and children links with swapnode

8 if node is the BST root then

9 Set root to be swapnode

10 end

11 end

12 if node has no children then

13 if node is the root then

14 Set root to be NIL

15 else

16 Set node.parent’s child to be NIL

17 end

18 else

/* node must have one child */

19 if node is the root then

20 Set root to be node’s child

21 else

22 Set node.parent’s child to be node’s child

23 end

24 Set node’s child’s parent to be node.parent

25 end

3

## Reviews

There are no reviews yet.