chap non-binary trees using the parent pointer array representation nowconsider what happens when equivalence relationship (abis processed the root of the tree containing is aand the root of the tree containing is to make them equivalentone of these two nodes is set to be the parent of the other in this case it is irrelevant which points to whichso we arbitrarily select the first in alphabetical order to be the root this is represented in the parent pointer array by setting the parent field of (the node in array position of the arrayto store pointer to equivalence pairs (ch)(gf)and (deare processed in similar fashion when processing the equivalence pair (if)because and are both their own rootsi is set to point to note that this also makes equivalent to the result of processing these five equivalences is shown in figure (bthe parent pointer representation places no limit on the number of nodes that can share parent to make equivalence processing as efficient as possiblethe distance from each node to the root of its respective tree should be as small as possible thuswe would like to keep the height of the trees small when merging two equivalence classes together ideallyeach tree would have all nodes pointing directly to the root achieving this goal all the time would require too much additional processing to be worth the effortso we must settle for getting as close as possible low-cost approach to reducing the height is to be smart about how two trees are joined together one simple techniquecalled the weighted union rulejoins the tree with fewer nodes to the tree with more nodes by making the smaller tree' root point to the root of the bigger tree this will limit the total depth of the tree to (log )because the depth of nodes only in the smaller tree will now increase by oneand the depth of the deepest node in the combined tree can only be at most one deeper than the deepest node before the trees were combined the total number of nodes in the combined tree is therefore at least twice the number in the smaller subtree thusthe depth of any node can be increased at most log times when equivalences are processed example when processing equivalence pair (ifin figure ( ) is the root of tree with two nodes while is the root of tree with only one node thusi is set to point to rather than the other way around figure (cshows the result of processing two more equivalence pairs(haand (egfor the first pairthe root for is while the root for is itself both trees contain two nodesso it is an arbitrary decision