Q1) B-trees generalize the notion of a 2-3 tree trees where non-leaf vertices have more children.

A. Generalize the 2-3 algorithms for INSERT and DELETE to K-J trees, where non-leaf vertices have between K and J children for fixed integers K >=2, and J>= 2K-1.

B. Explain why the condition J >= 2K-1 is needed.

C. Consider a computer disk where it takes time x to move ("seek") to the start of a portion of the disk ("track") that contains a block of m data items, and then it takes time y per data item to sequentially read or write each item in the block. Discuss the practical implications of storing n data items at just the leaves instead of at all vertices. In particular, consider the case where x is much larger than y and where data items are records consisting of a short key together a large amount of associated data (so values at non-leaf vertices are just keys, whereas leaves store entire records).