This lecture covers Binary Search Trees (BSTs), which are a special kind of binary tree that maintains a sorting invariant on its elements. It combines the advantages of a sorted array (i.e. fast lookup with binary search) with the flexibility of a linked list (i.e. efficient insert/remove operations anywhere in the data structure).
BSTs are the foundation of "industry-strength" implementations of several application-oriented data structures, including sets and maps. We'll particularly focus on maps, since we haven't discussed them previously and they are a key part of project 5 in EECS 280.
In some of the videos for this lecture, I might refer to implementing a binary search tree or map in project 5. That's project 6 this term.
|
1: Intro to Binary Search Trees
In essence, a binary search tree is a regular binary tree where each node's left subtree contains lower values and right subtree contains higher values. Let's take a look at some specifics as well as the reason this leads to efficient performance. |
|
2: Recursive Functions on BSTs
2.1
We can work with binary search trees using a similar recursive approach to regular binary trees, except that we can make an informed decision about which subtree to explore based on the sorting invariant.
2.1 Exercise:
bst_contains()
Implement the You're welcome to check your solution with this walkthrough video. |
|
3: BST Implementation on Project 6
It's also worth a bit of time to take a look at how a binary search tree could be realized as a C++ class, including some of the specifics for the implementation you'll work with in EECS 280 project 6. (Sorry - I recorded this video last year, when it was project 5.) |
|
4: Building a Set on a BST
Now, let's turn to some useful data structures implemented via a binary search tree. First, we'll consider a BST-based set, which will outperform the other array-based implementations we've seen previously. (Please ignore the references to the classifier application where you use a map… you've already done that this term in project 4.) |
|
5: Building a Map on a BST
In this video, we'll introduce the idea of a map as an associative container where we can store and retrieve values according to a particular key. Then we'll look at the fundamental approach we could use to implement a map with a BST. |
|
6:
Map Implementation
Finally, a few practical tips and tricks for Let's take a tour of each component in the Here's also an overview of what each of the three main |