Loading...

Splay Trees: Introduction

In this module we continue studying binary search trees. We study a few non-trivial applications. We then study the new kind of balanced search trees - Splay Trees. They adapt to the queries dynamically and are optimal in many ways.

estructuras de datos

Universidad de California en San Diego

Curso 2 de 6 en Estructuras de datos y algoritmos Programa Especializado

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!

Destrezas que aprenderás

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

Impartido por:

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

Transcripción

Hello everybody.

Welcome back.

Today we are going to talk about something a little different.

Up until this point, we've talked about AVL trees,

we've talked about how to keep them bound, and how to use them, to implement all of

our binary search tree operations, and all of log on time pre-operations.

But it turns out that there are a wide number of different binary search tree

structures that give you different ways to ensure that your trees are balanced,

there are trepes, there are red block trees, and today we're going to talk about

splay trees as sort of another example of the types of things that you can do.

And to motivate this suppose that, well, if you're searching for random elements,

one after the other, you can actually show that no matter what splay your use or

data, searcher you use it will always take at least log n time per operation.

That's actually the best you can do.

However, if some items are searched for more frequently than others,

you might be able to do better.

If you take the frequently queried items and

put them close to the root, those items will be faster to search for.

And some of the other items might be a little bit slower, but

you should still be okay.

To compare for example, we've got the unbalanced tree and

the balanced one with the same entires.

But you'll note that 1, 5 and 7 are much higher up in the unbalanced tree.

Now if we search for random things, if we search for 11, 11 is much higher up in

the balanced tree than the unbalanced one, so the unbalanced one is slower there.

But when we search for 1,

it takes a lot less time in the unbalanced case, we search for

one again, we search for seven, it's again a lot cheaper in the unbalanced case.

And if we do some sequence of searches well,

it might turn out that's is actually cheaper to use the unbalanced tree than

the balanced one if these elements that tend to be higher

up in the unbalanced tree are searched for more frequently than other elements.

So the idea here is that we'd like to have a search tree where we can put the commons

searched common nodes near the root of the tree so that they are cheaper to look up.

However, very often it will be the case that we won't know ahead of time

which those commonly searched for nodes will be.

And so if we, or

in this situation we'll need an adaptive way to bring them close to the root.

And one natural way to do it is every time you find a node in your tree

you do something to rearrange the tree and bring that node up to the root.

And that way at least heuristically, if there are elements that you search for

frequently, then since you keep bringing them up to the root,

they'll usually stay somewhat close to the root.

And they'll be very cheap to access.

So if we want to phrase this in a nice simple way, one thing that you could

do is if you have your tree and you've got this node that you searched for,

you could just bring it to the root by just rotating to the top.

You rotate it up and again and again and again, and

again until it ends up being the root.

Unfortunately, this simple idea is actually not very good.

As you'll note, we started with an unbalanced tree,

but after we did this operation, the tree is still unbalanced.

And in fact, if you keep doing this you'll get a bad sequence of inputs.

You can note that there's this loop here, these five rearrangements of the tree.

Where if you keep doing the appropriate search and then you rotate the searched

for a note all the way to the top, they just go in this loop.

And when this happens, if you count the total time it takes to perform

the sequence of operations, it takes O of n squared time to perform n operations.

And so the average time per operation is linear rather than logarithmic

which is far to slow.

So this rotate things up to the top doesn't actually work very well,

we need something better.

And for this we're going to make just a slight modification.

The rotate to top algorithm basically says you look at the node and

its parent and you rearrange them and then you, again, look at the node and

its parent and rearrange them, and keep going until you get to the root.

The modification, instead of just looking at the node and

its parent, you're going to look at the node and its parent and its grandparent.

And there are a few cases here.

Firstly, there's the case where the node and its parent and

grandparent are on the same side of it.

This is called the zig-zig case.

Then what we're going to do is we're going to elevate the node up so

that it's now the parent of what was its old parent, and

that's on top of what was the old grandparent.

On the other hand, it could be that the parent and

grandparent are on opposite sides of the nodes, what's known as the zig-zag case.

Then you rearrange the tree as follows, so

that the node is now the new parent parent of its old parent and grandparent.

And finally there's one more case where the node's parent is actually the root

node, so it doesn't have a grandparent.

And then you actually just rotate the node up And so

if we combine these operations, together we get what's called the splay operation.

If you want to splay a node N, and

this is a way of bringing the node N to the root of the tree,

you determine which case you are in, the Zig-Zig, the Zig-Zag, or the Zig case.

You apply the appropriate local operation to rearrange the tree.

And then if the parent of the node is not null IE,

if the node is not the root of the tree yet, you splay n again.

And you just keep splaying until it gets to become the root.

Okay so to make sure that we're on the same page with this.

If the take the tree up top and we splay the highlighted node number 4,

which of these three trees, A, B, or C, do we end up with afterwards?

Well, the answer, here, is A.

So, the point is, we start in this configuration, we note that we're,

originally, in the zig, zig case, two, three, and then, four.

So, we elevate four, such that three, and then, two come down from it, as children.

And then we're in the zig zag case.

One and five are on opposite sides of four so we elevate four, one and five

are it's new children and three and two now hang off of one and that is exactly

what we were supposed to end up with and so that is the answer to this question.

Okay, so that's what the splay operation is.

Next time we're going to talk about how to use the splay operation

to rebalance your circuitry, and

how to use it to perform all the basic binary circuitry operations efficiently.

So I'll see you then.

Acerca de Coursera

Cursos, programas especializados y títulos en línea impartidos por los principales instructores de las mejores universidades e instituciones educativas del mundo.

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 brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.

© 2019 Coursera Inc. Todos los derechos reservados.

Descargar en la App Store

Consíguelo en Google Play