[Python-Dev] binary trees. Review obmalloc.c (original) (raw)

Josiah Carlson jcarlson at uci.edu
Wed May 3 10:25:35 CEST 2006

"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:' .

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.

More information about the Python-Dev mailing list