insertion into tree is sometimes quite easy and sometimes rather complicated in any case the process begins by searching for the appropriate leaf node if no full nodes are encountered during the searchinsertion is easy when the appropriate leaf node is reachedthe new data item is simply inserted into it figure shows data item with key being inserted into tree abefore insertion bafter insertion shifted right inserted figure insertion with no splits insertion may involve moving one or two other items in node so the keys will be in the correct order after the new item is inserted in this example the had to be shifted right to make room for the node splits insertion becomes more complicated if full node is encountered on the path down to the insertion point when this happensthe node must be split it' this splitting process that keeps the tree balanced the kind of tree we're discussing here is often called top-down tree because nodes are split on the way down to the insertion point let' name the data items in the node that' about to be split aband here' what happens in split (we assume the node being split is not the rootwe'll examine splitting the root later newempty node is created it' sibling of the node being splitand is placed to its right data item is moved into the new node