Trees

[Tim Chase]

On 2015-01-19 16:19, Michael Torrie wrote:
> On 01/19/2015 04:08 PM, Steven D'Aprano wrote:
> > Zachary Gilmartin wrote:
> >> Why aren't there trees in the python standard library?
> > 
> > Possibly because they aren't needed? Under what circumstances
> > would you use a tree instead of a list or a dict or combination
> > of both?

While not an abundance of times, I've had a plurality of occasions
when I've wanted characteristics of a red/black tree where I wanted
O(log n) insertion/deletion/initial-access and O(1) access to
neighbors.

> > Also, what sort of tree? Binary tree? Binary search tree?
> > Red/black tree? AVL tree? Splay tree? B-tree? T-tree? Scapegoat
> > tree? General n-ary tree? Every possible type of tree yet
> > invented?
> 
> Don't forget left-child,right-sibling trees.
> 
> As I go through your list of trees, I can't find any tree type that
> cannot be easily and efficiently constructed with lists, possibly
> with dicts.

While the data-structures can easily be composed out of lists/dicts,
the algorithms that go along with them (such as red/black trees with
their insertion/deletion gymnastics) would be nice to have in the
stdlib so they wouldn't have to be reimplemented (or sought out and
downloaded, and added to the configuration/distribution) every time
someone wanted that particular tree's characteristics.   Much of that
could be addressed with a library of algorithms much like heapq
operates on a list.

-tkc