cclass BTreeNodeWithInsert$($BTreeNodeBase$)$:

def $\_\_$init$\_\_($self$,$ keys$=$None, ptrs$=$None, is$\_$root$=$False, d$=10)$:

if keys is None:

keys $=[]$

if ptrs is None:

ptrs $=[]$

self.keys $=$ keys

self.pointers $=$ ptrs

self.is$\_$root $=$ is$\_$root

self.d $=$ d

self.parent $=$ None # No parent initially

self.right$\_$sibling $=$ None # Right sibling placeholder

self.left$\_$sibling $=$ None # Left sibling placeholder

def create$\_$new$\_$instance$($self$,$ keys, ptrs$,$ is$\_$root, d$)$:

return BTreeNodeWithInsert$($keys$,$ ptrs$,$ is$\_$root, d$)$

def insert$($self$,$ new$\_$key$)$:

if len$($self$.$keys$)<2*$ self.d $-1$:

self.$\_$insert$\_$key$($new$\_$key$)$

return self # No split, just return the current node $($updated$)$

mid$\_$key, left$\_$child, right$\_$child $=$ self.$\_$split$\_$node$($new$\_$key$)$

return mid$\_$key, left$\_$child, right$\_$child

def insert$\_$helper$($self$,$ key$)$:

if len$($self$.$keys$)>2*$ self.d:

self.handle$\_$full$\_$node$()$

def $\_$insert$\_$key$($self$,$ new$\_$key$)$:

self.keys.append$($new$\_$key$)$

self.keys.sort$()$ # Ensure keys remain sorted

def insert$\_$key$\_$into$\_$list$($self$,$ new$\_$key$)$:

assert self.is$\_$leaf$()$

n $=$ len$($self$.$keys$)$

assert new$\_$key not in self.keys, f'key $\{$new$\_$key$\}$ already exists $\{$self$.$keys$\}\text{'}$

self.keys.append$($new$\_$key$)$

i $=$ n

while i $>=1$ and self.keys$[$i$]<$ self.keys$[$i$-1]$:

# Swap keys if necessary

$($self$.$keys$[$i$-1],$ self.keys$[$i$])=($self$.$keys$[$i$],$ self.keys$[$i$-1])$

i $=$ i $-1$

def insert$\_$key$\_$and$\_$ptr$($self$,$ mid$\_$key, node$\_$left, node$\_$right, i$)$:

n $=$ len$($self$.$keys$)$

assert i $>=0$ and i $<=$ n

node

def insert$\_$into$\_$node$($self$,$ new$\_$key$)$:

self.keys.append$($new$\_$key$)$ # Temporarily add the key

self.keys.sort$()$ # Sort the keys to maintain the order

return None

def fix$\_$parent$\_$pointers$\_$for$\_$children$($self$)$:

for j$,$ child$\_$node in enumerate$($self$.$pointers$)$:

child$\_$node.set$\_$parent$($self$,$ j$)$

def $\_$split$\_$node$($self$,$ new$\_$key$)$:

mid$\_$index $=$ len$($self$.$keys$)//2$

mid$\_$key $=$ self.keys$[$mid$\_$index$]$ # The median key

left$\_$child $=$ BTreeNodeWithInsert$($self$.$d$)$

right$\_$child $=$ BTreeNodeWithInsert$($self$.$d$)$

left$\_$child.keys $=$ self.keys$[$:mid$\_$index$]$

right$\_$child.keys $=$ self.keys$[$mid$\_$index$+1$:$]$

if new$\_$key $<$ mid$\_$key:

left$\_$child.insert$($new$\_$key$)$

else:

right$\_$child.insert$($new$\_$key$)$

return mid$\_$key, left$\_$child, right$\_$child

def handle$\_$full$\_$node$($self$)$:

if self.right$\_$sibling and len$($self$.$right$\_$sibling.keys$)<2*$ d:

parent$\_$index $=$ self.parent.children.index$($self$)$

self.parent.keys.insert$($parent$\_$index, self.keys.pop$())$

self.right$\_$sibling.keys.insert$(0,$ self.parent.keys$[$parent$\_$index$])$

if not self.is$\_$leaf:

fix$\_$pointers$\_$for$\_$children$($self$,$ self.right$\_$sibling$)$

return

elif self.left$\_$sibling and len$($self$.$left$\_$sibling.keys$)<2*$ d:

parent$\_$index $=$ self.parent.children.index$($self$)-1$

self.parent.keys.insert$($parent$\_$index, self.keys.pop$(0))$

self.left$\_$sibling.keys.append$($self$.$parent.keys$[$parent$\_$index$])$

if not self.is$\_$leaf:

fix$\_$pointers$\_$for$\_$children$($self$.$left$\_$sibling, self$)$

return

else:

self.split$\_$node$()$

lst $=[1,5,2,4,-4,-3,-7,12]$

b $=$ BTreeNodeWithInsert$($d$=2,$is$\_$root$=$True$)$

for k in lst:

b $=$ b$.$insert$($k$)$

b$.$rep$\_$ok$()$

print$(\text{'}$Starting tree is : $\text{'})$

draw$\_$btree$\_$graph$($b$)$

## Note: the insertions above will not trigger any calls to the student's code unless student has modified instructor's code

# TEST lending key to right sibling

print$(\text{'}$Inserting $-8\text{'})$

b $=$ b$.$insert$(-8)$

b$.$rep$\_$ok$()$

draw$\_$btree$\_$graph$($b$)$

assert len$($b$.$keys$)==1,$ f'root must have just one key. Your root has $\{$len$($b$.$keys$)\}\text{'}$

assert b$.$keys$[0]==1,$ f'root must have a single key : $[1].$ Your root has $\{$b$.$keys$\}\text{'}$

c$0=$ b$.$pointers$[0]$

c$1=$ b$.$pointers$[1]$

assert c$0.$is$\_$leaf$()$

assert c$1.$is$\_$leaf$()$

assert c$0.$keys $==[-8,-7,-4,-3],$ f'Left child of root must have keys $[-8,-7,-4,-3].$ Your left child has keys $\{$c$0.$keys$\}\text{'}$

assert c$1.$keys $==[2,4,5,12],$ f'Right child of root must have keys $[2,4,5,12].$ Your right child has keys $\{$c$1.$keys$\}\text{'}$

this is the error i get:

AttributeError Traceback $($most recent call last$)$ Cell In$[33],$ line $64$ b $=$ BTreeNodeWithInsert$($d$=2,$is$\_$root$=$True$)5$ for k in lst: $---->6$ b $=$ b$.$insert$($k$)7$ b$.$rep$\_$ok$()8$ print$(\text{'}$Starting tree is : $\text{'})$ AttributeError: 'tuple' object has no attribute 'insert'

i$\text{'}$m not sure where to go from here