Sunday 8 March 2015

Week 8 - Trees and Binary Trees

This week we've been taught how to create trees and binary trees. Trees look something like this:
Trees are a set of nodes with directed edges between pairs of nodes. An edge connects a parent node to a child node. The node at the very top is called the Root Node which is the one node that does not have a parent in the tree. The parent node is a node that contains children. Also the length of the path is the number of edges in the path of the tree. 

These are some more useful terminology that is helpful for the structure of trees:
  • A leaf is a node with no children (such as #1, 4, 7, 10 in the diagram)
  • Internal node is a node with one or more children (#5, 3, 8 in the diagram)
  • Subtree is a tree formed by any node and its descendants and the edges connecting them 
  • Height of the tree is the maximum path length + 1 
  • Depth is the height of the whole tree minus the height of the tree rooted at that node
  • Arity or branching factor is the maximum number of children for any node
We were also introduced to a specific kind of tree which is called the Binary Tree which looks like:

Distinctive factors that make the binary tree special is that..
  • Binary Trees is a tree with branching factor of 2. Which means that each node has a maximum number of 2 children. 
  • The children in a binary tree are called left and right child 
  • Binary Search Trees have a specific property which is that for evener node, its value is greater than all values in its left subtree and less than all values in its right subtree. 
    • It's good to note that each subtree as well is a BST.
    • For example, in the diagram above, all of the nodes on the left child side of 68 will always be less than the nodes values on the right child side of 68 and the pattern still continues as you keep going down the subtree. For example, look at the bottom of the subtree of the node 11. -22 is less than 2 which means the left side is always less than the right side.
Through out the labs, we have worked on some recursive methods that calls on trees that gets a better idea of how they work. Here's an example: 

(Will insert pictures later when I get on my CDF account)

You can note that the base case is mostly when there is no children (if self.left == None and self.right == None) which always occurs at the very bottom of the tree. 

I think I still need to review this concept as its difficult to wrap my head around but doing the labs really do help practising the concept lectured in class. I really hope the TA strike comes to an end soon as it's my main source of understanding computer science concepts better and its where everything starts to make sense with my TAs help even for CSC165... but other than that, ill try my best to understand it on my own and will try my best on the next test...............ha ha... anyway Happy Slogging and good luck on Test 2 everyone! :) 

2 comments:

  1. Nice use of visuals! They really help to understand the content and also give your blog post a visual appeal.

    ReplyDelete
  2. This comment has been removed by the author.

    ReplyDelete