Problem Detail: I know from Sedgewick’s book on algorithms that the max depth of any node x from a set of N nodes is at most log2(N) applying the algorithm(which says to put the shorter tree beneath to avoid tall trees) and he gives an understandable proof by induction. The thing is that I have trouble visualising that result apart form the mathematical manipulations, I mean besides proving that that assumption is correct my question is how do you get to that assumption. This are some remarks he makes before the proof: 1)The depth of the node x increases by one when merged to another tree 2)When the depth increases the size of the tree at least doubles. But here is the thing, he says : “The size of the tree containing x can double at most log2N times” And I don’t understand why. Here is the link to a presentation he gave on the topic. http://algs4.cs.princeton.edu/lectures/15UnionFind-2×2.pdf the proof’s sketch is on slide 33. Thanks 🙂
Asked By : Darwin57721
Answered By : FrankW
If the size of a tree starts at 1 and doubles $i$ times, it will be $2^i$ (at least — there might be other size increases as well). If $i>log_2N$ this would give a size $>N$ — more than the total number of nodes.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/28319
