Re: Using Red-Black Trees

[Adam Beneschan <adam@irvine.com>]

On Nov 16, 6:50 pm, "Alex Mentis" <f...@invalid.invalid> wrote:
> Randy Brukardt wrote:
> > Unless you are a student, worrying about a specific data structure is
> > silly in 99% of the cases.
>
> Some students do use Ada.
>
> > I don't know what data
> > structures this newsreader and browser use, but they're good enough
> > for the application, so why should I care?? Same goes for the
> > standard containers.
>
> Ah, ignorance is bliss!  "It just works."  We should call it iAda and
> sell it to Steve Jobs. :-)
>
> Implementation matters to some people, and it's not my job to decide
> when it should and shouldn't matter to them.  Of course, maybe that
> *is* your job...I don't want to be presumptuous. :-)
>
> Sometimes, when you're not building an airplane, you just want to use a
> data structure you know works and not have to do a lot of performance
> benchmarking.  In this case, the ARM only guarantees O((log n)**2)
> performance for particular operations, but a red-black tree should
> perform significantly better, so awareness of the implementation might
> be nice.
>
> I don't really disagree with your philosphy of "trust the container"
> all that much, though, and I'm not trying to start an argument.  So,
> hopefully the smiley emoticons did their job in conveying that.

I think that in a case like this, the truth is somewhere in between.
Like Randy said, in most cases you should not need to care about the
exact implementation.  However, often one does care that an
implementation works well for certain patterns of operations.  For
example, you might have a container-type package that supports
"insert" and "search" operations; but a user that wants to insert all
the data first, calling the Insert operation on data that's already
sorted, and then do searches, would probably prefer a different
implementation than a user that is going to be using the Insert
operation interspersed with searches throughout the program.

In my view, the OP shouldn't have said "I need a self-balancing binary
search tree" or "I need a red-black tree", but simply saying "I need
something that represents an ordered set of data" isn't always good
enough, either.  Sometimes it is.  But ideally it should be something
like "I need something that represents an ordered map, that is
optimized for arbitrary sequences of insertions, deletions, and
lookups" or whatever the needs are.  (And to *really* dream, an
implementation could provide an operation in a child package to allow
the caller to select from a set of optimization options and then
provide alternate implementations.  No, I'm not volunteering to do the
work :) )

                                 -- Adam