Content deleted Content added
→External links: replace java applet with javascript implementation |
m minor grammar fix |
||
Line 122:
The choice of which node becomes the parent has consequences for the complexity of future operations on the tree. If it is done carelessly, trees can become excessively tall. For example, suppose that <code>Union</code> always made the tree containing {{mvar|x}} a subtree of the tree containing {{mvar|y}}. Begin with a forest that has just been initialized with elements <math>1, 2, 3, \ldots, n,</math> and execute <code>{{math|Union(1, 2)}}</code>, <code>{{math|Union(2, 3)}}</code>, ..., <code>{{math|Union(''n'' - 1, ''n'')}}</code>. The resulting forest contains a single tree whose root is {{mvar|n}}, and the path from 1 to {{mvar|n}} passes through every node in the tree. For this forest, the time to run <code>Find(1)</code> is {{math|''O''(''n'')}}.
In an efficient implementation, tree height is controlled using '''union by size''' or '''union by rank'''. Both of these require
In the case of union by size, a node stores its size, which is simply its number of descendants (including the node itself). When the trees with roots {{mvar|x}} and {{mvar|y}} are merged, the node with more descendants becomes the parent. If the two nodes have the same number of descendants, then either one can become the parent. In both cases, the size of the new parent node is set to its new total number of descendants.
| |||