No trees in the stdlib?

[Tom Reed]

Why no trees in the standard library, if not as a built in? I searched
the archive but couldn't find a relevant discussion. Seems like a
glaring omission considering the batteries included philosophy,
particularly balanced binary search trees. No interest, no good
implementations, something other reason? Seems like a good fit for the
collections module. Can anyone shed some light?

Thanks.

 

[Aahz]

Why no trees in the standard library, if not as a built in? I searched
the archive but couldn't find a relevant discussion. Seems like a
glaring omission considering the batteries included philosophy,
particularly balanced binary search trees. No interest, no good
implementations, something other reason? Seems like a good fit for the
collections module. Can anyone shed some light?

What do you want such a tree for? Why are dicts and the bisect module
inadequate? Note that there are plenty of different tree implementations
available from either PyPI or the Cookbook.

 

[João Valverde]

What do you want such a tree for? Why are dicts and the bisect module
inadequate? Note that there are plenty of different tree implementations
available from either PyPI or the Cookbook.

A hash table is very different to a BST. They are both useful. The
bisect module I'm not familiar with, I'll have to look into that, thanks.

I have found pyavl on the web, it does the job ok, but there no
implementations for python3 that I know of.

Simple example usage case: Insert string into data structure in sorted
order if it doesn't exist, else retrieve it.

 

[João Valverde]

A hash table is very different to a BST. They are both useful. The
bisect module I'm not familiar with, I'll have to look into that, thanks.

I have found pyavl on the web, it does the job ok, but there no
implementations for python3 that I know of.

Simple example usage case: Insert string into data structure in sorted
order if it doesn't exist, else retrieve it.

Crap, sorry about the mixed identities, I'm not using my own machine.
The original post is mine also.

 

[João Valverde]

A hash table is very different to a BST. They are both useful. The
bisect module I'm not familiar with, I'll have to look into that, thanks.

I have found pyavl on the web, it does the job ok, but there no
implementations for python3 that I know of.

The main problem with pyavl by the way is that it doesn't seem to be
subclassable (?). Besides some interface glitches, like returning None
on delete if I recall correctly.

There's also rbtree, which I didn't try. And I think that's it. On the
whole not a lot of choice and not as practical for such a common data
structure.

 

[Chris Rebert]

A hash table is very different to a BST.  They are both useful. The bisect
module I'm not familiar with, I'll have to look into that, thanks.

I have found pyavl on the web, it does the job ok, but there no
implementations for python3 that I know of.

Simple example usage case: Insert string into data structure in sorted order
if it doesn't exist, else retrieve it.

That's pretty much the bisect module in a nutshell. It manipulates a
sorted list using binary search.

Cheers,
Chris

 

[Stefan Behnel]

Besides some interface glitches, like returning None
on delete if I recall correctly.

That's actually not /that/ uncommon. Operations that change an object are
not (side-effect free) functions, so it's just purity if they do not have a
return value.

Although practicality beats purity, sometimes...

Stefan

 

[Miles Kaufmann]

That's pretty much the bisect module in a nutshell. It manipulates a
sorted list using binary search.

With O(n) insertions and removals, though. A decent self-balancing
binary tree will generally do those in O(log n).

-Miles

 

[Jason Scheirer]

What do you want such a tree for?  Why are dicts and the bisect module
inadequate?  Note that there are plenty of different tree implementations
available from either PyPI or the Cookbook.

....And heapq is more-or-less an emulation of a tree structure in its
underlying model. I once wrote a binary sorted tree data structure for
Python in C. It performed anywhere from 15-40% worse than dicts. I
think with optimization it will only perform 10% worse than dicts at
best.

Oh hey maybe that is why trees aren't an emphasized part of the
standard. They are going to be much slower than the ultra-optimized
dicts already in the standard lib.

 

[João Valverde]

A hash table is very different to a BST. They are both useful. The
bisect module I'm not familiar with, I'll have to look into that, thanks.

I have found pyavl on the web, it does the job ok, but there no
implementations for python3 that I know of.

Simple example usage case: Insert string into data structure in sorted
order if it doesn't exist, else retrieve it.

After browsing the bisect module I don't think it is the complete
answer. Please correct me if I'm mistaken but...

Ignoring for a moment that subjectively I feel this is not very pythonic
for my use case, if I get back the insertion position, doesn't that mean
I have to go over on average N/2 items on a linked list to insert the
item in position? Maybe less for sophisticated implementations but still
O(n)? That doesn't compare favorably to the cost of (possibly) having to
rebalance a tree on insertion.

 

[João Valverde]

...And heapq is more-or-less an emulation of a tree structure in its
underlying model. I once wrote a binary sorted tree data structure for
Python in C. It performed anywhere from 15-40% worse than dicts. I
think with optimization it will only perform 10% worse than dicts at
best.

Oh hey maybe that is why trees aren't an emphasized part of the
standard. They are going to be much slower than the ultra-optimized
dicts already in the standard lib.

But a dict can't be used to implement a (sorted) table ADT.

 

[João Valverde]

That's actually not /that/ uncommon. Operations that change an object are
not (side-effect free) functions, so it's just purity if they do not have a
return value.

Although practicality beats purity, sometimes...

Stefan

I didn't know that. But in this case I think purity gets pummeled every
time It's still not making sense to force a lookup to fetch something
before deleting (another lookup operation). If that were imposed by
python's internal machinery I'd suggest fixing that instead.

 

[João Valverde]

I didn't know that. But in this case I think purity gets pummeled
every time It's still not making sense to force a lookup to fetch
something before deleting (another lookup operation). If that were
imposed by python's internal machinery I'd suggest fixing that instead.

To be clear what I mean by that is that it's just reference passing so
it can't generate programmatic errors.

 

[Chris Rebert]

After browsing the bisect module I don't think it is the complete answer.
Please correct me if I'm mistaken but...

Ignoring for a moment that subjectively I feel this is not very pythonic for
my use case, if I get back the insertion position, doesn't that mean I have
to go over on average N/2 items on a linked list to insert the item in

Linked list?! Python lists are *array-based*.
<"You must be new here" joke redacted>

Cheers,
Chris

 

[João Valverde]

After browsing the bisect module I don't think it is the complete
answer. Please correct me if I'm mistaken but...

Ignoring for a moment that subjectively I feel this is not very
pythonic for my use case, if I get back the insertion position,
doesn't that mean I have to go over on average N/2 items on a linked
list to insert the item in position? Maybe less for sophisticated
implementations but still O(n)? That doesn't compare favorably to the
cost of (possibly) having to rebalance a tree on insertion.

I was indeed corrected on this shameful blunder, but in my defense array
based lists are implementation dependent and the case for trees can be
made on deletion.

 

[Steven D'Aprano]

I once wrote a binary sorted tree data structure for Python in C. It
performed anywhere from 15-40% worse than dicts. I think with
optimization it will only perform 10% worse than dicts at best.

Oh hey maybe that is why trees aren't an emphasized part of the
standard. They are going to be much slower than the ultra-optimized
dicts already in the standard lib.

But dicts require hashable keys, and are in arbitrary order. You can't
(for example) traverse a dict in post-order.

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.

 

[Paul Rubin]

That's actually not /that/ uncommon. Operations that change an object are
not (side-effect free) functions, so it's just purity if they do not have a
return value.

But deletes in an AVL tree should not cause mutation. They should
just allocate a new root and path up to where the deleted node was.
That allows having references to the old and new versions of the tree,
etc.

 

[Paul Rubin]

That's pretty much the bisect module in a nutshell. It manipulates a
sorted list using binary search.

That lets you find an existing entry in log(n) time, but inserting
or deleting an entry still takes linear time. Also, you don't
get a persistent structure in the sense of functional programming.

 

[Stefan Behnel]

But deletes in an AVL tree should not cause mutation. They should
just allocate a new root and path up to where the deleted node was.
That allows having references to the old and new versions of the tree,
etc.

I doubt that there are many AVL implementations that do that. Plus, if
deletion doesn't delete, I'd happily consider that a bug.

Stefan

 

[Hallvard B Furuseth]

That's actually not /that/ uncommon. Operations that change an object are
not (side-effect free) functions, so it's just purity if they do not have a
return value.

It's purity that they don't return the modified tree/dict/whatever.
They can still return the deleted element and remain pure.