Help with Trees in Python


#1

To be honest, this topic does not belong in 'functions', but I couldn't find a general concepts category. I really wanted to ask about any knowledge that anybody had on trees and writing/formatting them in python. I don't need them for anything specifically, but my dad is building a looper guitar pedal using python and a raspberry pi and I just wanted to know more about trees because he's been explaining them as a whole to me, but I just wanted a deeper understanding of them if anybody could provide that. :slight_smile:


#2

Are you referring to a binary tree?


#3

we have a corner bar for anything non exercise related, it is under community lounge

i think before moving to threes, you should understand linked list, do you understand those?

What do you already know?

Python is a higher level language, if your understanding needs to go really deep, you should consider learned linked list in C.


#4

Nodes in a tree need to know their own data and its children. Say that's a number and two other nodes, just chuck that into a list and call it a node.

Depending on application you'll have very different requirements such as moving nodes, removing nodes, balancing the tree, being always balanced or just being able to balance it, being able to access any node by key or just by starting from the root, varying number of children, being ordered or not.

Usually the data is very simple (data + children, just stick them in a list or some such) and what really defines the tree is the operations you define for it.

Try implementing some operations for a binary (two children per node) search (values can be found quickly) tree with ints as its data. Some examples:

None  # empty tree
[3, None, None]  # single node which is both root and leaf, value 3
[8, [3, None, None], [10, None, None]] # root 8, left child 3, right child 10

Before you can do anything at all you'll need a way to add nodes, so you'd want a function that takes as input a tree, and the data to add - which returns a new tree, or perhaps modifies the old one (or do both versions)

In a binary search tree smaller values are on the left side and greater are on the right, that's how you determine where to add the new value.


With that in place you could use range to generate numbers and add them one at a time. Then you can start doing other operations:

  • does x exist in the tree?
  • what is the sum of the tree?
  • what is the greatest value in the tree?
  • how many nodes are there in the tree?
  • what's the average value?
  • what's the value of the deepest leaf?

(those questions all correspond to (very short) functions which all start operating at the root of the tree)

An interesting concept is folding, what you'd do is have a start value, then traverse the tree in order and apply a function to the current value and the value of the current node. For example:

def add(a, b):
    return a + b

tree = [8, [3, None, None], [10, None, None]]

print(fold(add, tree, 0))  # 21

The fold function would invoke the function as follows:
f(0, 3) # initial value and first node
f(3, 8)
f(11, 10)
And return the result of the last one, 21.


I disagree with @stetim94 on using C for any of this stuff, Python is among the best languages for exploring concepts, I'd sooner suggest Lisp, but that's probably best learnt as a first language or otherwise far later - not second or third. (Lisp has a way of putting the concepts in focus rather than the language itself, but is a lot like starting again from nothing after having started with Python/C/Java/Ruby/JS etc - which is really nice because it's like rediscovering programming even after having done it for years)