Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #84034

Re: Trees

Show all headers | View raw

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

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Trees Zachary Gilmartin <zacharygilmartin@gmail.com> - 2015-01-19 17:06 -0500
  Re: Trees Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-01-20 10:08 +1100
    Re: Trees Michael Torrie <torriem@gmail.com> - 2015-01-19 16:19 -0700
    Re: Trees Devin Jeanpierre <jeanpierreda@gmail.com> - 2015-01-19 15:52 -0800
    Re: Trees Tim Chase <python.list@tim.thechases.com> - 2015-01-19 18:00 -0600
    Re: Trees Nicholas Cole <nicholas.cole@gmail.com> - 2015-01-20 09:23 +0000
    Re: Trees Paul Rubin <no.email@nospam.invalid> - 2015-01-20 10:02 -0800

csiph-web