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

Vladimir 'Yu' Stepanov vys at renet.ru
Sat May 6 11:10:06 CEST 2006

Josiah Carlson wrote:

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

Josiah Carlson wrote:

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

Such problem arises at creation of the list of timers. I've never seen that particular use-case. Please understand something. I believe that trees can be useful in some cases. However, I don't believe that they are generally useful enough in Python, given that we already have key,value dictionaries and sortable lists. They become even less worthwhile in Python, given the total ordering problem that I describe later in this message.

I tiresome. It so :) Sorry for that.

Here that I have found through Google on a line " order statistic binary tree ":

http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic20/ Yes, that link does describe what an 'order statistic tree' is. One thing to note is that you can add order statistics to any tree wih one more field on each tree node. That is, you can have your AVL or Red-Black tree, and add order statistics to it. Allowing tree['x'] to return the associated value for the key 'x' (the same as a dictionary), as well as offer the ability to do tree.select(10) to get the 10th (or 11th if one counts from 0) smallest key (or key,value), or get the 'rank' of a key with tree.rank('x').

Thanks.

This problem has nothing to do with dictionaries and hashing, it has to do with the fact that there may not be a total ordering on the elements of a sequence.

It is sad. I did not know it. Therefore and have not understood.

I have looked in Google on "python dev total ordering". On intentions to correct this problem I have not found anything. It already earlier was discussed ?

-- Vladimir Stepanov

More information about the Python-Dev mailing list