class BTreeNodeWithInsert$($BTreeNodeBase$)$:

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

super$().\_\_$init$\_\_($keys$,$ ptrs$,$ is$\_$root, d$)$

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

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

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

assert self.is$\_$root

res $=$ self.insert$\_$helper$($new$\_$keys$)$

if res $!=$ None :

$[$mid$\_$key, n$1,$ n$2]=$ res

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

new$\_$root $=$ self.creat$\_$new$\_$instance$([$mid$\_$key$],[$n$1,$ n$2],$ True, self.d$)$

n$1.$set$\_$parent$($new$\_$root, $0)$

n$2.$set$\_$parent$($new$\_$root, $1)$

return new$\_$root

else :

return self

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

if self.is$\_$leaf$()$ :

self.insert$\_$key$\_$into$\_$list$($key$)$

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

if n $<=2*$ self.d :

return None

else :

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

else :

i $=0$

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

while i $<$ n and self.keys$[$i$]<$ key :

i $=$ i $+1$

if i $<$ n and self.keys$[$i$]==$ key :

if debug :

print$($f$\text{'}$Key $\{$k$\}$ already exists'$)$

return None

else :

res $=$ self.pointers$[$i$].$insert$\_$helper$($key$)$

if res is None :

$($mid$\_$key, node$\_$left, node$\_$right$)=$ res

self.insert$\_$key$\_$and$\_$ptr$[$mid$\_$key, node$\_$left, node$\_$right$]$

if len$[$self$.$keys$]==2*$ self.d $+1$ :

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

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]$:

$($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$\_$left.set$\_$parent$($self$,$ i$)$

assert self.pointers$[$i$]==$ node$\_$left

$($new$\_$key, new$\_$child$)=($mid$\_$key, node$\_$right$)$

for j in range$($n$,$ i$,-1)$:

self.keys$[$j$]=$ self.keys$[$j $-1]$

self.pointers$[$j $+1]=$ self.pointers$[$j$]$

self.keys$[$i$]=$ new$\_$keys

self.pointers$[$i $+1]=$ new$\_$child

new$\_$child.set$\_$parent$($self$,$ i $+1)$

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

self.pointers.append$($new$\_$child$)$

new$\_$child.set$\_$parent$($self$,$ n $+1)$

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

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

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

def $\_$split$\_$node$($self$)$:

assert len$($self$.$keys$)==2*$ self.d $+1$

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

d $=$ self.d

mid$\_$key $=$ self.keys$[$d$]$

new$\_$keys $=$ list$($self$.$keys$[$d $+1$:$])$

self.keys $=$ list$($self$.$keys$[$:d$])$

if self.is$\_$leaf$()$ :

new$\_$ptrs $=[]$

else :

new$\_$ptrs $=$ list$[$self$.$pointers$[$d$+1$:$]]$

self.pointers $=$list$[$self$.$pointers$[$:d$+1]]$

new$\_$node $=$ self.create$\_$new$\_$instance$($new$\_$keys, new$\_$ptrs$,$ False, d$)$

new$\_$node.fix$\_$parent$\_$pointers$\_$for$\_$children$()$

return $($mid$\_$key, self, new$\_$node$)$

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

assert len$($self$.$keys$)==2*$ self.d $+1$

d $=$ self.d

if self.parent $==$ None :

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

$($parent$\_$node, parent$\_$idx$)=$ self.parent

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

parent$\_$index $=$ self.parent.pointers.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*$ self.d:

parent$\_$index $=$ self.parent.pointers.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$()$

Cell In$[77],$ line $108,$ in BTreeNodeWithInsert.handle$\_$full$\_$node$($self$)106$ d $=$ self.d $107$ if self.parent $==$ None : $-->108$ return self.split$\_$node$()110($parent$\_$node, parent$\_$idx$)=$ self.parent $111$ # Check if there is a right sibling and if it can lend a key $112$ # Check if there is a right sibling and if it can lend a key AttributeError: 'BTreeNodeWithInsert' object has no attribute 'split$\_$node'