Lesson 1
Today we will begin a discussion about binary search trees. Some of this material will probably be review for you!
However, in future lessons, we will do a deeper dive than you have had in the past, learning about several variations on the basic BST idea.
This lesson will address the following learning goals in Group 8:
- Goal 8A: Binary Search Trees:
- Use tree terminology (size, height, root, node, edge, leaf) to characterize binary search trees.
- Goal 8D: BST Complexity:
- Use asymptotic complexity terminology to describe the cost of insert and lookup for
- Randomized BSTs
- 2–3–4 trees
- Randomized BSTs
- Red–Black trees
- Splay trees
- Discuss the implications of those costs for usage.
- Use asymptotic complexity terminology to describe the cost of insert and lookup for
-
We will also start looking at some implementation ideas for BSTs which will be helpful in your upcoming homework!
Outline
- Before You Start
- Search
- Tree Terminology
- Binary Search Trees (Lookup)
- BST Insert
- BST Delete
- Time Complexity
This is a good moment to take a quick break.
- Encoding a BST in C++
- C++ Implementation: Insert
- C++ Syntax: Static Member Functions
- C++ Implementation: Insert Alternatives
Nearly done. A good time to stand up and stretch.
To receive credit: complete all pages above, then this page will be complete as well (and get a green check emoji at the bottom right of the page).
(When logged in, completion status appears here.)