Re: red black trees
Re: red black trees
- Subject: Re: red black trees
- From: Allan Odgaard <email@hidden>
- Date: Thu, 19 Feb 2004 08:41:46 +0100
On 19. Feb 2004, at 5:22, Brian Reardon wrote:
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)
Arg... implementing algorithms in ObjC is certainly not something I
would recommend, not really for the performance overhead, but mainly
for the syntactic overhead -- i.e. lack of operator overloading,
implicit type conversions, compact type declarations, stack allocated
temporaries etc. etc.
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).
A sorted array would have linear insertion time, so that might be true
-- but e.g. std::set has lg N insertion time (in fact, std::set is
based on a red/black tree in the GCC/SGI implementation), so I would
not think this would affect the time complexity (granted you only need
to insert, lookup or iterate the values -- but what more could you ask
for? :) ).
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.
I have the second edition of the book from 1998 and cannot immediately
find the thing you refer to -- but I would be quite sure that std::set
is sufficient for your needs.
However, you actually have an rb_tree in the standard library that
comes with GCC, it is declared in the extension header "ext/rb_tree"
(i.e. it is not part of the C++ standard).
--
Private Mails To Allan At Top-House Dot DK
http://www.diku.dk/hjemmesider/studerende/duff/
_______________________________________________
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.