search trees listing helper function that splits full node splits non-root node and returns tuple with the promoted key and ref class tree dmap if pref !nonethen an interior node is being split so the new node created in the function will also be an interior node in that casethe links of the interior node have to be set appropriately def splitnodeselfnodekeydatapref )create the new nodethe reference to which will be promoted newnode treenodenonenone see where the key belongs if key node key left pkey node key pdata node data node key key node data data newnode key node key newnode data node data if pref is not none if interior nodeset its links newnode left node middle newnode middle node right node middle pref elif key node key middle pkey key pdata data newnode key node key newnode data node data if pref is not none if interior nodeset its links newnode left pref newnode middle node right else right pkey node key pdata node data newnode key key newnode data data if pref is not none if interior nodeset its links newnode left node right newnode middle pref the second key of the original node has to be set to null node key none node data none return the promoted key and reference to the new node return (pkeypdatanewnodethe insertion operationand the deletion which we leave as an exercisealso works very similarly to that of the binary search tree the search down the tree to find leaf into which the new key can be inserted takes logarithmic time if the leaf is fullit has to be split node can be split and the keys distributed between the original nodethe new nodeand the parent node in constant time in the worst casea node split is required at each level of the tree during the unwinding