MIT 6.006 Lecture 6: AVL Trees, Tree Rotations & Guaranteed O(log n) Height
Proves via Fibonacci recurrence bounds that height-balance invariants keep AVL trees strictly O(log n) tall, then derives single and double rotations cleanly.
MIT 6.006 Introduction to Algorithms, Fall 2011
View the complete course: http://ocw.mit.edu/6-006F11
Instructor: Erik Demaine
More courses at http://ocw.mit.edu
Previous · Lecture 5
MIT 6.006 Lecture 5: Binary Search Trees & Runway Reservation Scheduling
Next · Lecture 7MIT 6.006 Lecture 7: Decision-Tree Ω(n log n) Lower Bound, Counting Sort & Radix Sort
Comments
Add a comment...Sign in