Reminder that you must complete the pre-reading before each class.

On this page:
✔️ Pre-reading for Tuesday 4/6
✔️ Pre-reading for Thursday 4/8

---

Pre-Reading for Balanced Trees, Tuesday 4/6

Essential Questions

Before attending class, please complete the material below and use the following questions to guide your note-taking:

✔️ What are the advantages of self-balancing trees?
✔️ What are types of self-balancing trees?
✔️ What are rotations and how do they help create balanced trees?
✔️ How do self-balancing trees perform insertions and deletions?

Read/Watch/Review

Before attending class, please complete the material below:

• Read Different Self Balancing Binary Trees
• Watch Red Black Tree 1 The Rules (8 min)
• Watch AVL 1 Introduction (11 min)
• Explore this AVL Tree visualizer
• Explore this Red-Black Tree visualizer
• Watch Trees 9 Introduction to rotations (8 min)
• Watch Trees 10 Rotations (8 min)
• Watch Trees 11 Coding Rotations (12 min)
  • Note that the code is in Java but the C++ implementation would be very similar.

Some additional optional material:

• Read AVL Trees
• Read AVL Tree Insertion, Rotation, and Balance Factor Explained
• Read Red-Black Tree: Self-Balanced Binary Search Trees Explained with Examples
• Read Red Black Tree (Properties, Advantages, Inserting Nodes)

NEW: Check out this Tree Guide a previous student made for the class!

In Class

In today’s class we’ll be reviewing the properties of red-black, AVL, and other self-balancing trees.

---

Pre-Reading for Sets & Maps, Thursday 4/8

Essential Questions

✔️ How does a set work and when should it be used?
✔️ How does a map work and when should it be used?

Read/Watch/Review

Before attending class, please complete the material below:

• Read std::set
• Read std::map
• Watch Sets and Maps - Udacity (2 min)
• Watch Set and Maps (7 min)

In Class

In today’s class we’ll be applying sets and maps to use.