31251 Lecture 8.5: Introduction to AVL trees

We saw in the last segment that the height of a BST is critical to its performance. In this segment we talk about actively rebalancing a tree so that its height remains small O(log n). We introduce AVL trees and show how the AVL property ensures that the height of the tree is always O(log n) when the tree has n keys.