[Python-ideas] A tree data structure for Python

[Andrew Barnert]

On Feb 17, 2016, at 09:52, Stephan Foley <foley12723 at gmail.com> wrote:
> 
> Hello and thanks for the reply.
> 
>> On Wed, Feb 17, 2016 at 12:30 PM, Andrew Barnert <abarnert at yahoo.com> wrote:
>> 
>> Do you want it to be fixed-n-ary or arbitrary branching? Values in all nodes, or only the leaves? Does it need O(1) size or depth? Single-linked, back-pointers, or threaded? Mutable or copying? Are trees and nodes separate types (and, if so, is a subtree a tree in its own right)? What algorithms do you need besides BFS and DFS (pre-, in-, and post-order) visits?
> 
> Yes, I'm looking online and neither C++ nor Java have a tree class for
> the same reason. Rolling your own tree is very easy, but developing
> something useful for everyone can involve a lot of overhead.

It's not so much the overhead, as the design decisions. You need parent pointers; I not only don't need them, but need subtrees that don't keep their parents alive. I need threading, you don't want it, and don't want on do the log N work on each update to fix up the threads you're never going to use but the type demands them. You want first child and next sibling, I want all children. And so on. In most of there cases, there's no structure or API that's going to make us both happy.

That's why a functional design works much better than an OO design for this particular problem. It's hard to explain in text, but easy to show in code, so check https://github.com/abarnert/treestuff