search trees there are two cases the left child is splitthe existing key in the parent node becomes the second key and the middle child is moved to become the right child the promoted key kp becomes the first key in the parent and the reference to the new node becomes the middle child links that have to be modified are shown by directed edges in the figure the middle child is splitthe promoted key kp becomes the second key of the parent and the newly created node becomes the right child splitting parent node what happens if the node is split and its parent contains three childrenfor examplesuppose we want to insert key into the sample tree shown in figure the node containing keys and has to be split with being promoted to the parent but the parent also contains two keys ( and when the parent node is fullit has to be split in similar fashion as leaf noderesulting in key and node reference being promoted to its parentthe grandparent of the child that was split the splitting process can continue up the tree until either non-full parent node or the root is located before after ** ** figure full parent node has to be split to accommodate promoted key when the parent node is splita new parent node is created and the two will become siblings splitting full interior node is very similar to splitting leaf node two of the three keysthe two in the original parentp and and the promoted keykp have to be distributed between the two parents and one has to be promoted to the grandparent the difference is the connections between the parents and children also have to be changed the required link modifications depends on which child was split there are three casesas illustrated in figure the tree configurations on the left show the nodes and keys before the parent is split and the trees on the right show the resulting configurations the links that have to be modified are shown with directed edges splitting the root node when the root node has to be splitas illustrated in figure new root node is created into which the promoted key is stored the original root becomes the