Map ADT

Question 1

What are the main methods of the Map ADT?

Answer 1

get(element) - if map has an entry element, return its associated value
put(element, value) - if map does not have an entry element, add element, value into map
remove(element) - if map has element, remove it and its value

Question 2

What is a map?

Answer 2

A searchable collection of key-value entries that support searching, insertion and deletion

Question 3

What is the definition of a binary search tree?

Answer 3

a binary tree where each right child is strictly larger than the parent, and each left child is strictly smaller.

Question 4

how do we remove an element from a binary tree? if the element we are removing has one child

Answer 4

promote the child upwards to replace the element

Question 5

how do we remove an element from a binary tree? if the element we are removing has two children

Answer 5

• locate the predecessor
• move this up to replace the element
• remove the predecessor

Question 6

What is the predecessor in a binary tree?

Answer 6

The largest child of the left hand child of an element

Question 6

What is the predecessor in a binary tree?

Answer 6

The largest child of the left hand child of an element

Question 7

What is the performance of a binary search tree’s size and isEmpty method?

Answer 7

Worst case theta 1

Question 8

What is the performance of a binary search tree’s get, put and remove methods?

Answer 8

Worst case theta height