- - fig weight distribution of branches in the tree in fig we divide the nodes into three classes the - nodes in the left subtree have an average path length ai- the root has path length of the - nodes in the right subtree have an average path length an- hencethe equation above can be expressed as sum of two terms and an( (( - ai- ( -ian-in the desired quantity an is the average of an(iover all ni over all trees with the key at the root an (si < < ( - ai- ( -ian-in (si < < ( - ai- (si < ni ain this equation is recurrence relation of the form an ( an- from this we derive simpler recurrence relation of the form an (an- we derive directly ( by splitting off the last termand ( by substituting - for ( an *( - an- / (si < - ain ( an- (si < - ai( - ) multiplying ( by - ) / yields ( (si < - ain an- ( - ) / and substituting the right part of ( in ( )we find an ( - an- an- ( - ) an- ( - ) it turns out that an can be expressed in non-recursiveclosed form in terms of the harmonic sum hn / / / an (hn ( + )/ from euler' formula (using euler' constant )hn ln / we derivefor large nthe approximate value an (ln since the average path length in the perfectly balanced tree is approximately anlog we obtainneglecting the constant terms which become insignificant for large nlim (an/an' ln(nlog( ln( what does this result teach usit tells us that by taking the pains of always constructing perfectly balanced tree instead of the random treewe could always provided that all keys are looked up with