AVL Trees: Rebalancing After Every Insertion and Deletion

UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 15.2 Free with a free account

AVL Trees: Rebalancing After Every Insertion and Deletion

Data Structures and Algorithms · Chapter 15: Balanced Search TreesSection 15.2 · lesson 64 of 8711 min · free with a free account

← Binary Search Trees: Smaller Keys Left, Larger Keys RightNext lesson: Multiway Search Trees: 2-3 Trees, 2-4 Trees, and B-Trees →

Earn 3 college credits for Data Structures and AlgorithmsRecommended for credit by NCCRS · Computer Science 251 · self-paced · one payment, lifetime access
Enroll in Data Structures and Algorithms · $250 →Download the syllabus (PDF)

In this lesson

Keeping search trees short with balance factors and rotations.

  • Compute heights and balance factors and spot an unbalanced node
  • Apply single and double rotations for the LL, RR, LR and RL cases
  • Explain why insertion needs at most one repair while deletion may need many
  • Derive the AVL height bound from the fewest nodes at each height

Free study notes

Get this lesson's notes by email

The key points and 4 practice questions with answers, in your inbox. One email, free.

One email. Unsubscribe in one click.

Transcript

Everything said in the video, section by section (1,616 words). Read along, or search it.

Opening Question

Correcting the Lean After Every Step

A tightrope walker doesn't wait until falling to correct a lean. After every step, she senses the tilt, and adjusts at once, so no lean ever grows large. A plain search tree has no such reflex. Keys that arrive in order, like ID numbers or timestamps, stretch it into a chain as tall as it has keys. So can a tree check its own lean after every insert and every delete, and fix it on the spot, cheaply?

Definition

Height and Balance Factor

Two measurements do the job. The height of a node is the number of edges, on the longest path down to a leaf. So a leaf has height zero, and an empty subtree counts as minus one. The balance factor of a node is the height of its left subtree, minus the height of its right subtree. Positive means it leans left. Negative means it leans right. The AVL rule says every node has a balance factor of minus one, zero, or plus one. The two sides of any node differ in height by at most one. In this example, the root's two sides are equally tall. 60 has an empty left side and a leaf on its right: minus one minus zero, so minus one. Every node passes.

Implementation

Storing Heights in Each Node

A three-key chain breaks the rule. 10 has an empty left side, minus one, and a right side of height one. Its balance factor is minus two. One insert or delete changes a subtree's height by at most one, so a factor can reach plus or minus two, but never more. Only that case needs a repair. To make the factor cheap, each node stores its own height. In Java, a record bundles a key, two children, and a height. And a helper called make builds every node, computing its height as one more than the taller child. So the stored height is always right.

Rotations

Lifting a Child in Constant Time

A rotation is the repair. It changes the shape of a small part of the tree, without disturbing the order of the keys. Here, y leans left. A, B, and C stand for whole subtrees. In a right rotation, its left child, x, is lifted to the top, and y sinks to become x's right child. The subtree B, which hung between them, is handed over to y. Read the keys left to right, before and after: A, x, B, y, C. The order is untouched, so it's still a search tree. Only three links change, so a rotation takes constant time. And a left rotation is its mirror image.

Four Cases

LL, RR, LR and RL Repairs

Suppose a node z ends up with a factor of plus or minus two. Two questions pick the repair. Which side of z is too tall, and which side of that child is too tall? Take 10, 20, and 30, arriving in four orders. 30, 20, 10 leans left, then left again: case L L. One right rotation at 30 fixes it. 10, 20, 30 is the mirror, case R R: one left rotation at 10. 30, 10, 20 is a zig-zag: left, then right. Case L R takes a double rotation. Rotate left at 10 to straighten it, then right at 30. And 10, 30, 20 is case R L: rotate right at 30, then left at 10. All four repairs end the same way, with 20 on top, and the keys still in order.

Key Insight

Why Zig-Zags Need Two Rotations

Why can't a zig-zag take a single rotation? In case L R, the tall subtree sits on the inside, between the node and its child. A right rotation lifts the child, but it simply passes that tall inside subtree across to the other side. The new top is out of balance, the other way. The first rotation of a double rotation straightens the zig-zag into a straight line. Then the second is the ordinary single repair.

Quick Check

Inserting Twenty-Five

Quick check. This AVL tree holds 40, 20, 50, 10, and 30. Insert 25, and repair the tree. Which key ends up where 40 is now? Pause, and decide. 30. 25 goes left of 30. Now 40's left side is two levels taller than its right: plus two. Its left child, 20, leans right: minus one. That's a zig-zag, case L R, so it takes a double rotation: left at 20, then right at 40. 30 ends up on top, with 20 and 40 below it. A single right rotation would have lifted 20 instead, and left the tree leaning the other way.

Insertion

Rebalancing on the Way Back Up

Insertion goes down exactly as in a plain search tree, and attaches the new key as a leaf. Then, as the recursion returns, every node on the path back to the root recomputes its height and checks its factor. Only those nodes can have changed. Insert 1 through 7 in increasing order, the worst case for a plain tree. Inserting 3 tips node 1 to minus two, case R R, and a left rotation puts 2 on top. Inserting 5 repairs at 3, then 6 repairs at the root, 2, and 7 repairs at 5. All four are case R R. The result is perfectly balanced, height two, where a plain tree would be a chain of height six.

Key Fact

One Repair per Insertion

Here's a useful fact. An insertion needs at most one repair. The new key made the taller side one level taller. The repair brings that subtree back to exactly the height it had before the insert. So every ancestor above sees no change in height, and none of them can tip. In a test of 100,000 random insertions, no insertion ever needed more than one repair.

Deletion

Repairs Can Climb to the Root

Deletion starts like a plain delete. Then the same check runs at every node on the path back up. Insert 20, 10, 30, and 5, then delete 30. Removing it shortens the root's right side, and the left side is now two levels taller. The root's factor is plus two, and 10 leans left: case L L. One right rotation gives 10 on top, with 5 and 20 below. But here's the difference. A repair after a deletion can leave the subtree one level shorter than before. So the parent may tip, and then its parent, all the way up. So a deletion may need a repair at every level: still order log n. In the 100,000-key test, the worst deletion needed five repairs and nine rotations.

Measured Results

Rotations per Operation

In practice, rebalancing is cheap. Over those 100,000 random keys, there were about 0.7 rotations per insertion, and fewer than half a rotation per deletion. And after all the insertions, the tree's height was only nineteen.

Height Bound

Fewest Nodes for Each Height

Is the tree guaranteed to stay short? Turn the question around. What's the fewest nodes an AVL tree of height h can have? The thinnest tree has a root, one subtree of height h minus one, and the other as short as the rule allows: h minus two. So N of h equals N of h minus one, plus N of h minus two, plus one. That's the Fibonacci pattern, plus one. 1, 2, 4, 7, 12, 20, 33, and by height twelve, 609 nodes. The count grows by a factor of about 1.6 per level. So a tree with n keys can't be very tall. So the height is, at most, about 1.44 times log base two of the quantity n plus two. An AVL tree is never more than about 44 percent taller than a perfectly balanced one. Its height is order log n.

Measured Results

AVL Versus Plain Tree Heights

Measurements agree. With 100,000 keys inserted in sorted order, a plain search tree had height 99,999. The AVL tree's height was sixteen. In random order, the plain tree was fairly short too, at forty. But that's luck, not a promise. The AVL tree, at nineteen, stays below its bound of about twenty-four, whatever the order.

Quick Check

Height Limit for a Million Records

Quick check. A system stores a million records, under keys that may arrive in any order. In an AVL tree, what's the most its height could be? Pause, and decide. At most about twenty-nine. 1.44 times log base two of a million and two is twenty-eight point seven. Twenty is the height of a perfectly balanced tree, and the AVL rule allows a little more. A million would mean a chain, which the rule never allows. So every search takes a few dozen steps at most.

Summary

Guaranteed Order Log n

So search, insert, and delete all cost order log n in the worst case, whatever order the keys arrive in. A plain tree can be order n. The price is one stored height per node, at most one repair per insertion, and up to one repair per level for a deletion.

Common Mistakes

Four Rebalancing Errors

Four mistakes to avoid. Mixing height conventions: counting edges in one place, and nodes in another, breaks every balance factor. Forgetting to update heights after a rotation. Both moved nodes need new heights, the lower one first. Using a single rotation on a zig-zag. Check the child's factor first. And rotating at the wrong node. The repair belongs at the lowest node whose factor is plus or minus two.

Key Takeaways

Factors, Rotations and Height

To sum up. The balance factor is the left height minus the right height, and an AVL tree keeps every factor at minus one, zero, or plus one. A rotation changes three links in constant time, and keeps the keys in order. Straight cases take a single rotation. Zig-zags take a double rotation. An insertion needs at most one repair. A deletion may need one at every level. And the height stays below about 1.44 log n, so every operation is order log n.

Think About It

Trading a Little Height for Fewer Repairs

Here's something to think about. Suppose a rule let a tree lean a little more than the AVL rule allows. The tree would be a bit taller, but it would need fewer repairs. When would you happily accept that trade?

About Data Structures and Algorithms at UPI Study

Data Structures and Algorithms (Computer Science 251) is a self-paced online course of 87 video lessons in 17 chapters, from Java and object-oriented design to arrays, linked lists, recursion, stacks and queues, trees, heaps, hash tables, sorting and graphs. It carries a NCCRS credit recommendation for 3 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →

Compare: Discrete Math vs Data Structures and Algorithms · Intro to Java vs Data Structures and Algorithms

Why take it here

Why students take Data Structures and Algorithms with UPI Study

How programs store and search dataData Structures and Algorithms teaches how to organize data and measure how fast code runs: arrays, linked lists, stacks, queues, trees, heaps, hash tables, sorting and graphs, all written in Java. It is a core course in computer science and software degrees.
Credit at a fraction of the priceThe same 3 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Data Structures and Algorithms carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About AVL Trees: Rebalancing After Every Insertion and Deletion

What is a balance factor in an AVL tree?
A node's balance factor is the height of its left subtree minus the height of its right subtree, with an empty subtree counted as height -1. An AVL tree keeps every factor at -1, 0 or 1. Inserting 10, 20 and 30 into a plain tree makes a right-leaning chain, and the root 10 gets a factor of -1 minus 1, which is -2, so a rotation is needed there.
When does an AVL tree need a double rotation?
A double rotation fixes the zig-zag cases, LR and RL, where the new key went into the inner subtree of the taller child. Inserting 30, 10 and then 20 gives an LR case: 20 is the right child of 30's left child 10. A single right rotation at 30 would only lean the tree the other way, so a left rotation at 10 comes first, then a right rotation at 30, leaving 20 on top with 10 and 30 below.
How tall can an AVL tree get?
An AVL tree with n keys has height at most about 1.44 times log2(n + 2), so it is never more than about 44 percent taller than a perfectly balanced tree. The bound comes from the fewest nodes for each height, N(h) = N(h - 1) + N(h - 2) + 1, a Fibonacci-like pattern. For a million keys, the worst-case height is at most about 28 to 29, against 19 for a perfectly balanced tree.
How many rotations does an AVL tree do per insertion and deletion?
An insertion needs at most one repair, a single or double rotation, because the repair restores the subtree's old height and the ancestors above see no change. A deletion can shorten a subtree, so repairs may continue at every level up to the root, which is O(log n) rotations. In measurements with 100,000 random keys, insertions averaged about 0.7 rotations each and deletions fewer than half a rotation.

About the Data Structures and Algorithms course

How many college credits is Data Structures and Algorithms?
Data Structures and Algorithms (Computer Science 251) carries a NCCRS credit recommendation for 3 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Data Structures and Algorithms cost and what is included?
$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Data Structures and Algorithms take?
It is self-paced with no deadlines. The 87 lessons total about 15 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 3 credits in Data Structures and Algorithms.

87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Data Structures and Algorithms →Download the syllabusEvery course with PRO →
Data Structures and Algorithms
3 credits · NCCRSEnroll →