Working with Binary Search Trees
In the previous lesson of this recursion and trees course, we learned to implement a binary heap and explored how heaps are helpful when querying a dataset.
In this lesson, we’ll be implementing another special type of binary tree called a binary search tree. Binary search trees provide the ability to run efficient range queries on our datasets. Knowing how binary search trees work can help you understand the most efficient way to write a SQL query when using the WHERE clause.
As you work through the screens of this lesson, you’ll build a self-balancing binary search tree to demonstrate how to speed up range queries. You will also learn why you need a binary search tree to be self-balancing in order to the reduce the time complexity from O(n) to O(log n).
At the end of this mission, you will build a query range method to query a CSV file for a range of data.
As with all of our lessons, in this lesson you’ll get to apply what you’ve learned from within your browser so that there's no need to use your own machine to do the exercises. The Python environment inside of this course includes answer checking so you can ensure that you've fully mastered each concept before learning the next concept.
Objectives
Mission Outline
1. Introduction to the BST
2. Insert Multiple and Sorted Order
3. Searching the BST
4. Why We Need a Balanced BST
5. Maintaining a Balance (Part 1)
6. Maintaining a Balance (Part 2)
7. Maintaining a Balance (Part 3)
8. Enhancing the Node and BST Class
9. Adding the Range Query
10. Range Querying a CSV
11. Next Steps
12. Takeaways
Course Info:
Advanced
The median completion time for this course is 5.2 hours. View Details
This course requires a premium subscription. This course includes six missions and one guided project. It is the sixth course in the Data Engineer path.