Last time, we took a look at some basic Data Structures with Queues, Stacks, and Linked Lists. Right now, we're going to dive into a more complex data structures: Trees and Hash Tables.
A Tree is a data structure that simulates a tree structure with a root value and children nodes, each with the possibility of containing other children nodes, just like a family tree.
There are some terms you should probably know about Trees:
Root: The top node in a tree Parent: A node which has child nodes Sibling: Multiple nodes that share the same Parent node Descendant (of a certain node): A node that can be found within a Parent by traversing down its children Ancestor (of a certain node): Same as above, only backwards (traversing upwards to find a node, starting from the child) Leaf: A node without any children.
A Tree object contains the following methods and properties:
valueproperty, which stores the value that this tree was created with.
childrenproperty, which contains a list of all the children that this specific tree has.
addChildmethod, which takes in a value and creates a new Tree object while placing it into the current tree's
childrenproperty. Note that this new Tree has all of the methods and properties that its parent has, though it manages its own list of
children(it starts with a new, empty list).
containsmethod, which takes in a value and then searches the entire tree (along with its children, and its children's children, etc. but not its parents) for a tree with that specific value and returns either
falsedepending on whether the tree contains this value or not.
That one was more advanced than the others before it, but that's okay! I hope you're still hanging in there.
Hash Tables are possibly the most important data structure to be knowledgeable about. Rather than storing items in a data structure that traverses for objects in a linear fashion, Hash Tables utilize a special Hashing Function that allows items to be looked up and retrieved in a very quick manner. Because of this, they are one of the most efficient data structures in terms of time complexity (we'll talk about time complexity in another post).
First, let's assume that we would like to organize a collection of movies. We have a large stack of DVDs, Blu-Rays, and even some Laserdiscs (sweet!). Because of the variety of different types of movies we have and our extremely limited shelf space, we're going to put these movies into a bunch of bins we bought from Costco, and put them into the closet.
How do we decide which bin to put them in?
This is where a Hashing Function comes into play. It's going to take a value. In this case, let's say it's the name of the movie, and return a random number. Most hashing functions are very complex, but we're going to work off of the assumption that it's a magical box that takes in a value and returns a number without us needing to do any more work.
Now that we have a number, we'll go to our closet and find the bin with that specific number on it and place our movie into it.
The next time I need to find that movie, I'm going to simply pass in the movie name into my Hashing Function again and receive that exact same number from before back. I'll take that number, go back into my closet, into that bin, and retrieve my movie.
This is basically a Hash Table, in very high-level terms.
The image above attempts to illustrate a Hash Table. When you add an item to your Hash Table, the following happens:
- The Hashing Function takes a value (for example, 'The Dark Knight'), it returns a number
- Then the item (your DVD of 'The Dark Knight') is placed into the appropriate bucket within the Hash Table, as determined by your Hashing Function
The next time it's Batman Marathon Night, retrieve the item from the Hash Table:
- The Hashing Function takes in the same value as before ('The Dark Knight'), returning the same number as before
- The item ('The Dark Knight', on DVD) is retreived from the appropriate bucket.
- Make some popcorn (optional)
That's basically it! Again, this was a very high-level overview of Trees and Hash Tables, but I hope you were able to learn something from it.