Lesson 8.2: AVL Analysis

Video Lesson:

Slides	Annotated Slides	Video
8.2-avl-balance-203-1221.pdf Download 8.2-avl-balance-203-1221.pdf	PDF Download PDF	Recorded lecture Links to an external site. Access Passcode: b8=!cgU?

---

Readings:

• Carrano & Henry : Chapter 19.5 (AVL Trees)

 

---

Summary:

In this class, we face the terrible prospect of unbalanced BSTs and plan to address it by height-balancing. AVL trees have a specific prescribed balance property. We determine just how tall an AVL tree can be.

---

Learning Outcomes:

• Use the "height balance" of a binary tree to identify balanced vs. unbalanced trees.

• Explain the performance benefits of balanced BSTs.

• Analyze the height of a binary tree given its balance properties.

• Compare and contrast standard BSTs and balanced BSTs.

• Explain the impact of tree rotations on BSTs' height-balance and (lack of) impact on their search-tree property.