Week 9 | Binary Search Trees!

We learn about Binary search Trees this week, You may ask what in the world is a  binary  tree? There are 4 basic conditions for Binary search tree:

1. The left subtree of a node contains only nodes with values less than the node’s values.
2. The right subtree of a node contains only nodes with values greater than the node’s values.
3. The left and right subtree each must also be a binary search tree.
4. There must be no duplicate nodes.

Intuitively this is a natual way to construct and maintain ordered lists. A real world implementation of a (BST) Binary Search Tree would be for a company who wants to keep  track of the date they first started doing business with a customer and have  the ability to search through this data base quickly. This can be done with a BST because they are self-balancing in the sense that they store data in their subtrees based on least and greatest values making it much faster to search the Tree structure for said company to access information. Also its good to know that the the rightmost child is the largest value in the entire tree, which allows for optimal performance when traversing a tree for a given value. A Binary Search Tree’s performance is  O(log n), which is very similar to binary search, in the way that with every iteration we were able to half the number of values we had to search through.

Advertisements

Week 8 | Recursive Structures | Linked Lists

This week we learned about a recursive structure called LinkedLists. The basic building blocks for Linked Lists are a sequence of nodes, each with a head (value) and a reference to rest (its successors). When we say the term linked we refer to each nodes having a reference in memory to the next node i.e Linked!

A linked list is either: the empty list, represented by None, or a node that contains an  object and a reference to the next node of the linked list.
linkedlist
“Searching for a value in a linked list implementation of an unordered list also uses the traversal technique. As we visit each node in the linked list we will ask whether the data stored there matches the item we are looking for.”
I find Linked Lists pretty interesting considering they can grow dynamically and there is no restriction on its size! Sounds so efficient right!