W3151 Trees
Prerequisites[edit]
Introduction[edit]
In Computer Science, Trees are a hierarchal data structure that are very commonly used. At its core, the Tree is a series of nodes where each node contains some data and references one or multiple other nodes called Children. These structures are called Trees because of the visual resemblance between the data structure and a tree's roots. It's because of this that the top most Node is called the root.
The use of Trees as Data Structures can be seen everywhere: file systems, relationship hierarchies, visual displays and GUIs and many more. This is why developers ought to understand this data structure and how to apply it.
Structure[edit]
As has been mentioned, the structure of a Tree is made entirely of Nodes where each node has some data that's being stored and references to other Nodes lower in the tree. If you look at a Node in a tree, it will likely be referencing one or several Nodes beneath it. These Nodes that are being referenced are called the Children or Child Nodes while the Node they come from is their Parent.
Its important to understand that in a General Tree, a Node can only have One Parent but multiple children.
Now, looking at the Structure of a tree, it starts with The Root. The root is the very top of a Tree's hierarchy and can be recognized because it is the only Node that is not referenced to by another Node. Conversely, a Tree will end with Leaves. Leaves are simply the Nodes that do not reference any other Node.
In fact, the idea of The Root and Leaves lends itself into the idea of a Node's Degree. The Degree of a Node, when discussing Trees, simply refers to how many children does a Node have plus the Number of children each of those Nodes have and so on until you reach a Leaf. Said in another way, The Degree of a given Node is the number of Nodes that can call that given Node one of its roots. This means that if there are a total of twenty Nodes in a Tree, the top Root will have a Degree of 20.
Additionally, in Trees there's the concept of Level. The Root will always be Level 0 and its immediate Children will be Level 1, their children will be level 2 and so on. Note that a Leaf can come up in any Level greater than 0, not just the lowest level in the tree.
For clarification on a Tree's Structure, consult the following diagram.
Quiz[edit]
Usages[edit]
As we mentioned, Trees have many Usages in the real-world. Most notably, they're used for storing data that lends itself to be hierarchal. The common example being, of course, a file system. This is why the base of a file system is often called The Root. Indeed, Hierarchies are present in many day-to-day examples. Games may have hierarchies implemented into collectible items, Websites have tree-like hierarchies in terms of its URL, Enterprise applications in CAD or Digital Art Software may store its file data as a Tree, Large Data companies often contain much of their data in hierarchies for quicker response times when executing commands.
In fact, the General Tree can be used to implement more specialized data structures such as Binary Trees, which are often used for applications where time complexity is very important specifically in searching algorithms. This has made the usages of Tree Data structures very common and is why knowing Trees algorithms is so important.
Quiz[edit]
Swift Implementation[edit]
Here, we'll be implementing a general tree, this means we won't be putting in any limits on how many children a Node can have or anything like that, which means this should be rather straight forward to implement. As always, we'll start by making a Node class to handle all of our nodes.
class Node {
var value: String
var children: [Node] = []
var parent: Node?
init(value: String){
self.value = value
}
}
As you can see, every Node will have a value, in this tree we will use exclusively Strings to start off, additionally we have to other variables: a list of children and a parent. Note that the Parent may be nil for some Nodes, specifically the root. We also have it set so that a Node has no children by default. Finally, we have a simple init.
Now, we'll make a Tree class to handle the data structure and all of the methods it needs to have.
class Tree {
var root: Node
init(root: Node){
self.root = root
}
}
We will start by having a simple class where we must define the root Node upon defining the Tree. Now, we'll want to add a function that allows us to add a value wherever we want into the tree. A simple implementation of this is as follows.
func add(parent: Node, child: Node){
parent.children.add(child)
child.parent = parent
}
Here, all we're doing is asking for a Parent Node and the Child Node and then making a connection between them. Then we take the parent and add the child node to the parent's list of children. We'll then take the child node and set its parent value to the given parent Node.
Now, we'll want to be able to see our tree, so to do that, we'll implement an Extension on the Node class to allow us the ability to print Node classes
extension Node: CustomStringConvertible {
var description: String {
var text = "\(value)"
if children.isEmpty{ return text}
text += " {" + children.map { $0.description }.joined(separator: ", ") + "} "
return text
}
}
Finally, we can test our general tree. In the following we'll use our tree to implement the taxonomy of a Wolf, a Coyote, and a Tiger. Taxonomy is use in biology as a hierarchy of living creatures that is represented with trees.
var anamalia = Node(value:"Anamalia")
var chordata = Node(value:"Chordata")
var manamalia = Node(value:"Manamalia")
var carnivora = Node(value:"Carnivora")
var caridae = Node(value: "Caridae")
var felidae = Node(value: "Felidae")
var canis = Node(value: "Canis")
var panthera = Node(value: "Panthera")
var lupin = Node(value: "Lupin")
var latrans = Node(value: "Latrans")
var tigris = Node(value: "Tigris") //finish declaring our Nodes
var taxonomy = Tree(root: anamalia) //declare tree
taxonomy.add(parent: anamalia, child: chordata)
taxonomy.add(parent: chordata, child: manamalia)
taxonomy.add(parent: manamalia, child: carnivora)
taxonomy.add(parent: carnivora, child: caridae)
taxonomy.add(parent: carnivora, child: felidae)
taxonomy.add(parent: caridae, child: canis)
taxonomy.add(parent: felidae, child: panthera)
taxonomy.add(parent: canis, child: lupin)
taxonomy.add(parent: canis, child: latrans)
taxonomy.add(parent: panthera, child: tigris) //finish adding Nodes into Tree
print(anamalia) //print the root Node to see it and all its children
When we run this code, we would have made a successful Tree, however, it's a little clunky and inefficient. As an Exercise, think of how you can optimize the classes function so so that the Tree is filled in a more efficient manner. In the meanwhile, we can implement a Search function into our Tree. To do this, we'll add a recursive method in the Node class.
func search(value:String) ->Node?{
if value == self.value {
return self
}
for child in self.children {
let found = child.search(value: value)
if found != nil {
return found
}
}
return nil
}
All we're doing is looking at any given Node and seeing if that Node's value is the value we are searching for. If it isn't, we will look at the Node's children and search them, if that doesn't work we know that the Node is not in the tree. For consistency we will put this function into the taxonomy class as well where it will start searching from the root node by default.
We can test out the function by writing the following
print(taxonomy.search(value: "Lupin")!) //unpack the given optional Node to print it, will print "Lupin"
The following Tree Diagram shows the Tree we've made.
Think about what functions you can add or how you can customize the data structure for higher efficiency.
Beyond Basic Trees[edit]
From what you've learned about basic trees, you will soon be able to make more complicated, specialized tress (such as binary trees) which can be used for several algorithms and handling data. Among the most popular forms of trees are binary trees, AVL Trees, and Red Black Trees. More specialized tress can be used for their time and space complexity as alternatives to data structures such as Arrays and Linked Lists, providing situational advantages. Begin thinking about how more specialized trees may work.
Key Concepts[edit]
- Trees are data structures meant to show hierarchical relationships and are composed of Nodes where each Node has a single parent and a list of children
- The Root is the top of a tree and has no parents whereas the Leaves are the end of a Tree and have no children
- General Trees can be used to make more specialized trees that offer improved time and space complexities in certain operations
Exercises[edit]
- Look at the code sample above, try to improve the efficiency of filling a tree with a recursive function, refactor given code if necessary
- Try to implement Levels to each Node, then try to make a method that finds all the Leaves of a tree and print its value with its level
- Try to implement limits on how many children each Node may have, see how this effects the Tree
