[Python-Dev] binary trees.

[Vladimir 'Yu' Stepanov]

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