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 -- https://mail.python.org/mailman/listinfo/python-list