Goal

Program in Python$3$ a B$-$Tree according to the specs given below. Your BTree allows a user to indicate the value of

t on creation. I have also included a tester and sample output. The tester used to grade will be almost identical.

The sample output of the print$\_$tree function is given so you can mimic its behavior exactly.

Pay close attention to the function descriptions. If you feel anything is unclear, please ask for guidance.

Submit only the code for your tree and node to Brightspace. We don't need the tester or sample output.

BTreeNode

You are free to implement the node class as you see fit. Remember, b$-$tree nodes keep their keys in order and child

links are ordered according to the order of the keys. You will need to indicate if a node is a leaf or not. Remember:

you can only add keys to a leaf node.

class BTreeNode:

There is no requirement that you use anything more complicated than simple lists. However, your tree must make

use of a node class to represent vertexes in the tree.

BTree

The BTree should have the following interface. The functions must behave as they are described. The interface is

minimal. You are welcome to add helper functions to both the tree and node class. Remember, they work together.

Consider which manipulation or check is better done in either the node or tree.

class BTree:

The BTree class

def init$($self$,$ t$)$:

The initializer function of the BTree class. The parameter t determines the order of the tree. If you are confused

about the purpose of t check the book on page $502($point $5).$ Do not hard$-$code the order of your tree to match the

tester. Allow it to vary at run$-$time. We might not grade using a tester where t$=3.$

The initializer should establish an empty tree and save the value of t$.$

def insert$($self$,$ key$)$:

The insert function adds the value stored in key to the btree. This function should follow the approach given in

section $18\mathrm{.}2$ of the book. In other words, insert should happen in one downward pass through the tree. This requires

that nodes are checked for fullness on the way to the bottom of the tree. If a node is full $(2$t$-1),$ the insert operation

calls for the node to be split before continuing down the tree.

Remember: New keys are only added to leaf nodes. All nodes must always have at least t$-1$ keys and no more than

$2$t$-1$ keys. The root node is exempt from the minimum key requirement. If you are splitting correctly, the lower

bound should not pose a problem since this assignment does not require you to implement the delete operation.

def print$\_$tree$($self$)$:

The print$\_$tree function prints the tree to the terminal in the format given in the screenshot below. Root keys $($depth

$0)$ are printed on the left hand margin. As depth increases, keys are printed indented by the following formula: two

spaces $*$ depth. A key at depth $2$ would be indented four spaces.

The keys and children must be printed in order with the left side of the tree at the top and the right side at the

bottom. Each line with a key should have the depth also indicated as an integer $($e$.$g$.,2$: $27,$ indicates key $27$ at

Yepthor screenshot.

You may add additional functions to the tree $($in fact I encourage it$),$ but only these three will be used by our tester.

Your tree printing function should produce output exactly like that given below for the provided

tester. Again, the grading tester will differ, but the format of your output should still conform to these specs.

Comments

The specs do not contain a node splitting function. Where that happens is up to you. Splitting should conform to

the splitting rules we discussed and practiced $($which are in the book$).$

For this the $($which are in the book$).$

The data. Keys appearing in internal nodes do not need to be duplicated in the leaves.

The book, in its pseudo$-$code for the various operations required by insertion, include DISK$-$WRITE and DISK$-$READ

As mentioned

improve your skills, delete is a good one.

The tree in the following example was produced by the tester included with this homework.