TreeSet - log(n) time.

[Kezia Matthews]

"TreeSet guarantees log(n) time cost for basic operations (add, remove and contains)"
Can anybody explain the above statement to me?
Kezia.

[Karthik Guru]

hi kezia,
U seem to be testing our datastructures/algo skills :-)
did that long back (uhhm well ,2nd year of my bachelors)
well let me try,
Consider a balanced tree ( i guess that's the name for a tree with equal number of nodes on either side of the root?? ..u need get this confirmed :-) for me.
if the height of the tree is h, then the maximum number of comparisons u need to make c'd be h+1 (1 for root as well).
If u traverse a tree from root covering the complete height h, then
number of nodes traversed
n = 1 (root) + 2 exp 1 + 2 (exp) 2 + 2 (exp) 3....2 (exp) h
= 2 exp 0 +.....
= 2 exp (h+1) - 1
now ignoring "1"s we get
n = 2 (exp) h
if u take log to base 2 of both the sides, u get
log n(base 2) = h; got it??
Now suppose u intend to add an elemnt to TreeSort which implemets SortedSet,
At the most u might have to travel all the way to hieght of the tree, so u need to make comparisons at everynode upto the tree, so that u can place it to the right/left child of a particular node, right?.
this max c'd be h+1 (1 for root as well).
so say c is the time for 1 comparison,
the total time w'd be c(h+1)?
now h = log n(base 2);
subsituting u'll have
total time = c(logn) /// ignore 1
total time = (some constant) X (logn) right?
so total time for addition is proportional to log(n).
Am not sure if my explanation made any sense to you.
Others can probably explain it in a better way.
karthik.

[Kezia Matthews]

Hi Karthik,
I got stuck after reading the first line in the " number of nodes traversed " - explanation
n = 1 (root) + 2 exp 1 + 2 (exp) 2 + 2 (exp) 3....2 (exp) h
Let me try to analyze it....
Taking binary tree as an example,
Root
|
-----------------
| |
Left Right -- Level 1
Branch Branch
| |
2 child nodes 2 child nodes -- Level 2
| |
Total 4 nodes Total 4 nodes
- 2 children - 2 children -- Level 3
from each node from each node
The height of this binary tree is (3 + 1 root). Am I correct? The total number of nodes are 15 that is (14 + 1 root).
Now, coming to your statement,
n = 1 (root) + 2 exp 1 + 2 (exp) 2 + 2 (exp) 3....2 (exp) h
Does
2 (exp) 3
mean
2*3 number of nodes?
According to this calculation,
1 root + 2 nodes + 4 nodes + 6 nodes = 13 nodes.
I think I am getting you wrong. Can you explain the following statement?
n = 1 (root) + 2 exp 1 + 2 (exp) 2 + 2 (exp) 3....2 (exp) h
Thanks.
Kezia.

[This message has been edited by Kezia Matthews (edited June 07, 2001).]

[Karthik Guru]

kezia,

Originally posted by Kezia Matthews:
Does
2 (exp) 3
mean
2*3 number of nodes?
According to this calculation,
1 root + 2 nodes + 4 nodes + 6 nodes = 13 nodes.
[This message has been edited by Kezia Matthews (edited June 07, 2001).][/B]

2 (exponent) 3
ie 2 to the power 3 ( so 8).
Sorry abt that ,probably i s'd've mentioned that i meant exponent when i wrote exp.
so 1 + 2 + 4 + 8! = 15.
hope it helps.
karthik.

[Kezia Matthews]

Karthik,
The statement
n = 2 exp (h+1) - 1
would mean 2 to the power of (h+1) minus 1. Right?
In the example of the height of the tree being 3, n would be,
n = 2 to the power of 4 minus 1
= 16 - 1
= 15
In the next statement you have mentioned, 'ignore 1's'. I did not understand this. Can you explain?
Thanks,
Kezia.

[Karthik Guru]

Originally posted by Kezia Matthews:

Karthik,
The statement
n = 2 exp (h+1) - 1
would mean 2 to the power of (h+1) minus 1. Right?
In the example of the height of the tree being 3, n would be,
n = 2 to the power of 4 minus 1
= 16 - 1
= 15
In the next statement you have mentioned, 'ignore 1's'. I did not understand this. Can you explain?
Thanks,
Kezia.

kezia,
normally when you arrive at such notations u try to provide approximations.
That's why i said ignore 1.
Yes in this case it s'd be considered...(bcos h is small, rather comparable to 1)
Such derivations are to predict a generic behaviour so as value of h >> 1 ( 1 can be ignored when compared to h)you w'd arrive at the expression.
karthik.

[Kezia Matthews]

...(bcos h is small, rather comparable to 1)

You mean '1' is small when comparable to 'h'. Right?
Thanks Karthik. The log(n) time concept is clear to me now.
Kezia.