Problem Set $4$

This problem set will build upon ideas for B$-$Trees and suffix tries that we have already presented in the

videos and notes. The code in the notes will be very important for completing this assignment. We suggest

that you familiarize yourself with the notes $($interactive labs$)$ before starting this problem set.

Problem $1$

We will revisit the insertion algorithm for B$-$Trees in this problem. Recall that the insertion algorithm presented

in class was rather simple. If a node is full, we split it into two. If needed, we will insert a new key into the

parent. This process goes up the tree and if need be$,$ creates a new root node.

For this problem, we would like to implement the "lending scheme" similar to the "borrowing scheme" that we

considered for key deletion in B$-$Trees for the insertion algorithm. The key idea is that if a node is over$-$full

$($has $2d+1$ keys$)$ as a result of an insertion, we would like to perform the following steps:

Check if the node has a right sibling and it has $<2d$ keys. If so$,$ shift the rightmost key up to the parent

node and the key from the parent node as the leftmost key of the right sibling. If the node$/$right sibling is

not a leaf, we need to move pointers as well.

Check if the node has a left sibling and it has $<2d$ keys. If so$,$ shift the leftmost key up to the parent

node and the key from the parent node as the rightmost key of the left sibling. If the node$/$left sibling is

not a leaf, we need to move pointers as well.

If both of the conditions above do not hold, split the node into two according to the median and insert a

parent at the leaf. This is the same procedure as before.

The advantages of doing things this way include: $($a$)$ efficiency $--$ we have insertions potentially finishing

faster with a few key exchanges $($in a real B$-$Tree the sibling nodes may be on the disk and that may

actually cause insertions to be slower but we will ignore this in our implementation$)$; and $($b$)$ balance $--$

splitting a full node into two causes two nodes that are just half full. By lending keys, we are ensuring

that splitting only happens when the node and its sibling are at capacity.

Here is the base object for a BTreeNode given to you exactly as we had implemented in the notes. We would like you to modify the BTreeNodeWithInsert class below that implements the insert function. For your convenience, we have modified it so that when a node becomes full, it calls the handle$\_$full$\_$node function. This function should

$($a$)$ check if the node has a right sibling and whether it can "lend" a key to the right sibling. If so$,$ it should implement that and remember to update the pointers. The function fix$\_$pointers$\_$for$\_$children will be very useful.

$($b$)$ check if the node has a left sibling and whether it can "lend" a key to the right sibling. If so$,$ it should implement that and remember to update the pointers. The function fix$\_$pointers$\_$for$\_$children will be very useful.

$($c$)$ Otherwise, we revert back to the old code for splitting a node that is given to you.

Complete the implementation of the handle$\_$full$\_$node function below. Note that it is being called at two places from the insert$\_$helper function.