Re: red black trees
Re: red black trees
- Subject: Re: red black trees
- From: Brian Reardon <email@hidden>
- Date: Wed, 18 Feb 2004 21:22:06 -0700
So what is driving your desire to have a tree vs an ordered array?
I am trying to implement Preparata and Shamos's convex hull point set
search algorithm (Computational Geometry, Springer-Verlag, 1985,
section 4.1.3, pages 157-166) which is O(NlogN) for 2 dimensional
data sets and O(N(logN)^(d-2)) for d >=3. However, this result is
dependent on the implementation of a red-black tree and my
understanding of the algorithm (perhaps I am wrong) is that if you
only use a sorted array then the algorithm is O(N^2). I am making
this assumption based on p. 160 which goes into detail as to the
importance of using an ordered, balanced tree in this algorithm.
--
_______________________________________________
cocoa-dev mailing list | email@hidden
Help/Unsubscribe/Archives:
http://www.lists.apple.com/mailman/listinfo/cocoa-dev
Do not post admin requests to the list. They will be ignored.