[Python-Dev] binary trees.
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