Summary of Abstract Data Types (ADT)

    Over the past few weeks we've been working with recursion and a few new abstract data types. Since I've already talked about recursion in a previous post, I'll be talking about abstract data types in this post. An ADT specifies a set of operations (or methods) and semantics of operations (what they do), but it does not specify the implementation of the operations (that's what makes them abstract).

    The first ADTs that we learned in class were the Stack and Queue. Both stacks and queues are collections which means that they are data structures that contain multiple elements. They are also generic data structures which means that we can add any type of items to it (int, string, float, etc.). In class we implemented the stack and queue with python lists to use their built-in append, remove, and pop methods.

    A stack is last-in, first-out which means that the last item that is placed onto the stack will also be the first item to be removed from the stack. Our implementation of the stack had 3 main methods: pop, is_empty, and push. Since we implemented our stack as a list, we were able to use the pop method the exact same way for the stack and for the push method we used the list's append method. For the is_empty method we just compared our stack to and empty list, [].

    A queue on the other hand, is first-in, first-out which means that the first item that is placed onto the queue will also be the first item out of the stack (like a line if you were to line-up for something). The implementation for the queue was very similar to the stack. Both the queue method and is_empty method had the exact implementation as the pop method and is_empty method for the stack, but the dequeue method for the queue did not use the list's pop method, it used the remove method instead to remove the item at position 0.

   The next ADT that we learned and worked with was the Tree. Trees simulate a hierarchical tree structure, with a root value and subtrees of children, represented as a set of link nodes. Trees are made up of nodes or vertices with edges without having to cycle. The root of the tree is also known as the top node of the tree and a leaf is a node with no children.

    Another type of tree that we've started to work with is the Binary Search Tree (BST). A BST is a tree where each node contains up to 2 subtrees and each subtree itself is a BST. The left subtree of any node contains nodes with keys that are strictly less than the node's key and the right subtree of any node contains nodes with keys that are strictly greater than the node's key.

   Since BST keep the keys in order it is very easy to find any key in the tree without visiting all the nodes. For example, let's say we want to know if the BST contains the key '7'. We can look at the root and determine which which subtree the key could possibly be in. Since we know that 7 < 8 we can just look in the left subtree (that means we don't even have to look at the entire right subtree!). Now the current node we are looking at has the key '3' and we know that 7 > 3 so we can ignore node 3's left subtree and only look in the right subtree. And since we know that 7 > 6 we can then just look at the right subtree. BAM! We just found '7' in the BST without looking at all the nodes. Now you might be thinking "oh yea, big whop! we didn't have to look at a few nodes and we only saved like 1-2 seconds...", BUT YOU'RE WRONG! Imagine if you have a HUGE BST that is symmetrical in terms of height, each time you compare the keys you are eliminating half the possible subtrees you would have to look through (THINK OF ALL THAT TIME YOU'RE SAVING!).

    Now that we understand how BST work we can easily write some recursive code for it to determine if a BST contains a certain value.

    This first thing this code does is check if there even exists a BST. It then determines if the value we are looking for is less than the current node's value or greater than the current nodes value. If it falls under one of these categories then it will use recursion and call bst_contains on its respected subtree. But if it doesn't fall under one of these categories it will return True because the current node we are looking at contains the value we are looking for!