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) 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 [email protected]. For more options, visit https://groups.google.com/groups/opt_out.
