patternMinor
Depth of any node x in Weighted Quick-Union Algorithm
Viewed 0 times
depthnodeanyweightedunionalgorithmquick
Problem
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-2x2.pdf the proof's sketch is on slide 33.
Thanks :)
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-2x2.pdf the proof's sketch is on slide 33.
Thanks :)
Solution
Here is my approach to understand, mix of both visualization and mathematics.
In the weighted quick union, when we need to do union for two nodes, we join the roots of those two nodes ( basically the smaller tree joins the bigger tree ).
Lets say these are the two trees :-
Now lets say we need to perform union ( 3, 5) the resulting tree will look like this
Depth of node 3 increased by 1 during this operation but the depth of node 5 remained the same.
This means the depth of a node will only increase if the tree in which it is present joins a bigger tree.
Now whenever a small tree of size x ( no. of nodes in the tree) joins a bigger ( or equal sized ) tree, the size of result tree is at least 2 times x.
Now lets say this doubling of size happens i times, the size of resulting tree will be 2^i. Remember that whenever the size doubled the depth of some of the nodes increased by 1.
What is the maximum size the tree can obtain ?
Thus the depth of any node can be increased upto log n, not anymore than that.
Remember all the above logic only applies when a smaller tree joins a larger tree as its branch. Otherwise the doubling logic will not apply.
In the weighted quick union, when we need to do union for two nodes, we join the roots of those two nodes ( basically the smaller tree joins the bigger tree ).
Lets say these are the two trees :-
1 6
/ \ and / \
4 3 5 2
\
7Now lets say we need to perform union ( 3, 5) the resulting tree will look like this
6
/| \
1 5 2
/ \ \
4 3 7Depth of node 3 increased by 1 during this operation but the depth of node 5 remained the same.
This means the depth of a node will only increase if the tree in which it is present joins a bigger tree.
Now whenever a small tree of size x ( no. of nodes in the tree) joins a bigger ( or equal sized ) tree, the size of result tree is at least 2 times x.
Now lets say this doubling of size happens i times, the size of resulting tree will be 2^i. Remember that whenever the size doubled the depth of some of the nodes increased by 1.
What is the maximum size the tree can obtain ?
2^i <= n ( no. of nodes in the tree )
i <= log n ( base 2 log operation )Thus the depth of any node can be increased upto log n, not anymore than that.
Remember all the above logic only applies when a smaller tree joins a larger tree as its branch. Otherwise the doubling logic will not apply.
Code Snippets
1 6
/ \ and / \
4 3 5 2
\
76
/| \
1 5 2
/ \ \
4 3 72^i <= n ( no. of nodes in the tree )
i <= log n ( base 2 log operation )Context
StackExchange Computer Science Q#28319, answer score: 5
Revisions (0)
No revisions yet.