Week 4: Binary Search Trees

Question 1

What is a dictionary / map?

Answer 1

Question 2

What is an ordered dictionary/map?

Answer 2

Question 3

What is a total order?

Answer 3

Question 4

What methods are in an ordered dictionary ADT?

Answer 4

Question 5

What is a search table?

Answer 5

Question 6

What are the time complexities of the following methods for a search table using a sorted array:

get()

put(k,data)

remove(k)

smallest()

largest()

predecessor()

successor()

Answer 6

Question 7

What is the hash table implementation of a search table? What are the time complexities of the following methods:

get

put

remove

smallest

largest

predecessor

successor

Answer 7

Question 8

What is a binary search tree?

Answer 8

Question 9

Where is the information stored in a binary search tree?

Answer 9

Internal nodes

Question 10

An inorder traversal of a BST visits keys in what order?

Answer 10

Increasing order

Question 11

What is the basis of the smallest() operator for BST’s? What is the algorithm? What is the time complexity?

Answer 11

Question 12

What is the basis of the get() operator for BST’s? What is the algorithm? What is the time complexity?

Answer 12

Question 13

What is the basis of the put() operator? What is the algorithm? Time complexity?

Answer 13

Question 14

What is the basis of the remove operator?

Answer 14

Question 15

What is the algorithm for the remove method? Time complexity?

Answer 15

Question 16

What is the algorithm for the successor operation? What is the time complexity?

Answer 16