[Python-Dev] binary trees. Review obmalloc.c

[Josiah Carlson]

"Vladimir 'Yu' Stepanov" <vys at renet.ru> wrote:

> Comparison of functions of sorting and binary trees not absolutely 
> correctly. I think that function sort will lose considerably on
> greater lists. Especially after an insert or removal of all one element.

Generally speaking, people who understand at least some of Python's
internals (list internals specifically), will not be *removing* entries
from lists one at a time (at least not using list.pop(0) ), because that
is slow.  If they need to remove items one at a time from the smallest
to the largest, they will usually use list.reverse(), then repeatedly
list.pop(), as this is quite fast (in general).

However, as I just said, people usually don't remove items from
just-sorted lists, they tend to iterate over them via 'for i in list:' .


 - Josiah

As an aside, I have personally implemented trees a few times for
different reasons.  One of the issues I have with most tree
implementations is that it is generally difficult to do things like
"give me the kth smallest/largest item".  Of course the standard
solution is what is generally called a "partial order" or "order
statistic" tree, but then you end up with yet another field in your
structure.  One nice thing about Red-Black trees combined with
order-statistic trees, is that you can usually use the uppermost bit of
the order statistics for red/black information.  Of course, this is
really only interesting from an "implement this in C" perspective;
because if one were implementing it in Python, one may as well be really
lazy and not bother implementing guaranteed balanced trees and be
satisfied with randomized-balancing via Treaps.

Of course all of this discussion about trees in Python is fine, though
there is one major problem.  With minimal work, one can construct 3
values such that ((a < b < c) and (c < a)) is true.