while performing insertion and deletion operations in treethe number of child nodes may change soin order to maintain minimum number of childrenthe internal nodes may be joined or split we will discuss searchinsertionand deletion operations in this section searching for an element in tree searching for an element in tree is similar to that in binary search trees consider the tree given in fig to search for we begin at the root node the root node has value which is less than sowe traverse in the right sub-tree the right sub-tree of the root node has two key values and since ps ps we traverse the right sub-tree of that isthe left sub-tree of this sub-tree has three values and on finding the value the search is successful take another example if you want to search for then we traverse the left sub-tree of the root node the left sub-tree has two key values and againwe traverse the left sub-tree of we find that it has two key values and there is no left sub-tree of hence the value is not stored in the tree since the running time of the search operation depends upon the height of the treethe algorithm to search for an element in tree takes (logt ntime to execute inserting new element in tree in treeall insertions are done at the leaf node level new value is inserted in the tree using the algorithm given below search the tree to find the leaf node where the new key value should be inserted if the leaf node is not fullthat isit contains less than - key valuesthen insert the new element in the node keeping the node' elements ordered if the leaf node is fullthat isthe leaf node already contains - key valuesthen (ainsert the new value in order into the existing set of keys(bsplit the node at its median into two nodes (note that the split nodes are half full)and (cpush the median element up to its parent' node if the parent' node is already fullthen split the parent node by following the same steps example look at the tree of order given below and insert and into it step insert step insert figure (