W3151 Trees

From Coder Merlin
Within these castle walls be forged Mavens of Computer Science ...
— Merlin, The Coder
A Magnolia Tree

Prerequisites[edit]

Introduction[edit]

In Computer Science, a Tree is a hierarchical data structure that is very commonly used. Essentially, a 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. Because of this, the top most Node is called the root.

Trees are used as Data Structures, and this use can be seen everywhere: file systems, relationship hierarchies, visual displays and GUIs, and many more. This is why, as a developer, you ought to understand this data structure and how to apply it.

Structure[edit]

As mentioned, the structure of a Tree is made entirely of Nodes, where each node has some data that's being stored and contains 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; whereas the Node they come from is their Parent.

It's important to understand that in a General Tree, a Node can have only One Parent, but it can have 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 ends 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 a Node has, plus the number of children each of those Nodes has, and so on until you reach a Leaf. Put another way, the Degree of a Node is the number of Nodes that can call that Node one of its roots. This means that if there are a total of 20 Nodes in a Tree, the top Root will have a Degree of 20.

Additionally, in Trees, there's the concept of Level. The Root is always at Level 0, and its immediate Children are Level 1. Their children are level 2, and so on. Note that a Leaf can come up in any Level greater than 0, not only the lowest level in the tree.

For clarification on a Tree's structure, see the following diagram.

Structure of a Binary Tree

Quiz[edit]

1 What is the name of a Node without a Parent?

The Leaf
The Root
Every Node must have a Parent
The Height

2 What is the name of a Node without Children?

The Depth
A Leaf
The Root
The Lowest Level

3 True or False: A Tree's leaves must be at the Tree's lowest Level.

True
False

4 True or False: A General Tree can have any number of Nodes as Children.

True
False

Usages[edit]

As noted, Trees have many uses in the real world. Most notably, they're used for storing data that lends itself to be hierarchical. The common example, of course, is 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 might have hierarchies implemented into collectible items. Websites have tree-like hierarchies in their URLs. Enterprise applications in CAD or digital art software might store their 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 using Tree Data structures very common and is why knowing Trees algorithms is so important.

Quiz[edit]

1 What relationship do Trees represent in their method of storing data?

A hierarchical relationship
A lack of a relationship
A dynamic relationship
A linear relationship

2 How do trees differ from a data structure such as a Graph?

Graphs provide a statistical understanding of data, but Trees show relationships between data
Graphs show relationships between data, but Trees represent data hierarchically
Graphs provide a hierarchical view of data, but Trees organize them based on an arbitrary relationship
Graphs store data in a nonlinear fashion, but Trees store data linearly

3 True or False: General Trees are primarily used to create more complex trees.

True
False

4 True or False: Trees are implemented in many systems in some capacity, whether as a general tree or as one of its varieties

True
False


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. This should be rather straightforward 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 start by using exclusively Strings. We also have two other variables: a list of children and a parent. Note that the parent can 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 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 once the Tree is defined. 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 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 parent Node.

Now, we want to be able to see our tree. To do that, we'll implement an Extension on the Node class to allow us 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 used 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 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 that the Tree is filled more efficiently. In the meantime, we can implement a search function into our Tree. To do this, we 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 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 and 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.

Implemented Tree.png

Think about what functions you can add or how you can customize the data structure to be more efficient.

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) that 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. You can use more specialized trees for their time and space complexity. These are good as alternatives to data structures, such as Arrays and Linked Lists and provide situational advantages. Begin thinking about how more specialized trees might work.

Key Concepts[edit]

Key ConceptsKeyConceptsIcon.png
  • Trees are data structures meant to show hierarchical relationships and are made up of Nodes where each Node has one parent and a list of children
  • The Root is the top of a tree and has no parents, but 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]

ExercisesExercisesIcon.png
  • Look at the code sample above and try to improve the efficiency of filling the tree with a recursive function. Refactor the code if needed.
  • Try to implement Levels to each Node, then try to make a method that finds all the Leaves of a tree and print each Leave's value with its level.
  • Try to implement limits on how many children each Node may have. See how this effects the Tree.

References[edit]