entry into node and add new child (an external nodeto on the left of that iswe add entry (kxwto the dictionary (vour insertion method preserves the depth propertysince we add new external node at the same level as existing external nodes neverthelessit may violate the size property indeedif node was previously -nodethen it may become -node after the insertionwhich causes the tree to no longer be ( , tree this type of violation of the size property is called an overflow at node vand it must be resolved in order to restore the properties of ( , tree let , be the children of vand let be the keys stored at to remedy the overflow at node vwe perform split operation on as follows (see figure )replace with two nodes and ''where is -node with children storing keys and 'is -node with children , storing key if was the root of tcreate new root node uelselet be the parent of insert key into and make and 'children of uso that if was child of uthen and 'become children and of urespectively we show sequence of insertions in ( , tree in figure figure node split(aoverflow at -node (bthe third key of inserted into the parent of (cnode replaced with -node and -node 'figure sequence of insertions into ( , tree(ainitial tree with one entry(binsertion of (cinsertion of (dinsertion of which causes an overflow(esplitwhich causes the creation of new root node(fafter the split(ginsertion of (