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 algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
