Binary Trees, Part 2: AVL

MIT 6.006 Introduction to Algorithms, lecture 7, explained in plain English

Want this lecture to stick? In LessonBound you get checked practice questions for every part, can ask about anything you don't get, and can listen with your screen off. Free, no ads.

Learn this lecture free

Watch or read the original lecture: MIT OpenCourseWare.

Part 1 · 0:00–10:00

This part explains how binary trees store items in order, why a tree's height controls how fast it works, and why we need a tree that stays short.

Key ideas

A binary tree stores items in a hidden order called the traversal order: visit the left side, then the node, then the right side. We never write this order down as a list. 1:40
The height of a tree is the longest path going down from the root, counting edges. Our operations take about h steps, so a tall, thin tree can be slow, up to linear time in the worst case. 2:46
A set-style tree keeps keys in increasing order. Searching works like binary search on a sorted array: compare the key, then go left or right. 5:13
The goal for today is to keep the height near log n, so every operation runs in log n time. We do this by changing the tree's structure, not by changing what it stores. 3:07
To find the ith item in a sequence tree, we need to know the size of each subtree. The last index in a subtree is its size minus 1. 9:34

Words to know

height: How far down the longest path goes from a node to the bottom, counting the lines (edges) you cross.
traversal order: The order you get when you visit every node in a tree: left side first, then the node, then the right side.
binary search tree: A tree where every key on the left of a node is smaller and every key on the right is bigger, so you can search it like a sorted list.
size: The number of nodes in a subtree, including the node at its top.

Example

Think of a sorted phone book. You open it in the middle, then go left or right, and each step cuts the choices in half. A short, balanced tree works the same way, so you find what you want in only a few steps.

3 checked practice questions for this part are in the app.

Part 2 · 10:00–20:00

This part shows how a binary tree can find the item at any position, and how each node can store a size so that inserts keep the positions correct.

Key ideas

If each node knows how many nodes are in its left subtree (its nL), you can find the item at position i by a process much like binary search. 10:53
Compare i with nL. If i is smaller, go left. If i equals nL, this node is the one you want. If i is larger, go right, and subtract nL plus 1 from i because the numbering starts over inside the right subtree. 11:37
You can insert at position i by finding the node at that position and inserting just before it. This works only if the sizes on the path are updated, because otherwise the positions go wrong. 14:54
A subtree property is a value a node can work out in constant time from values stored on its two children. Size is one such property: a node's size is its left size plus its right size plus 1. 17:38
Each node stores its size, so reading it takes constant time instead of counting the whole subtree. The hard part is keeping every stored size up to date as the tree changes. 19:55

Words to know

subtree: A smaller tree that sits inside a bigger tree. It is a node together with everything below it.
traversal order: The fixed order in which you visit all the nodes of a tree, one after another. It gives every item a position in the sequence.
recurse: To call the same process again on a smaller piece of the problem, such as moving down into the left or right subtree.
constant time: A task that takes about the same short amount of time no matter how big the tree is.

Example

Think of a row of coats on a hanger rail where each hook also has a tag saying how many coats hang on the left side of it. To find coat number 7, you check the tags and move left or right, the way a binary search does, instead of counting from the first coat. This is only an analogy to help the idea click.

3 checked practice questions for this part are in the app.

Part 3 · 20:00–30:00

This part explains how to keep useful information up to date in each subtree of a binary tree, and why only certain kinds of information can be kept up to date cheaply.

Key ideas

Adding or removing a leaf (a node with no children) only changes the subtrees that contain it, which are its ancestors, the nodes above it on the path to the root. 20:42
Each ancestor can be updated in constant time using a fixed update rule, so one change costs about h steps, where h is the height of the tree. 22:55
A subtree property can only depend on a node and its children, not on the rest of the tree. Subtree size, sum, min, and max all work this way, but a node's index does not. 24:26
The goal is to make the height h about log n, which gives a balanced binary tree and makes each operation fast. 26:40

Words to know

leaf: A node in a tree that has no children below it.
ancestor: A node above another node on the path up to the root of the tree.
subtree property: A stored value for a node that depends only on that node and the nodes below it, so it can be updated by walking up the tree.
balanced binary tree: A binary tree whose height is about log n, so it stays short and fast to search, even as it grows.

Example

Think of a company org chart where each manager keeps a count of everyone in their team. When one new person joins at the bottom, only the managers above that person need to add one to their count, not everyone in the company. That is how a subtree property works: a change only affects the nodes above it.

3 checked practice questions for this part are in the app.

Part 4 · 30:00–40:00

This part explains how rotations can rebalance a tree without changing its order, and how the AVL height-balance rule keeps the tree's height small.

Key ideas

A rotation is a tool for rebalancing a tree. It must not change the data the tree holds, which is the order you get when you walk through its nodes. 30:00
Many different tree shapes can hold the same traversal order. The lesson calls this redundancy, and rotations use it to change the shape while keeping the order. 30:43
A rotation moves nodes up and down. Some nodes get shallower and others get deeper, so a very deep node can be moved closer to the top. 33:47
In an AVL tree, the rule is that for every node, the heights of its left and right subtrees differ by no more than 1. The lesson calls the difference the skew, and it must be minus 1, 0, or plus 1. 35:11
The lesson proves that if every node follows this rule, the tree's height grows only logarithmically with the number of nodes. The worst case has node counts that grow like Fibonacci numbers, which grow exponentially. 39:38

Words to know

rotation: A small change to how nodes are linked, where one node moves up and its neighbor moves down. The order of the data stays the same.
traversal order: The order you get when you visit every node in the tree in a fixed walk. The lesson says this order must never change.
skew: The difference between the height of a node's right subtree and the height of its left subtree. In an AVL tree it must be -1, 0, or +1.
height: The longest downward distance from a node to a leaf, meaning a node with no children at the bottom of the tree.

Example

Think of a set of books that must be read in alphabetical order. You can stack them in one tall pile or spread them into a few short piles, as long as reading them left to right still gives the same order. A rotation changes the piles to a shape that is easier to search, and the reading order stays the same.

3 checked practice questions for this part are in the app.

Part 5 · 40:00–50:00

This part shows why AVL trees stay balanced in height, and how storing each node's height lets the tree fix itself with rotations after an insert.

Key ideas

An AVL tree's height can be at most about twice the logarithm of the number of nodes. The number of nodes grows at least exponentially with height, so the height stays small. 40:00
Height is a subtree property, so we can store it in each node. This is called subtree augmentation. 42:45
A node's height can be updated in constant time: take 1 plus the larger of its two children's heights. 43:49
A rotation changes only a few pointers, but the stored heights of the rotated nodes and their ancestors must be updated. 44:30
After inserting a leaf, only the ancestors of that leaf can become unbalanced. We check them from bottom to top and fix the lowest bad one. 46:20

Words to know

subtree augmentation: Storing extra information in each node, such as its height, that depends only on that node's own subtree.
skew: The difference between the heights of a node's left and right subtrees. In an AVL tree, the skew must stay at minus 1, 0, or plus 1.
rotation: A small change to the pointers that moves one node up and another node down, keeping the tree in order while changing its shape.
ancestor: A node above another node on the path up to the root of the tree.

Example

Think of a company org chart where a new person joins a deep team. Only the managers on the chain of bosses above that person need to check whether their teams are still balanced. Managers in other branches do not need to look.

3 checked practice questions for this part are in the app.

Part 6 · 50:00–54:03

This part explains how an AVL tree fixes itself when it leans too far, so that it stays balanced and fast to search.

Key ideas

A node is out of balance when the heights of its two sides differ by more than 1. The tree then leans too far to one side. 50:00
In the easy cases, one rotation (a move that shifts nodes up or down while keeping the left-to-right order) fixes the lean. After that, every node is balanced again. 50:20
The hard case is case three, when the lean of y goes the other way. Here you look at y's left child, called z, and a single rotation makes things worse, so you use two rotations instead. 51:03
After fixing one node, the height of the whole tree may change, so you check the parent. You keep walking up the tree and fixing any node that is out of balance. 53:25
Because the tree stays balanced, each operation takes about log n steps, which is much faster than checking every node. 53:47

Words to know

height balanced: Each node's two sides differ in height by at most 1, so no side is much taller than the other.
rotation: A small rearrangement of a few nodes that moves one node up and another down, while keeping the order of the values the same.
skew: How much a node leans. It tells you whether the left side or the right side is taller at that node.
augmentation: Extra information stored in each node, such as its height or the number of nodes below it, that must be kept correct when the tree changes.

Example

Think of a stack of books on a shelf that starts leaning. A small shift of a few books can straighten the stack, but sometimes a bad shift makes it lean harder, so you have to move books in two steps instead. You keep checking the stack from the bottom up until the whole thing stands straight.

3 checked practice questions for this part are in the app.

← Lecture 6: Binary Trees, Part 1 · Lecture 8: Binary Heaps →

Notes written by AI (Claude) from the lecture's official transcript, so check anything important against the lecture. MIT OpenCourseWare · CC BY-NC-SA 4.0 · not affiliated with or endorsed by MIT. These notes are shared under the same license.

LessonBound · Free lecture notes · Privacy · Terms · New York