Loading...

AVL Trees

Course video 54 of 60

In this module we study binary search trees, which are a data structure for doing searches on dynamically changing ordered sets. You will learn about many of the difficulties in accomplishing this task and the ways in which we can overcome them. In order to do this you will need to learn the basic structure of binary search trees, how to insert and delete without destroying this structure, and how to ensure that the tree remains balanced.

Data Structures

University of California San Diego

Course 2 of 6 in the Data Structures and Algorithms Specialization

A good algorithm usually comes together with a set of good data structures that allow the algorithm to manipulate the data efficiently. In this course, we consider the common data structures that are used in various computational problems. You will learn how these data structures are implemented in different programming languages and will practice implementing them in our programming assignments. This will help you to understand what is going on inside a particular built-in implementation of a data structure and what to expect from it. You will also learn typical use cases for these data structures. A few examples of questions that we are going to cover in this class are the following: 1. What is a good strategy of resizing a dynamic array? 2. How priority queues are implemented in C++, Java, and Python? 3. How to implement a hash table so that the amortized running time of all operations is O(1) on average? 4. What are good strategies to keep a binary tree balanced? You will also learn how services like Dropbox manage to upload some large files instantly and to save a lot of storage space!

Skills You'll Learn

Binary Search Tree, Priority Queue, Hash Table, Stack (Abstract Data Type), List

Taught By

Alexander S. Kulikov
Visiting Professor
Michael Levin
Lecturer
Daniel M Kane
Assistant Professor
Neil Rhodes
Adjunct Faculty

Transcript

Hello everybody, welcome back.

We're still talking about binary search trees but

today we're going to talk about AVL trees.

And AVL trees are just sort of a specific way of maintaining balance in your

binary search tree.

And we're just going to talk about sort of the basic idea.

Next lecture we're going to talk about how to actually implement them.

But okay, what's the idea?

We learned last lecture that in order for

our search operations to be fast, we need to maintain balance of the tree.

But before we can do that we first need a way to measure the balance of the tree so

that we can know if we're unbalanced and know how to fix it.

And a natural way to do this is by what's called the height of a node.

So if you have a node in the tree,

its height is the maximum length of a path from that node to a leaf of your tree.

Fair enough.

So for

example if we have the following tree, what's the height of the highlighted node?

Well, this node has height six, the following path of length six leads down

from this node and it turns out to be nothing longer.

So, we can define height recursively in a very easy way.

If you have leaf its height is one because you're just there and

you can't go any further.

Otherwise, well the longest path downwards you can have, it's either through

the longest path on your left side or the longest path on your right side.

So you want to take the maximum of the height of your left child and

the height of your right child, and

then you need to add one to that because n sort of gets added to this path.

Okay, that's fine.

Now, in order to actually make use of this height we actually are going to want to

add a new field to our nodes.

So, the nodes that made up our tree previously stored a key and

are pointed to the parents on the left child and the right child, and

now they also need to store another piece of data, the height of node.

And note that we are actually going to have to do some work, and

we'll talk a little bit about how to do this later,

to insure that this height field is actually kept up to date.

We can't just store it as a number and leave it there forever.

If we rearrange the tree, we might need to change its heights.

In any case, back to balance.

Height is a very rough measure of the size of a sub-tree.

For things to be balanced, we want the size of the two sub-trees of the left and

right children of any given node to be roughly the same.

And so there's an obvious way to do this.

We'd like to force the heights of these children to be roughly the same.

So the AVL property is the following.

For all nodes N in our tray, we would like it to be the case

that the difference between the height of the left child and

the height of the right child is at most one.

And we claim that if you can maintain this property for all nodes in your tree,

this actually ensures that your tree is reasonably well balanced.

Okay and so, really what we'd like to know is that if you have the AVL property

on all nodes, then the total height of the tree should be logarithmic.

It should be O(log(n)).

So basically what we want to say is that you have an AVL tree and

it doesn't have too many nodes.

Then the height is not too big.

But it turns out that the easier way to get at this is to turn this on its head.

We want to show instead that if you have an AVL tree and

the height isn't too big, then you can't have too many nodes.

And this we can do.

So we're going to prove the following theorem.

Suppose that you have an AVL tree, a tree satisfying the AVL property, and

N is a node of this tree with height h.

THen the claim is that the sub-tree of N has to have size at

least the Fibonacci Number F's og h.

And so just to review, we talked about Fibonacci Numbers way back

in the introductory unit for this, but for the previous course in this sequence.

But this is just a sequence of numbers.

The zeroth one is zero, the first is one, and

from there after each Fibonacci number is the sum of the previous two.

Now, these are a nice predictable sequence, they grow pretty fast,

the end Fibonacci number's at least two to the n over two for all n at least 6.

Okay so let's look at the proof,

we're going to do this by induction on the height of our node.

If the node we're looking at has height one, it's a leaf.

And it's sub-tree has one node which is the first Fibonacci number, great.

Next we need an inductive hypothesis if you've got some node of height h.

By sort of definition of the height,

at least one of your two children need to have height h minus one.

Then, by the AVL property,

your other child needs to have height at least h minus two.

So by the inductive hypothesis,

the total number of nodes in this tree is at least the sum of the h -1 Fibonacci

number plus the h- 2 Fibonacci number, which equals the h Fibonacci number.

And so that completes the proof.

So what does this mean?

It means that if a node in our tree has height h,

the sub-tree of that node has height at least two to the h over two.

But if our tree only has n nodes, two to the h over two can't be more than n.

So the height can't be more than two log base two of n.

Which is o of log n.

And so the conclusion is if we can maintain the AVL property,

you can perform all of your find and operations in such in O(log(n)) time.

And so next lecture we're going to talk about how to maintain this property but

this is the key idea.

If we can maintain this property, we have a balanced tree and things should be fast.

So I'll see you next time as we discuss how to ensure that this happens

About Coursera

Courses, Specializations, and Online Degrees taught by top instructors from the world's best universities and educational institutions.

Join a community of 40 million learners from around the world

Earn a skill-based course certificate to apply your knowledge

Gain confidence in your skills and further your career

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2019 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play