Transcript


00:14
okay all right any questions on past
00:18
material that you want to bring up at
00:21
this point no all right so so far we've
00:29
seen a number of tree structures for
00:32
dictionaries and please the balanced
00:38
versions of these that we saw things
00:39
like AVL and red black and B trees all
00:43
of these provided logarithmic
00:45
performance for operations such as
00:48
search and and seed and insert
00:50
logarithmic performance as far as
00:52
worst-case time for operation is
00:55
concerned you know we're going to finish
00:58
our discussion on dictionaries well at
01:01
least on search tree type dictionaries
01:03
by taking a look at a version of a
01:07
binary search tree where the complexity
01:12
is logarithmic from the amortized point
01:13
of view but from the worst case point of
01:16
view the complexity of several of the
01:19
operations would be order n you know
01:22
experiments using the structure suggest
01:26
that if you measure time over sequences
01:30
of operations rather than per operation
01:32
then this structure actually performs
01:35
well performs better than things like
01:38
AVL trees and red black trees of course
01:42
since it's a binary structure it still
01:45
has a large number of cache misses so if
01:47
you're trying to compare it to a B tree
01:49
of low order maybe 16 that you might be
01:52
able to implement for internal use
01:55
because of the cache misses it's really
01:57
isn't expected to perform as well okay
02:01
all right so look at splay trees as I
02:04
said they these are binary search trees
02:08
the amortized complexity of search
02:12
insert delete and split is logarithmic
02:16
whereas the actual complexity for these
02:18
operations is order of N
02:22
for the joint operation the actual and
02:27
amortized complexity is one you can use
02:34
this structure of course you can use any
02:35
search structure for a priority queue so
02:39
if you need to find the max for example
02:42
you just keep making right child moves
02:43
if you want to find the menu keep making
02:45
left child moves okay so you can use it
02:48
as a single ended or double ended
02:50
product queue and have logarithmic
02:54
performance as far as amortized
02:56
complexity is concerned and in terms of
02:58
measured complexity many of the
03:01
experiments that have been done indicate
03:03
that this actually works better than
03:04
things like heaps and deeps and many of
03:08
the other double ended structures again
03:10
this is over sequences rather than on a
03:12
per operation basis all right there are
03:18
two varieties of splay trees one of
03:23
these is a bottom-up and the other one
03:25
is a top-down and today what we'll do is
03:29
we'll take a look at both varieties
03:30
we'll see how each of these work and
03:33
just the fact that we can cover both in
03:36
one lecture indicates that this is not a
03:38
very complex structure or strategy okay
03:41
and then in the next lecture we will do
03:44
the amortized complexity analysis for
03:46
one of these two and the one that we
03:48
will analyze is the bottom-up variety
03:52
okay
03:56
all right so let's start first by
03:58
looking at bottom-up splay trees in a
04:03
bottom-up splay tree most of the
04:06
operations are done exactly the way you
04:08
would in a binary search tree okay so
04:11
that's an unbalanced binary search tree
04:13
see you perform search insert delete
04:14
join exactly as you were there but once
04:20
you're done with the operation as you
04:22
would if you didn't care about balance
04:24
then you perform an extra step or
04:27
operation called display operation okay
04:31
so when you perform any of these
04:33
operations you
04:35
the process of performing these you
04:37
identify a particular node that will
04:40
refer to as display node once you
04:44
identify the splay node then you can
04:46
invoke a function called splay which
04:49
will perform some extra work beginning
04:51
at that splay node what display does is
04:59
it promotes the splay node so that it
05:04
becomes the root of the search tree so
05:07
like all of the other structures we've
05:10
seen that have good amortized
05:13
performance but not good from the poor
05:16
operation point of view those structures
05:19
as well as this one requires you to do
05:22
some extra work with the expectation
05:25
that there will be more operations
05:26
performed in the data structure later
05:28
and that the complexity for those
05:31
operations will go down okay so you do
05:33
more extra work now with the hope that
05:35
there will be additional things done in
05:37
the structure and now those additional
05:39
things become cheaper so it's the same
05:41
thing here we do everything that had to
05:44
be done before to perform the operation
05:46
but instead of walking away having done
05:49
the minimal that was needed we do
05:51
something extra and that something extra
05:53
is display a splay starts a display node
05:57
identified during the operation and
05:59
moves that splay node up the tree so
06:02
that it becomes a becomes the root of
06:05
the tree so that's extra work as far as
06:09
that individual operation is concerned
06:10
but that extra work pays off because it
06:13
ensures that no succeeding operation can
06:16
take a lot of time all right
06:23
the joint operation has no splay
06:28
associated with it or another way to
06:31
look at it once you take a look at how
06:33
splay works is that it's a null splay
06:40
the split operation is done somewhat
06:43
different from how you might in a
06:45
unbalanced tree
06:48
in a split operation display instead of
06:52
being done at the end of the operation
06:54
is done in some sense in the middle of
06:57
the operation so as we will see for as
07:04
far as coding a bottom a split tree is
07:07
concerned or all you really need to do
07:11
is take the codes you might already have
07:13
for an unbalanced binary search tree and
07:16
for the majority of the functions at the
07:22
end of it you insert one line which says
07:24
call splay okay so you invoke this play
07:28
function and the only new code you need
07:32
to write is display function okay for
07:35
the split you'll have to put this
07:36
invocation as place somewhere in the
07:38
middle of the code so you really have to
07:43
write only one new function and insert
07:48
calls display in the others so so coding
07:52
becomes easy and as we'll see the code
07:55
for this play itself isn't terribly hard
07:57
you don't keep balance factors you don't
08:00
have colors on nodes or anything else
08:04
all right
08:05
so first we need to identify the splay
08:08
node okay suppose you do a search okay
08:12
so you ask to search for an element or a
08:16
pair with a given key okay
08:18
then there are two possibilities for the
08:22
search it's either successful or it's
08:24
unsuccessful so if you ask to search for
08:26
eight you terminate here if you ask to
08:30
search for 10 you terminate out there if
08:32
you ask you search for 30 you terminate
08:34
out here if you ask to search for 20 you
08:36
terminate there okay so when you have a
08:39
successful search display node is simply
08:41
the node where you terminate okay so if
08:47
I did a search six I would follow the
08:50
path here once I found six I'll say
08:53
splay at this node okay and then
08:58
following display I can return the
09:00
parrot
09:02
if you have an unsuccessful search so
09:06
for example you're searching for a seven
09:08
you fall off here okay or you're
09:11
searching for a 14 and you fall off
09:13
there so in an unsuccessful search
09:15
display node is the node from where you
09:18
fell off the tree okay so in the first
09:20
case you display from here in the second
09:23
case you display from that regardless of
09:26
whether it's a successful or
09:28
unsuccessful search the outcome of
09:30
display is that the splay node will
09:33
eventually end up as the root so if I
09:36
splay from 8 when you're done with this
09:37
play 8 will be the root of the tree
09:39
everybody else would have been
09:40
reorganized so that you have a binary
09:42
search tree right any questions about
09:47
what the splay node is for a search all
09:57
right if you do an insert again an
10:01
insert can have two outcomes in one case
10:04
you actually insert a new node in the
10:07
other case you maybe update the element
10:09
associated with a pair because you
10:11
already have a pair with that key okay
10:15
so if you already have a pair with that
10:17
key so maybe you were asked to insert a
10:20
pair with key six you come here any
10:22
changes associated pair well then you
10:24
make six display node so this is this
10:27
play node okay so whatever the search
10:30
terminates and you update the element
10:35
that is this play node on the other hand
10:39
if you insert a new node for example you
10:42
had to insert a pair with key 32 you'd
10:45
insert it down here then this newly
10:47
inserted node would be this play note in
10:51
general the remaining node in the tree
10:56
at the lowest level that you have is
10:59
this play node okay so the deepest node
11:02
that you see becomes display node
11:08
or any questions about what this play
11:10
note is for an insert if you do a delete
11:19
there are two outcomes one is the tree
11:24
doesn't have anybody with the Delete key
11:26
in it and the other outcome as it does
11:30
so we need to define this play note for
11:34
both cases so if you actually have that
11:40
key present in your tree so if you're
11:42
doing a delete ten okay or you're
11:46
deleting 15 or 20 or 30 okay and in that
11:51
case there is going to be one node that
11:54
is thrown away it may not be the node
11:56
that contains the element that's deleted
11:58
so for example when you delete 20 the
12:01
node that's going to be thrown away is
12:03
this one okay so again the deepest node
12:07
encountered during the operation as
12:09
display node okay so if you throw this
12:11
node away okay of course you this cannot
12:14
become display node because it's gone
12:16
okay so the the deepest remaining node
12:18
is the parent of this guy this guy would
12:20
be display node okay similarly if you
12:24
did a delete 40 okay
12:29
well then you will change this point due
12:31
to this one and then you would start
12:34
your splay at that node
12:46
now if the item you are trying to delete
12:50
doesn't exist okay well then you fall
12:54
off the tree somewhere and use the
12:56
parent or use the node from where you
12:59
fell off as display node
13:09
okay right so in all cases once you do
13:15
this play this play node will eventually
13:18
end up by the end of this play operation
13:20
as the new root of the tree when you're
13:26
doing a split the way we're going to do
13:37
a split is we'll kind of simulate an
13:42
insert okay so I'll first do an insert
13:46
with the given key but when I do this
13:49
insert if I find a pair with the same
13:52
key
13:52
I will not update the associated element
13:55
they don't really change the D and the
13:58
items in the tree okay
14:00
so essentially do I do an insert with
14:03
the exception of not updating the
14:06
element if you already have a pair with
14:08
that key okay and when you do the insert
14:13
we've defined display node for the
14:15
insert so we'll use that as display node
14:19
and we will do this play the result of
14:24
this play is that display node becomes
14:27
the root okay so you have a splay node
14:33
it becomes the root okay now this fellow
14:37
may contain well this fellow is going to
14:42
contain a pair whose key is K okay we
14:46
did an insert up here okay the insert
14:52
will either insert a new node with a
14:56
fake pair that you created with key K in
14:59
which case that new node will become the
15:02
root following the display or that
15:05
insert will try to update an element but
15:08
you won't allow the update of the
15:09
element to take place but still that
15:12
node will end up becoming the splay node
15:14
and then it'll be promoted to this level
15:17
okay so either way when you're done with
15:21
display the
15:22
will contain a pair whose key is K that
15:26
pair may be the original pair or it may
15:29
be a newly inserted pair okay all right
15:33
regardless everybody in s because this
15:37
is a binary search tree it's smaller
15:39
than K everybody in B is bigger than K
15:42
so this is the small tree for the split
15:45
so we cut it off that is the big tree
15:47
for the split the fellow in here if it
15:52
is an original pair then it has to be
15:54
returned as the middle pair if it is the
15:57
fake pair that you put in well then you
16:00
didn't have anybody with key K to begin
16:02
with you just throw that fellow out
16:18
all right questions are on how a split
16:21
is done so you first do an insert using
16:26
the old insert down with them for
16:28
unbalanced trees with a change made to
16:33
it so that if you already have a pair
16:35
with that insert key you don't update
16:37
the Associated element okay then you do
16:44
a splay using this play node as defined
16:46
for an insert so that's going to be a
16:49
node whose key is K following that you
16:52
end up with this configuration you split
16:55
off the s and B and then whether or not
16:58
you return a middle pair depends on
17:00
whether this is that fake insert you did
17:03
up here or this is an original all right
17:15
so that's how the split works all right
17:23
so we've defined the splay node for all
17:26
of the operations we now need to see how
17:29
is this play actually done the objective
17:33
of this play is to restructure the
17:37
binary search tree so that the splay
17:39
node is the root all right so let Q be
17:47
the current splay node we're going to
17:51
move Q up the tree from wherever it is
17:54
right now we're going to move it up as a
17:57
result of many small steps in each step
18:05
okay
18:07
the splay node is going to be moved up
18:08
the tree by either 0 1 or 2 levels 0 of
18:13
course is done only when you are already
18:15
at the root ok so if Q is already the
18:19
root doesn't know there are no levels to
18:22
move it otherwise you either move it up
18:25
by one level or you move it up by two
18:27
levels and you keep doing this until
18:29
your
18:29
done now certainly you could accomplish
18:34
this play by just doing a whole bunch of
18:36
one level moves if you just do a whole
18:41
bunch of one level moves the amortized
18:43
complexity is not logarithmic so the
18:47
reason for having both one level and two
18:49
level moves is to get the amortized
18:51
complexity if you have only two level
18:56
moves well then you can't get things up
18:59
to the root because if you have a node
19:03
at level two there's no way to move into
19:05
the root using a two level move you
19:07
can't have a one level move in the end
19:10
all right so we need one level and two
19:12
level moves to accomplish the task with
19:16
the logarithmic amortize complexity
19:22
we'll use two level moves so long as two
19:25
level moves are possible and then if
19:28
after a whole bunch of two level moves
19:30
your splay node ends up at level two
19:32
we'll use a one level move to complete
19:36
display now let's look at this play step
19:44
so if you already had the root or if
19:51
you're not even pointing at a node then
19:53
there's no work to be done if you're at
19:58
level two you need to do a one level
20:00
move to possibilities for this case Q
20:07
could be the left child of the root or Q
20:10
could be the right child of the root
20:11
okay so let's look at the case when Q is
20:14
the left child of the root so this time
20:17
we'll just do a rotation looks like an
20:21
ll rotation okay so Q moves up here and
20:26
then you place everybody else so as to
20:29
satisfy the binary search tree
20:31
requirements
20:36
the other case Q out here is the same as
20:39
this you just rotate in the other
20:40
direction
20:51
alright if the splay node is not at
20:53
level two then you have to do a two
20:56
level move so for two level moves there
21:00
are four cases q could be the left child
21:04
of its parent which is the left child of
21:06
its parent says kinda like the ll case
21:08
then you could have an L R case an RR in
21:11
an RL so if in an LL type situation like
21:19
this we perform that transformation okay
21:24
so Q is going to be moved up two levels
21:27
so Q is going to occupy this part
21:29
previously occupied by its grandparent P
21:34
is bigger than Q GP is bigger than Q so
21:37
both have to show up in the right
21:39
subtree of Q okay
21:40
so you arrange things in that fashion
21:43
that gives you a binary search tree the
21:51
RR case is very similar this would be
21:55
the starting point for the RR case with
21:57
Q out here and this would be the
21:59
terminal point for the our our case you
22:01
just rotated back
22:09
all right then we have the LR and the RL
22:11
so this would be the LR case and here
22:16
we'll do a transformation that's the
22:18
same as the AVL LR rotation Q is to be
22:23
moved up two levels so it moves up two
22:25
levels and then you place everybody else
22:28
to satisfy the binary search tree
22:30
requirements all right so the two level
22:43
moves are done according to the pictures
22:45
we just saw and after you've done a two
22:49
level move it's possible that Q is now
22:55
at level one it's a route in which case
22:58
you're done or Q may be at level two in
23:02
which case you'll need to do a one level
23:04
move or if it's further than that you
23:07
have to do another two level move okay
23:10
so you do a whole bunch of two level
23:12
moves possibly terminated by a one level
23:16
move you finish this play
23:24
all right any questions about how it's
23:26
played works
23:39
now let's take a look at the actual
23:41
complexity of splay trees right suppose
23:47
you start with an empty splay tree and
23:49
we insert items in ascending order right
23:56
so you put in a 1 and then you put in a
23:59
2 it becomes the right child of the one
24:03
but then you do a splay so two becomes
24:07
the root yes you do a one level display
24:10
step and you end up with that okay
24:19
alright then you insert a three okay so
24:21
this is what we had before the insertion
24:23
insert at three it becomes a right child
24:26
of two and this is the splay node so we
24:28
do is play from here again I'd say one
24:31
level splay right then I insert a four
24:41
and it's going to show up down here and
24:47
that new node is display node so you do
24:50
one levels play the four becomes the
24:52
root alright so as you can see if you go
24:58
back to that picture
25:05
so after display the fort becomes the
25:07
root and the height of this tree becomes
25:09
four when he do a five it'll become the
25:11
right child of the four you do is plate
25:13
becomes the root and so on so if you do
25:15
a long sequence of inserts in this
25:17
fashion you're going to just end up with
25:19
a chain of nodes and the height will be
25:22
and if you insert n items okay all right
25:27
so the worst case height of a splay
25:30
trees n and that happens when you insert
25:32
items in ascending order
25:35
each insert took only one unit of time
25:40
okay but now if you want to do a search
25:43
suppose you want to do a search for the
25:44
item one that'll take you n units of
25:47
time follow a long sequence of left
25:51
child moves if you want to insert
25:55
something smaller than one you have to
25:57
follow a long sequence of left child
25:59
moves falling off as the left child of
26:01
one so since the height becomes n the
26:07
actual complexity now to perform a
26:10
search operation or an insert operation
26:13
or a delete operation becomes n also if
26:20
you want to split if you want to split
26:22
at one you have to do a search for the
26:24
item that will take you want any units
26:26
of time
26:30
so the actual complexity of performing
26:33
operations in a splay tree is n please
26:38
stir for these operations search insert
26:40
delete and split all right yet the
26:47
amortized complexity is logarithmic and
26:50
we'll prove that in the next lecture or
26:56
any questions about bottom-up split
26:58
trees
27:02
yeah
27:18
how does it help to make this play note
27:22
the route as far as further operations
27:24
are concerned it's hard to see it from
27:27
the you know it's hard to get an
27:29
intuition about it but what happens is
27:31
that after you do a lot of plays the
27:33
tree tends to get balanced okay and so
27:39
we will see that when we actually look
27:41
at the proof that things actually work
27:45
out and the complexity becomes
27:47
logarithmic rather than this worst case
27:56
okay other questions
28:04
yeah as an aside in in the early days of
28:08
computing people are actually doing
28:10
things like this though perhaps not with
28:13
the two-level move that people use the
28:23
observation that if an item is accessed
28:26
right now then there's a good likelihood
28:30
is going to be accessed in the near
28:31
future again and so they would take
28:34
frequently accessed items and move them
28:36
to a point in the dictionary where they
28:38
could be found easily and this is really
28:42
following up on that intuition but with
28:46
the addition of the two-level move to
28:48
get things there you can actually prove
28:50
that things are going to work well even
28:54
in the worst case rather than just most
28:56
of the time so it's kind of an offshoot
28:59
of things people were doing in practice
29:02
long before anybody talked about
29:04
amortize complexity all right let's take
29:11
a look at top-down splay trees
29:19
I'll describe top-down split trees only
29:22
in the context of a successful search
29:25
and then you can extend it from there
29:28
for any of the other operations okay so
29:32
in a top-down splay tree you avoid the
29:35
second path that is made in the
29:36
bottom-up splay tree okay so in the
29:38
bottom-up splay tree you first start
29:40
from the root you go downward finding
29:41
the node at which you want to do
29:43
something search or you want to add
29:45
something out there or you want to
29:46
remove and then you have this backward
29:49
pass where you're promoting the splay
29:51
node so that it becomes the root in a
29:55
top-down tree you start rearranging
29:58
things as you go down so that when you
30:01
eventually find the splay node it's easy
30:04
to make this play note the root you
30:05
don't have to go back up and the task
30:09
that you perform is really what was
30:11
being done in a split of an unbalanced
30:14
binary tree so on the way down you split
30:17
the tree into two parts so that one part
30:20
can become the left subtree of the splay
30:22
node and the other part can become the
30:24
right subtree of the splay node okay so
30:28
that's the overall objective okay so on
30:31
the way down we're going to split the
30:32
tree into a small node into a small tree
30:38
and a big tree and then once you've
30:40
found the splay node we'll make that the
30:42
root and make these the sub trees okay
30:45
with some minor modification
30:52
the creation of s and B is in some sense
30:55
similar to how we split in an unbalanced
30:58
binary tree but in some sense it's a
31:00
little bit different as well and the
31:06
difference is that as you're moving down
31:09
instead of moving down one level at a
31:11
time you try to move down two levels at
31:14
a time okay and then you classify the
31:18
kind of move you're making you're either
31:20
moving making an ll move or you're
31:22
making an RR move and when you do ll and
31:26
our our moves what you do it in terms of
31:30
creating s and B is different from what
31:33
would happen in a split but when you
31:37
make LR and RL moves the construction of
31:42
s and B is the same as in a split
31:47
alright so we're going to move down to
31:50
levels at a time so long as it's
31:52
possible to move down to levels at a
31:53
time until you reach the splay node as
31:59
you move down we're going to create the
32:01
trees s and V and we'll see details of
32:07
how it's done all right and as I said
32:12
when you finally reach the splay node
32:13
you then make this play note the roots
32:16
you take s make it its left subtree you
32:18
take B makers its right subtree there's
32:21
going to be a little extra stuff because
32:23
once you reach this plain-old the splay
32:25
node may itself have a left subtree and
32:26
a right subtree that still need to be
32:27
put into S and B okay so let's just
32:35
recall how a split works in an
32:37
unbalanced binary search tree okay so we
32:41
start with two header nodes for the
32:43
small and the big tree and let's suppose
32:46
we are searching for the pair that's
32:50
sitting in this node okay so you start
32:52
up here you compare with the key out
32:55
here you move here
32:56
that tells you that the fellow here is
32:59
smaller than the split key everybody
33:00
here is smaller so they get stuck into
33:02
the small tree
33:05
then you make a comparison here you move
33:07
in the left subtree that tells you that
33:08
the pair out here and everybody in this
33:11
subtree is bigger than the split key so
33:13
you put it into the big tree then you
33:16
come out here you move to the right so
33:18
the fellow here and down here are
33:20
smaller than the split key so you move
33:22
them into the small tree you compare out
33:26
here we move to the right so this fellow
33:28
and everybody here is smaller than the
33:32
split key so they go into the small tree
33:37
okay well then you come out here you
33:40
move to the left so the fellow here is
33:42
bigger than the split key everybody down
33:44
there is bigger so these guys go into
33:46
the big tree okay then you reach here
33:50
and this fellow goes into the small tree
33:53
and that fellow goes into the big tree
33:55
and then this is the middle item to
33:59
return okay all right so we saw this
34:04
slide a few weeks ago when you're
34:07
looking at red black trees and basically
34:10
that's how the split works for an
34:11
unbalanced tree of course not for a red
34:14
black tree alright so in the context of
34:18
a top-down splay tree we aren't going to
34:22
move one level at a time along this path
34:26
okay we're going to move two levels at a
34:28
time okay so we're going to go from A to
34:34
C of course in terms of programming you
34:38
can't get from A to C without going
34:39
through be okay but conceptually we're
34:42
going from A to C okay and then we're
34:45
going to go from C to E and then finally
34:47
there'll be a one level move from E to
34:49
ya right so the first move the yellow
34:55
move is an are L move the second one is
35:00
an RR move and then you have an L move
35:04
in the end okay well let's see what
35:10
happens when you make these kinds of
35:13
moves
35:16
all right so again I'll start with
35:18
header nodes first and B I want to
35:20
create a small tree and a big tree as I
35:21
go down okay
35:25
all right so first we go from A to C so
35:31
when you go from A to C the items in a
35:34
and little a are smaller than the split
35:38
key with the items in B and little B a
35:40
bigger than the split key so this stuff
35:42
has to go into s and that stuff has to
35:44
go into B okay and that's so there's no
35:48
opportunity here to really do anything
35:50
different from what you would do when
35:52
you're splitting an unbalanced binary
35:54
search tree okay so an RL move works
35:57
exactly like if you had taken one level
36:00
moves for the unbalanced case this stuff
36:04
goes into s and that other stuff goes
36:06
into the big tree all right the next one
36:12
is a two-level move from C to e at this
36:16
time the C and everybody in this subtree
36:19
as well as this D and everybody in its
36:23
subtree they all go into the small tree
36:27
okay so since both of them go into the
36:29
small tree you now have an opportunity
36:31
to play around a bit for example what
36:34
we're going to do is I'm going to take D
36:36
and make this fellow a child out there
36:38
and then I'll make C a child of D in the
36:44
old example first C became a child here
36:48
and then D got attached as a child of C
36:51
now I'm going to rotate it I'm going to
36:53
make D a child of a and then I'm going
36:56
to make C a right child of D so this is
37:00
where the difference comes about okay so
37:04
when you did the RL move it's the same
37:06
okay when you do the our our move okay
37:11
I did a rotation of the CD previously C
37:15
was a parent and D was a child of
37:17
inverted that
37:21
again you could have got by by doing
37:24
exactly what was done for the unbalanced
37:27
case in terms of accomplishing the split
37:29
but then you would not have amortized
37:32
complexity log n ok so this rotation is
37:35
critical to getting the amortized
37:37
complexity all right now you're at E
37:44
it's just an move to a left child so
37:47
you've got this fellow to take care of
37:48
there's no choice this has to go into
37:50
the big tree there's really no room for
37:52
rotation or anything out there ok so
37:56
we're just going to stick it in over
37:58
there as the subtree all right so the
38:04
last one is the L move and that just
38:06
moved out there
38:16
all right so once you reach the splay
38:18
node okay we've got these fellows to
38:21
worry about F and G F goes into the
38:24
small tree G goes into the big tree okay
38:29
and now I can take this splay node make
38:38
it the root I can take this fellow throw
38:41
away that header take this fellow make
38:43
it the left subtree of this guy and take
38:46
this fellow throw away the header and
38:49
make it the right subtree of that node
38:52
and so the splay node has become the
39:03
root of the overall tree
39:26
all right questions about a top-down
39:28
display what why did we rotate these two
39:41
right the only reason for rotating them
39:44
is to be able to prove an amortize
39:48
complexity okay so it's really a
39:50
function of the proof if you didn't do
39:53
the rotation then the amortized
39:55
complexity would not be logged with me
39:57
so it really has to do with looking at
40:01
the details of the proof and seeing what
40:02
part of the proof would fail if you did
40:04
not do the rotation part which or which
40:21
condition yeah right so the rotation is
40:25
done if you go back a few slides in this
40:29
thing right so I said you always make
40:40
two level moves okay so you go from A to
40:42
C from C to E and so on okay when you
40:45
make a two level move the two level move
40:48
can be characterized in this case as an
40:50
RL move or in this case as an RR move
40:54
okay so when you do an RL or an LR you
40:58
don't do any rotation in fact there's no
41:00
opportunity to do a rotation because
41:02
when you do an RL one of these guys in
41:06
this case this guy goes on the small
41:08
tree and that guy this guy goes in the
41:10
big tree okay so there's no opportunity
41:13
for a rotation when you're moving those
41:15
two fellows similarly when you do an LR
41:18
one fellow will go into the big tree one
41:21
fellow will go into the small tree and
41:23
there's no opportunity there to do a
41:24
rotation it's only when you do an RR or
41:27
an LL okay so in the RR okay
41:32
both of these nodes D C and D are going
41:37
to end up in the small tree
41:39
okay so now you have a choice in terms
41:41
of how you put these fellows into the
41:43
small tree you can put them exactly the
41:45
way they are here or you can rotate like
41:48
we did if you put them exactly the way
41:51
they are here and that's what would
41:53
happen when you do a split of an
41:54
unbalanced tree then the amortize
41:57
complexity is not logarithmic so when
42:01
you make an up when you make an RR move
42:03
you do a rotation similarly when you
42:06
make an ll move you do a rotation okay
42:22
okay now in terms of coding coding of
42:29
the top-down tree is more involved than
42:31
coding of the bottom-up because for the
42:33
bottom-up I simply write a new function
42:35
called splay and then call it from the
42:37
right place of the other functions here
42:41
display is is married with the
42:44
performance of the operation is
42:45
intricately woven into the process of
42:49
moving down okay so you really have to
42:53
go and be doing the coding inside of
42:59
each of those functions every time we
43:02
move down to levels you got to move
43:04
things around now even though it may be
43:11
harder to code people have done a lot of
43:14
experiments playing around with
43:15
bottom-up and top-down and generally the
43:19
top-down works faster by a constant
43:22
factor than the bottom-up scheme
43:32
okay there are any questions on splay
43:34
trees nope
43:41
okay that's it