listing helper function for inserting key into node of the - tree handles the insertion of key into node if pref !nonethen the insertion is into an interior node class tree map def addtonodeselfsubtreekeydatapref )if the leaf is fullit has to be split if subtree isfull(return self splitnodesubtreekeydatanone otherwiseadd the new key in its proper order else if key subtree key subtree key subtree key subtree data subtree data subtree key key subtree data data if pref is not none if interior nodeset the links subtree right subtree middle subtree middle pref else subtree key key subtree data data if pref is not none if interior nodeset the links subtree right pref return (nonenonenonetuple to indicate the node was not split otherwisethe node has to be split by calling splitnode(and the resulting tuple is returned to the parent the splitnode()provided in listing handles the creation of the new tree node and the distribution of the keys and links to the proper location the pref argument is again used to indicate if we are working with leaf node or an interior node when an interior node is splitthe links have to be rearranged in order to maintain the tree property the three cases that can occurwhich depends on the child node into which the key is insertedare all handled by the function the promoted key and reference are returned in tuple for use by the treeinsert(function efficiency of the - tree by definitiona - tree is height balanced with all leaf nodes at the same level in the worst caseall nodes in the - tree will contain single key and all interior nodes will only have two children from the discussion of the binary search treewe know such structure results in height of log for tree of size the traversal operation must visit every node in the - tree resulting in worst case time of (nthe search operation used with - tree is identical to that of the binary search treewhich we know depends on the height of the tree since the maximum height of - tree is log nthe search operation will take no more log comparisonsresulting in worst case time of (log