Week 5: Multi-Way Trees

Question 1

What is a Multi-Way Search Tree?

Answer 1

Question 2

Each internal node of a Multi-Way tree has how many children?

Answer 2

Question 3

What does it mean for a Multi-Way Search Tree to be of degree ‘d’

Answer 3

Each node can have d-1 items and each node can have at most d children (2 is the minimum amount of children)

Question 4

What is a sentinal key?

Answer 4

Question 5

How does searching work in Multi-Way Search Trees?

Answer 5

Question 6

What is the algorithm for get() in a Multi-Way Search Tree?

Answer 6

Question 7

What is the time complexity of the get() method in a Multi-Way Search Tree?

Answer 7

Question 8

The smallest() and largest() operations for a MWST take how much time?

Answer 8

Question 9

How does the successor operation work for MWSTs?

Answer 9

Question 10

What is the time complexity of the successor() operation for MWSTs? What is the algorithm?

Answer 10

Question 11

How does the put operation work in MWSTs? What is the time complexity?

Answer 11

Question 12

How does the remove() operation work for MWSTs? What is the time complexity?

Answer 12

Question 13

What are the time complexities of the following operations for MWSTs?

smallest()

largest()

get()

successor()

predecessor()

put()

remove()

Answer 13