Entry 2: Trees

This week I've decided to talk about trees, as they seem to be the focus of the course at this time. As Professor Heap outlined, the name 'tree', while also corresponding intuitively to the species of plant, appears to come from graph theory.

As I'm sure the reader knows, the tree is a recursive data structure, defined in terms of its nodes, which in a tree contain both a value(say an integer) and some number of references(potentially zero) called children(which is a bit of mixed metaphor, next to all the plant stuff). A tree is a root node and its sub-trees(which each have a root node), and so on and so forth. At the bottom of a tree is a "leaf" which sensibly is a node which does not connect to anything(this is if a tree is finite; but practically I don't think we will ever have to deal with infinite trees except as an error).

By this definition a linked list is simply a tree with a root node and a single branch between each of its nodes. In fact a node is also a kind of tree, a root with no sub-nodes.

So far we've stuck mainly which with binary trees, which are, unsurprisingly, trees where each sub-node has two children(which may be other nodes or None). Binary trees obviously present some advantages: it's easier to write code to traverse them, for one, as one knows in advance that each node has two children(and therefore at most two subtrees). These are actually part of the focus of assignment two(which I need to get working on!).

Most of my interest in trees comes from their structure. It's very elegant, an elegance that comes from its recursive structure and implementation. What I'm not so sure about at this point is their utility. The only real 'use' for trees we've seen so far is their ability represent regular expressions in assignment two, but I'm not at all experienced with regular expressions, and therefore I can't quite speak to whether or not using trees with regular expressions is good for anything more than an academic exercise.

I can think of some data that trees would be useful for. For example, if for some reason you wanted to store a 'master list' of organisms, it would make a good deal of sense to do it with a tree. The root node would contain references to Animalia, Plantae etc, each of which would contain references to sub-classications, until finally one would reach the leaves, which would be species or sub-species. However, it doesn't seem like most data would be suited to a similar representation: I can't imagine wanting to represent a list of students in a school this way, for example.