URI CSC 212
Reminder that you must complete the pre-reading before each class.
On this page:
✔️ Pre-reading for Tuesday 7/20
✔️ Pre-reading for Wednesday 7/21
✔️ Pre-reading for Thursday 7/22
Pre-Reading for Self-Balancing Trees
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.
- 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)
- Read Red Black Tree (Basic Tutorial)
Pre-Reading for Heaps
Essential Questions
Before attending class, please complete the material below and use the following questions to guide your note-taking:
✔️ What is the purpose of a heap and how does it work?
✔️ How do heaps keep their balance?
✔️ What are the use cases and advantages of heaps?
Read/Watch/Review
Before attending class, please complete the material below:
- Read Data Structures 101: how to build min and max heaps
- Watch Data Structures: Heaps (11 min)
Pre-Reading for Heapsort
Essential Questions
Before attending class, please complete the material below and use the following questions to guide your note-taking:
✔️ How does the heapsort algorithm work?
✔️ What is heapsort’s time complexity and why?
Read/Watch/Review
Before attending class, please complete the material below:
- Read Heap Sort Algorithm
- This article also reviews heaps and their array-version implementation. If you are comfortable with your understanding of heaps, scroll down about half-way to “How Heap Sort Works?”
- Watch Heap sort in 4 minutes (4 min)