example consider the btree of order given below and delete node from it step delete step leaf node underflows so merge with left sibling and remove key step now index node underflowsso merge with sibling and delete the node figure deleting node from the given btree note insertion and deletion operations are recursive in nature and can cascade up or down the +treet thereby affecting its shape dramatically - trees in the last we have seen that for binary search trees the average-case time for operations like search/insert/delete is (log nand the worst-case time is (nwhere is the number of nodes in the tree howevera balanced tree that has height (log nalways guarantees (log ntime for all three methods typical examples of height balanced trees include avl treesred-black treesb treesand - trees we have already discussed these data structures in the earlier and sectionnow we will discuss - trees in - treeeach interior node has either two or three children nodes with two children are called -nodes the -nodes have one data value and two children nodes with three children are called -nodes the -nodes have two data values and three children (left childmiddle childand right childthis means that - tree is not binary tree in this treeall the leaf nodes are at the same level (bottom levellook at fig which shows - tree figure - tree