A binary search tree gives you O(log n) search, insert, and delete only when it stays reasonably short. Insert keys in sorted or nearly sorted order and the same tree degenerates into what is essentially a linked list, pushing every operation to O(n). AVL trees fix this by adding one simple rule: for every node, the heights of its left and right subtrees may differ by at most one. That difference is the node's balance factor, and whenever an insertion or deletion violates the rule, the tree repairs itself with local restructuring operations called rotations.
In this topic you will learn the AVL definition and its height guarantee, how to compute and update balance factors, and the four repair cases: single left and single right rotations for the "straight line" imbalances, and the left-right and right-left double rotations for the "zig-zag" cases. Insertion requires at most one rotation (single or double) to restore balance; deletion may require rebalancing at several nodes along the path back to the root, which is why it is treated separately.
The three videos below form a short, ordered sequence: definition and search, then insertion, then deletion. While watching, keep a pen handy and redraw each example yourself. Focus on three things: which node is the first unbalanced ancestor, which of the four cases applies based on the direction of the imbalance, and how heights and balance factors are updated after the rotation. Pausing to predict the rotation before the narrator performs it is the fastest way to build fluency for exams.
A compact introduction to AVL trees that defines the structure and walks through the search operation. Expect the balance condition, the role of node heights, and why searching an AVL tree works exactly like searching an ordinary BST but with a guaranteed O(log n) bound. Linked source code is provided on the channel's GitHub repository.
Michael Sambol's data structures series is a widely used, carefully scripted set of explanations, and this video covers the "motivation," "definition and properties," and "balance factor" subtopics before any rotation mechanics are introduced.
The longest video of the three, devoted to AVL insertion. It should cover how a new key is inserted as in a normal BST, how the imbalance is detected on the way back up, and how the rotation cases are chosen and applied to restore the AVL invariant.
Insertion is where single and double rotations are introduced most naturally, and the extra running time here gives room for worked examples of the left-left, right-right, left-right, and right-left cases you must be able to trace.
A focused treatment of AVL deletion. It should show the standard BST removal cases (leaf, one child, two children with a successor or predecessor) and then the rebalancing that follows, including the fact that deletion can require rotations at more than one ancestor.
Deletion is the subtopic students most often skip, and this video completes the set from the same instructor so the notation, diagrams, and terminology match the previous two videos exactly.
Together these videos directly serve MO1 and MO2. The first establishes why unbalanced BSTs degrade and what structural invariant AVL trees impose to prevent it, supporting the AVL portion of MO1. The insertion and deletion videos give you worked traces of the balance factor check and the single and double rotations needed to restore it, which is precisely the skill MO2 asks you to demonstrate. The height guarantee discussed throughout also supplies the O(log n) reasoning you will reuse when comparing AVL trees against heaps and tries for MO5; heaps and tries themselves (MO3, MO4) are covered elsewhere in the module.
These videos were chosen from YouTube on October 2, 2026. Each has captions; the player turns them on. Videos on YouTube can be changed or removed — if one no longer plays, tell your instructor. If a player does not appear, use its Watch on YouTube link.