chap non-binary trees figure an example of path compressionshowing the result of processing equivalence pair (heon the representation of figure (cunion rule for joining setsis th( lognthe notation "lognmeans the number of times that the log of must be taken before < for examplelog is because log log log and finally log thuslogn grows very slowlyso the cost for series of find operations is very close to note that this does not mean that the tree resulting from processing equivalence pairs necessarily has depth th(lognone can devise series of equivalence operations that yields th(log ndepth for the resulting tree howevermany of the equivalences in such series will look only at the roots of the trees being mergedrequiring little processing time the total amount of processing time required for operations will be th( logn)yielding nearly constant time for each equivalence operation this is an example of the technique of amortized analysisdiscussed further in section general tree implementations we now tackle the problem of devising an implementation for general trees that allows efficient processing of all member functions of the adt shown in figure this section presents several approaches to implementing general trees each implementation yields advantages and disadvantages in the amount of space required to store node and the relative ease with which key operations can be performed general tree implementations should place no restriction on how many children node may have in some applicationsonce node is created the number of children never changes in such casesa fixed amount of space can be allocated for the node when it is createdbased on the number of children for the node matters become more complicated if children can be added to or deleted from noderequiring that the node' space allocation be adjusted accordingly