No trees in the stdlib?
backup95 at netcabo.pt
Fri Jun 26 20:57:42 CEST 2009
> In article <006078f0$0$9721$c3e8da3 at news.astraweb.com>,
> Steven D'Aprano <steve at REMOVE-THIS-cybersource.com.au> wrote:
>> Hash tables (dicts) are useful for many of the same things that trees are
>> useful for, but they are different data structures with different
>> strengths and weaknesses, and different uses. To argue that we don't need
>> trees because we have dicts makes as much sense as arguing that we don't
>> need dicts because we have lists.
> The problem is that trees are like standards: there are so many to choose
> from. Each has its own tradeoffs, and because Python dicts and lists can
> substitute for many of the traditionals uses of trees, the tradeoffs are
> less clear. I think nobody would object to adding trees to the standard
> library, but it will certainly require a clear PEP, preferably with a
> pointer to an existing PyPI library that has acquired real-world use.
Wish I had asked this before this year's GSoC started.
What's lacking is an associative array that preserves ordering, doesn't
require a hash function and has fast insertions and deletions in
O(log(n)). The particular algorithm to achieve this is a secondary
issue. It's a BST for sure, AVL vs RBT vs something else. It's my fault
for having opened the topic with simply "trees" instead, it would have
avoided this vagueness problem, but I'm genuinely surprised to know
there are no data structures that efficiently support such a common need
in Python. And I really enjoy the using this language.
More information about the Python-list