On Monday, April 29, 2013 4:06:50 PM UTC-8, Gary Drocella wrote: > > My name is Gary Drocella, age 23, and got my BA in comp. sci. at > University of Maryland College Park. I am reading a book for fun on my > spare time > Multidimensional and Metric Data Structures by Hanan Samet. They are > talking about range trees, and they claim that a 1-dimensional range search > for [B:E] is O(lg(N) + F) where N is number of nodes and F is number of > points found, which makes sense because it's a binary tree. Then for > higher > spatial dimensions d; it becomes (O(lg(N)^d + F) > > What I don't understand is they also claim that the 1d structure only > takes O(N) space. To me this is to low for a balanced binary tree where > their are already > N leaf nodes and I internal nodes. But as I'm explaining this I think I > figured it out, but someone can just to make sure this is correct. So we > have total space > > Total Space = N + I = (N + lg(N)) in O(N) > Re-thought this :). The height of the tree will be h = lg(N) so I = (sum of I=1 to h) 2^i = (1 - 2^(lg(N) / (1 - 2) = 2^lg(N) - 1 = N - 1 Therefore Total Space = N+I = (N + N-1) = 2N - 1 in O(N) got it!!
> > Thanks for your remarks. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
