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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s