fusion operation at node may cause new underflow to occur at the parent of wwhich in turn triggers transfer or fusion at (see figure hencethe number of fusion operations is bounded by the height of the treewhich is (log nby proposition if an underflow propagates all the way up to the rootthen the root is simply deleted (see figure and ( (bu ( (dfigure propagating sequence of fusions in ( tree(aremoval of which causes an underflow(bfusionwhich causes another underflow(csecond fusion operationwhich causes the root to be removed(dfinal tree performance of ( , trees the asymptotic performance of ( tree is identical to that of an avl tree (see table in terms of the sorted map adtwith guaranteed logarithmic bounds for most operations the time complexity analysis for ( tree having keyvalue pairs is based on the followingthe height of ( tree storing entries is (log )by proposition splittransferor fusion operation takes ( time searchinsertionor removal of an entry visits (log nnodes thus( trees provide for fast map search and update operations ( trees also have an interesting relationship to the data structure we discuss next