Computer Science 385
Design and Analysis of Algorithms
Spring 2019, Siena College
Lecture 20: 2-3 Trees; AVL Tree Review
Date: Monday, March 11, 2019
Agenda
- Announcements
- Problem Set 3: [HTML] [PDF] writeup due today
- Problem Set 4: [PDF] is your next focus: all written problems
- Lab 6: Working With Recurrences due in lab this week for those who did not finish up
- Levitin's spanning tree constructions quiz postponed to date TBA
- Binary trees (a very quick data structures review)
- terms, properties, and traversals
- binary search trees, AVL trees
- 2-3 trees
- In-class lab exercise to practice with AVL and 2-3 trees
Terminology
- binary trees (many associated terms)
- 2-3 trees
- 2-nodes and 3-nodes
- perfectly balanced