Transcript


00:09
okay yeah all right time to start you
00:13
have any things you want to talk about
00:14
before I continue the discussion on AVL
00:17
trees okay all right so in the last
00:25
lecture we took a look at the definition
00:29
of AVL trees and we saw that basically
00:33
an AVL tree is a binary tree if you
00:38
define a balanced factor on every node
00:40
of the binary tree to be the height of
00:47
the left subtree of that node minus the
00:49
height of the right subtree of that node
00:51
okay then an AVL tree has the property
00:55
that the balance factor of every node is
00:58
either minus 1 0 or plus 1 so if you
01:03
have a node whose balanced fact there's
01:04
something different from one of those 3
01:06
numbers or from those 3 numbers then
01:09
it's not an AVL tree an AVL tree has the
01:14
property that its height lies somewhere
01:17
between a low that lowest for every
01:20
binary tree can't be below log n plus 1
01:23
and being the number of internal nodes
01:25
and the max height is 1.4 for log of n
01:29
plus 2 so it's got a nice height
01:32
property the height is logarithmic in
01:35
the number of nodes all right so what
01:42
we'd like to do today is use AVL trees
01:45
to represent dictionaries and be able to
01:50
perform the standard dictionary
01:51
operations of search insert and delete
01:54
in logarithmic time now in order to use
02:01
an AVL tree to represent a dictionary
02:04
will impose a constraint on the
02:07
placement of the dictionary pairs and
02:10
that constraint would require that the
02:12
AVL tree also
02:13
be a binary search tree so for
02:17
dictionary applications we use AVL trees
02:21
that are also binary search trees though
02:23
for other applications the AVL tree use
02:26
may not also be a binary search tree
02:27
could be some other placement of the
02:30
elements
02:33
alright so an example AVL tree and here
02:36
a BL tree is a binary search tree so
02:39
maybe if you wanted to be very definite
02:40
we'd have to say AVL search tree or
02:42
something but we'll just abbreviate it
02:45
to AVL tree so you can see that the
02:50
placement of the keys only the keys are
02:52
shown here satisfies the binary search
02:54
tree properties and the structure of the
02:57
tree itself satisfies the AVL tree
03:00
properties the balance factors which is
03:02
shown here and red those are all 0 1 or
03:05
minus 1 all right so from what we proved
03:09
last time the height of this tree is
03:11
guaranteed to be logarithmic in the
03:13
number of elements you can search an AVL
03:18
tree using exactly the same algorithm
03:21
that was used to search binary search
03:23
trees and that runs in time proportional
03:26
to the height of the structure and since
03:28
the height is logarithmic you
03:29
automatically gets search in logarithmic
03:31
time the more interesting operations are
03:34
the insert and the delete all right so
03:38
let's move on to take a look at how
03:40
inserts and deletes work let's start
03:46
first with the insert operation put as a
03:50
synonym for insert so we are going to
03:53
put a pair into this structure which has
03:55
the key 9 or we're going to insert the
03:58
key 9 into the structure you may think
04:03
of the insert as being done in two steps
04:07
in the first step you take the new pair
04:11
and put it into the tree without regard
04:13
to the fact that it says an AVL tree so
04:16
you just run your old algorithm for
04:18
insertion into a binary search tree and
04:20
place the item in and then in the second
04:23
step you adjust the balance factors and
04:25
if some balance factor become
04:27
out of the permissible range minus 1 to
04:30
1 then you invoke some remedial steps ok
04:34
so the first step is just put the item
04:37
in and then in the second step worry
04:39
about the balance factors and whether
04:41
you've gotten out of balance so to put
04:46
the 9 in we just to follow the standard
04:48
insertion algorithm for binary search
04:50
trees 9 is smaller than tens you end up
04:52
here it's bigger than 7 you end up here
04:54
it's bigger than 8 you fall off that
04:56
tells you 9 is not in the tree and so
04:59
that's the place to make the insertion
05:02
ok
05:03
so you get a new node you put in the 9
05:05
and you link it in alright so the first
05:11
step is exactly the way you would do it
05:13
if you didn't if you weren't dealing
05:14
with a balanced or with an AVL tree
05:17
simply a binary search tree in the
05:21
second step we worry about the balance
05:23
factors and whether some bounce factor
05:25
has become illegal okay alright so now
05:29
having made the insertion I'm going to
05:31
walk backwards up toward the root ok so
05:37
you can do this if you on the way down
05:40
you save the path on a stack and then on
05:43
the way back up you pop off the stack
05:45
retracing your path ok so that be one
05:49
way to do it alright so I'm going to
05:52
retrace my path setting bounce factors
05:54
so the balance factor of the newly
05:56
created node is always zero okay then
05:59
you come up here ok since we're coming
06:01
from the right side of this node and at
06:06
this point we know that the height of
06:09
the right subtree has gone up by one
06:10
previously there was no right subtree
06:12
you've created one source fight went
06:15
from zero to one so when you come up
06:17
here we know that the balance factor
06:19
here is going to decrease by one because
06:22
the balance factor is height of left -
06:24
hi - right and height of right went up
06:26
by one okay so this balance factor is
06:29
going to reduce by one it's going to
06:31
become minus one okay which is ok ok and
06:35
when the balance factor here becomes
06:37
minus one
06:39
that tells you that the height of this
06:41
tree here has gone up by one okay
06:45
previously the balance fact there was
06:46
zero which meant height of left and
06:47
right were the same when the bounce
06:49
factor changes to minus one
06:51
that means that the height of the right
06:52
sub groups become one more than the
06:54
height of the left so the height out
06:56
here has gone up by one okay so this
06:58
height went from previous height of one
07:00
now it's two so the balance factor here
07:03
has to change okay so come up here
07:06
because the height of this sub tree has
07:08
gone up by one so the balance factor
07:10
here is going to decrease because you're
07:12
coming from the right so it's going to
07:14
become zero now when a balance factor
07:19
here switches to zero what that tells me
07:22
is that the height of this sub tree
07:24
hasn't changed okay previously it was
07:26
one so this was one more than that this
07:28
went up by one the height difference is
07:30
now zero but the overall height hasn't
07:32
changed so the overall height here
07:35
hasn't changed there's no need to
07:36
retrace the rest of the path because in
07:39
the rest of the path you the new heights
07:42
are the same as the old types okay so my
07:49
first stage a step is make the insertion
07:52
without regard to the fact this is an
07:55
AVL tree and then in the second step or
07:58
second phase you retrace the path from
08:00
the new node adjusting balance factors
08:02
if you come from the right side the
08:05
balance factor is going to decrease by
08:08
one if you come from the left side the
08:10
balance factors are going to go up by
08:12
one if a balance factor becomes zero you
08:17
stop you don't have to go any further
08:19
because the height has not changed if a
08:22
balance factor becomes plus one or minus
08:24
one you have to go for the rub okay and
08:30
we're going to keep doing this until we
08:31
reach a place where the bounce factor
08:33
becomes plus two or minus two at that
08:37
time an alarm bell goes off something's
08:38
gone wrong you have a bad tree okay but
08:41
so long as you don't reach node whose
08:43
bounce factor becomes plus two or minus
08:45
two we can keep going back changing
08:48
zeros to plus one or minus one changing
08:52
a one or
08:53
- one - a zero when you change something
08:56
to a zero you stop okay so that's going
08:59
to be the basic strategy okay let's try
09:05
another example right so this time I
09:11
want to insert a twenty nine so in the
09:13
first step I follow a search path trying
09:16
to see if 29 is already in my dictionary
09:18
if it is I can update the Associated
09:21
element if it's not you'll fall off the
09:23
tree and that's where you insert the 29
09:25
okay so 29 is bigger than 10 smaller
09:28
than 40 smaller than 30 bigger than 20
09:32
bigger than 25 you fall off so that's
09:35
the place to insert the 29 so you get a
09:38
node you place the item in and Link it
09:41
in right so that's the first phase and
09:46
then the second phase is adjustment of
09:49
bounce factors and verification that you
09:52
still have an AVL tree all right so the
09:56
balance factor over here is set to 0 new
09:58
node is always 0 you move up we've come
10:02
from the right subtree so the balance
10:03
factor is going to decrease by one okay
10:08
when a balance factor becomes plus one
10:11
or minus one there's been a height
10:12
change okay so move up further to adjust
10:15
the balance factor further up again I've
10:18
I'm coming from the right subtree so the
10:19
balance factor will go down by one it
10:22
becomes minus two okay minus two is
10:25
illegal so we stop the backward
10:28
retracing at this point to handle the
10:31
fact that we've got somebody that's
10:33
illegal okay alright so in the backward
10:39
retrace when you reach a node whose
10:41
balance factor becomes illegal plus 2 or
10:43
minus two we classify the nature of the
10:48
we'll call that an imbalance the tree
10:50
has become unbalanced at this point okay
10:53
so we refer to this node here as the a
10:57
node okay that's the node whose balance
11:01
factor has become plus 2 or minus 2 and
11:04
then with respect to this
11:06
I'll classify the
11:08
balance depending upon whether the new
11:12
node was inserted in its left subtree in
11:14
its right subtree and further did he go
11:18
into the right subtree of the right
11:19
subtree in this case you move into the
11:21
right subtree of the a node and then
11:23
again into the right subtree so i'll
11:25
call that an r our type of imbalance
11:30
okay
11:31
all right so the a node is the node
11:33
whose balance factors become plus 2 or
11:35
minus 2 and then with respect to that i
11:39
decide whether the newly inserted node
11:42
the pink node here is that in the right
11:45
subtree of the a node or the left
11:47
subtree and further is it in the right
11:49
subtree or the left of this other node
11:52
okay so in this case you're in the right
11:55
subtree of the right subtree so we call
11:57
that an RR imbalance as we will see
12:04
using this classification scheme you can
12:06
end up with four types of imbalance so
12:09
you can have our rll rll and l r and for
12:13
each of these four types of imbalance
12:15
we'll have a strategy to get you out of
12:17
the imbalance okay so in the case of an
12:21
RR imbalance we will perform what's
12:24
called an RR rotation around the a node
12:27
and the rotation would have the result
12:31
of changing the structure out here so
12:34
that it looks like this in a moment
12:37
we'll see abstractions as how you do it
12:39
in general cases and following the
12:44
rotation what will happen is that the
12:47
balance factor of this position this is
12:51
where the old a node was will change
12:53
from its plus 2 or minus 2 to a zero
12:57
okay and the height of the sub tree
12:59
located at the location of the old a
13:02
node will be the same as it was before
13:05
the insertion and what that tells you is
13:08
there's no point going further up
13:11
because the height of these sub trees
13:13
before and after the insertion are the
13:15
same and so those balance factors are
13:17
not changed
13:20
okay alright so the second phase
13:23
strategy is retrace the path from the
13:26
new node toward the route change the
13:28
balance factors if you reach a node is
13:32
balanced factor becomes zero you stop if
13:36
it becomes plus one or minus one you
13:38
keep going back if it becomes plus 2 or
13:41
minus 2 you classify the imbalance you
13:43
do a rotation and that rotation will
13:46
ensure that the new balance factor there
13:48
is zero and the height of the sub tree
13:49
out there is unchanged from before the
13:52
insert and so you stop ok I will verify
13:57
all of this all right so strategy is
14:03
after you've done the insert retrace the
14:07
path adjusting the balance factors if
14:11
you reach somebody whose bounce factor
14:13
becomes 0 2 or minus 2 you stop if you
14:21
stop at a zero you're finished but if
14:24
you stop at a 2 or a minus 2 then you no
14:29
longer have an AVL tree and in this case
14:32
the tree is unbalanced you classify the
14:35
imbalance and perform a rotation and
14:38
then you terminate alright so we have
14:46
the concept of an a node okay so in the
14:49
retrace path the first time you come to
14:52
somebody whose balance factors plus 2 or
14:54
minus 2 that is the a node and you stop
14:56
that backward retrace
15:06
something you can observe is that the
15:11
balance factor of the nodes that lie
15:14
between the a node and the newly
15:16
inserted node okay
15:21
the balance factor of these nodes must
15:22
have been zero before the insertion okay
15:27
you see that look at the retrace path so
15:31
the retrace path says if the new balance
15:35
factor is plus one or minus one you
15:37
continue moving back okay so if you
15:41
reach a node and if it's new balance
15:44
factor is plus one or minus one then
15:46
you're going to move further back and
15:47
the only way you get to the a node is
15:50
you start at the new node and you keep
15:52
going back one node at a time so all of
15:55
these nodes must have a new balance
15:57
factor this plus one or minus one to
16:01
have a new balance factor this plus one
16:03
or minus one the old balance factor must
16:05
have been zero okay so so that's how you
16:14
get this one that before the insertion
16:16
all of the nodes between the a node and
16:19
the newly inserted node along that path
16:22
should have a balance factor of zero if
16:26
somebody out they had a balance factor
16:27
will say plus one then after the
16:30
insertion it's balanced factor would
16:32
either become zero or plus two if it
16:37
became zero you will stop the backward
16:38
trace there if it became plus 2 you
16:41
would still stop the backward trace
16:42
there and that intermediate node would
16:44
be a node okay so this has to be true
16:49
all nodes between the a node and the
16:52
newly inserted node on that path must
16:54
originally have had a balance factor of
16:56
zero and of course the a node itself
17:00
must originally have had a balance
17:02
factor of plus one if its new balance
17:04
factor is two or minus one if it's new
17:06
balance factor is minus two alright so
17:12
further the imbalance types this is done
17:14
with respect to the a node
17:17
okay as the first letter of the
17:23
imbalance comes from whether you go into
17:25
the left or right subtree of the a node
17:28
and the second letter comes from whether
17:32
you go into the left or right subtree of
17:34
that subtree so we have an RR so from a
17:41
you move into its right subtree and then
17:44
the second our says you make another
17:45
right move
17:46
ll from a you move into the left subtree
17:49
and from the node you reach you make
17:51
another left move similarly get our L
17:57
and L are
18:08
but again if you think about it you'll
18:11
notice that if you do have an imbalance
18:13
you can't have an a node and then have
18:17
just inserted it as the left child of
18:19
the a node or the right child of the a
18:21
node that can give you a balance factor
18:23
of plus or minus two at a so you must
18:26
have gone further down the tree so you
18:30
can't have an imbalance which is just of
18:32
type r which says I inserted it as the
18:34
left child of a or L I inserted it as
18:37
the left child of a okay you must have
18:40
gone further down because if you just
18:42
insert it as they left a right child of
18:44
a well then you've got a height one say
18:49
as the left child which is the new node
18:51
and the right child could have a height
18:56
of at most one before the insertion okay
18:59
so your new balance factor has to become
19:01
zero all right so you can reason that
19:06
these are the only four cases that can
19:08
arise when you actually have an a node
19:10
with a balance factor plus 2 or minus 2
19:14
let's look at some of the cases we look
19:17
at the L cases the ellow and the L are
19:20
the r r and r l are symmetric all right
19:24
so ll you have an a node okay so this is
19:28
the before insertion picture this node
19:31
is the one that's going to become the a
19:32
node after you do the insertion so you
19:38
must have gone into the left subtree of
19:40
this fellow and then from here you must
19:42
have gone further into the left subtree
19:43
so the new node has to be sitting
19:45
somewhere in here it could in fact be
19:49
the root okay this thing previously
19:51
could be empty and you may put it in
19:53
right here that's possible so B sub L
19:55
could be empty at this time okay but
19:59
we're guaranteed that this node exists
20:01
and we guaranteed that that node exists
20:03
we're not guaranteed there's any node
20:05
down here or down there
20:11
the balance factors on the path from A
20:14
to whatever you make the insertion must
20:16
be zero prior to the insert the balance
20:19
factor here has to be +1 that's the only
20:22
way it can become +2 after the insert if
20:25
you're doing it in the left subtree so
20:29
before the insertion you have to look
20:31
like this
20:34
and from these balance factors we
20:37
conclude that if the height of the left
20:40
subtree is H the height of the right
20:42
subtree must also be H prior to the
20:44
insert that's how you get a balance
20:45
factor of zero and the height out here
20:48
must also be H because this subtree here
20:51
now has a height H plus one and that's
20:54
got to be H so you can get a difference
20:56
of 1 okay so these numbers give you the
20:58
height of the sub-trees prior to the
21:01
insert all right so this picture fully
21:05
categorizes the ll case there are no
21:08
other possibilities for the other case
21:09
it's got to look exactly like that when
21:14
you do the insert it's going to go in
21:16
here okay so BL changes it becomes B
21:24
prime L we don't really know where in BL
21:29
you made the insert it doesn't matter
21:31
okay but the height of BL has to change
21:36
it has to go up by one okay if the
21:39
height does not go up by one then the
21:42
balance factor out here cannot change
21:44
and if the back sorry the balance factor
21:48
can change but if the height of BL
21:50
doesn't go up then the height of this
21:52
subtree cannot go up and you shouldn't
21:54
have backed up to that point okay so we
21:59
know that the height of BL has to go up
22:02
so previously it was H it now becomes H
22:05
plus one okay and as a result the
22:08
balance factor there changes from zero
22:11
to plus one okay so when the height of
22:14
the left subtree goes up by one balanced
22:16
factor increases by one so the new
22:18
balance factor here is one and then you
22:22
move back up when you compute the
22:23
balance factor there
22:25
it was previously one now it becomes two
22:27
and you can see that from this picture
22:29
also the height of this subtree is H
22:33
plus 1 so the height of the subtree here
22:35
is h plus 2 the height on that side is H
22:37
so the balance is plus 2 so prior to
22:46
insertion you have to look like this
22:48
just after the first phase of the
22:51
insertion you have to look like that and
22:54
now we will perform an ll rotation the
22:58
ll rotation will preserve the binary
23:00
search tree property but restore the
23:03
balance at this point ok so the rotation
23:07
will take this node here the left child
23:11
of a and move it up to the position of a
23:13
and then relocate everybody else to
23:16
satisfy the binary search tree property
23:19
ok alright so this fellow is promoted
23:24
one level up the tree so it looks like
23:29
that then we place everybody else to
23:34
satisfy the binary search tree property
23:36
B prime L contains items that are
23:38
smaller than B so they must form the
23:41
left subtree of B a has an item that is
23:48
bigger than B so it's going to become
23:51
the root of the right subtree so is the
23:54
right child BR has things that are
23:58
bigger than B but smaller than a okay so
24:04
bigger than B smaller than a is going to
24:07
come here so move that subtree over
24:09
there
24:09
and then a sub r has things that are
24:13
bigger than a there of course also
24:15
bigger than B so that will remain as the
24:18
right subtree of a alright so those are
24:22
the that's the structural change that
24:24
I'll perform in this rotation to make
24:29
this change I go to change some number
24:32
of pointers the pointer coming from the
24:34
parent of a is going to change its going
24:37
to move to this node with
24:38
before it was going to this note the
24:42
left child pointer of B stays the same
24:44
as it was before the right child pointer
24:47
of B changes it now goes to a proof so
24:50
it's going to be R the left child point
24:53
of a changes it comes here to be R where
24:56
before it was going to be the right
24:58
child pointer stays the same okay so
25:01
there's a small number of pointer
25:04
changes maybe they're like three pointer
25:06
changes or four pointer changes you have
25:07
to make in addition to those small
25:14
number of pointer changes you have to
25:16
change some balance factors the balance
25:20
factors of the nodes in B prime L are
25:23
not changed as a result of this
25:25
transformation the balance factors
25:28
inside BR are not changed and inside a
25:31
are they're not changed either because
25:33
we don't change their sub trees the only
25:36
balance factors that are affected are in
25:38
B and a the balance factor of a becomes
25:43
zero okay left and right subtrees have
25:46
the same height and the balance factor
25:49
at b becomes zero left and right
25:52
subtrees have the same height okay so
25:57
some number of pointer changes and to
26:01
balance factor changes right so this is
26:08
the rotation now we can see that the
26:13
rotation preserves the binary search
26:15
tree property of the tree the other
26:20
thing we can see is that the height of
26:22
the subtree rooted at this point before
26:25
the insertion it was h h plus 1 h plus 2
26:30
after the insertion at the same point
26:33
the height of the subtree is h h plus 1
26:36
h plus 2 so the height before and after
26:40
the rotation is unchanged and what that
26:46
means is you don't need to retrace the
26:49
path any further toward
26:52
you can stop right here the the
26:54
remaining balance factors will not be
26:56
changed alright so by performing this
27:05
transformation I restore balance to the
27:08
tree I don't back up any further on the
27:12
tree this rotation takes constant amount
27:18
of time of course in addition to this
27:22
constant time spent on the rotation you
27:24
may spend log n time backing up from the
27:28
new node toward the root changing
27:29
balance factors until you reach the a
27:32
node there are any questions about an ll
27:40
rotation the RR is very similar it's
27:44
just done on the other side all right
27:50
let's look at the LR rotation the LR
27:53
rotation is going to be broken down into
27:56
three sub cases all of these sub cases
28:00
involve the same structural change to
28:03
the tree the only difference is the
28:05
balance factors of some of the nodes at
28:08
the end of the transformation alright so
28:15
the first case is you go into the left
28:19
subtree of the a node so it's balanced
28:20
factor was one prior and then we're
28:24
going to go into the right subtree of
28:26
the root out here and it's balanced
28:29
factor prior to the insertion was zero
28:30
and in the first case I'm assuming that
28:33
the right subtree was empty okay so the
28:36
right subtree was empty so also is the
28:38
left subtree cuz the balance factor is
28:39
zero alright so this is the first case
28:48
I'm going to insert it here okay so the
28:52
insertion takes place in the right
28:54
subtree of the left child of a this is
28:58
got to look like that because this case
29:00
is where B has no right subtree prior to
29:03
the insertion
29:06
so the balance factors the new node has
29:09
a balance factor of zero okay and then
29:11
you're kind of retracing the path the
29:13
balance factor here is going to decrease
29:15
by one so it becomes minus one up there
29:18
it's going to increase by one it becomes
29:19
plus two so the transformation that I'm
29:27
going to do is going to take this fellow
29:30
here and in the general case this fellow
29:33
is going to be the right child of B it
29:37
also happens to be the new node at this
29:39
time but for the other cases it will not
29:41
be the new node it will be the right
29:44
child of B okay so the right child of B
29:47
is going to be promoted up two levels to
29:49
become the root of that subtree and then
29:53
everybody else is kind of placed to
29:54
satisfy the binary search tree
29:56
requirements so B is smaller than C so
30:02
it becomes the left child of C a is
30:06
bigger than C so it becomes the right
30:09
child of C okay so I get a binary search
30:12
tree rooted at that same position the
30:16
balance factors of the new nodes are all
30:19
0 if you check the height of the sub
30:27
tree rooted in this position before and
30:29
after okay
30:32
before the height is 2 and then
30:34
afterwards it's the same thing you got
30:37
two levels high does too okay and so
30:41
once you've done this there's no point
30:43
backing up further because everybody
30:45
else has a balance factor that's the
30:47
same as it was prior to the insertion
30:56
all right so the subtree height is
30:58
unchanged this terminates the backup
31:02
process you stop here again the time
31:08
required to perform the rotation is
31:10
order one there's a some number of
31:12
pointer changes and balance factor
31:15
changes alright let's go to the second
31:22
case the second case B actually has a
31:26
right child prior to the insertion so
31:32
I'll call that node the C node in the
31:35
previous case we still had a C node with
31:37
the C note emerged only after you did
31:40
the insert it wasn't there before the
31:41
insert now I've got a C note out here
31:44
and potentially this has a subtree CL
31:47
and C are okay these may be empty the
31:53
balance fact again that the a node has
31:54
to be one before the insertion on the
31:57
path toward the inserted node the
32:00
balance factors had to be zero so this
32:02
bounce factor has to be zero then we go
32:04
to the right subtree of B the bounce
32:05
factor has to be zero
32:06
and if you end up going this way all the
32:09
balance factors you encounter must be
32:10
zero okay all right since the balance
32:15
factor here is zero the heights of these
32:17
two fellows must be the same of course
32:19
both could be empty which is all right
32:21
so we call that height H minus one okay
32:24
the bounce factor here is zero so the
32:27
height of BL must be the same as the
32:29
height of the sub tree rooted at C so
32:31
that's got to be H the balance factor
32:33
here is one so the height of a sub R
32:36
must be one less than the height of the
32:38
sub tree rooted at B there's got to be H
32:40
up there okay so this describes the
32:43
generic case you do the insert and in
32:49
case - I'm going assume the insert took
32:52
place and C Prime and C out in case
32:54
three the insert takes place here okay
32:59
so I say took place here so you got a
33:02
new sub tree there C prime L and the
33:05
height of C prime L must have increased
33:08
if it didn't increase we
33:10
would stop the back-trace right here
33:12
we'd not be going back up to find that a
33:14
node okay so the height of C prime L
33:17
went up from H minus 1 to H all the
33:21
other sub trees have the same height
33:22
before and after the insertion all right
33:26
so the balance factor here is previously
33:29
zero it now is one will be coming from
33:33
the left side over here does previous is
33:35
zero now it must be minus one over here
33:38
it is previously one it now becomes two
33:43
again you can verify those numbers by
33:45
subtracting the heights that are shown
33:47
in the figure all right so we're going
33:54
to perform a rotation which is
33:57
essentially what we did before this node
34:00
here if the see node is going to get
34:02
promoted up two levels and occupy the
34:04
place of the old a node B is smaller
34:13
than C it becomes the left child of C a
34:17
is well bigger than C so it becomes the
34:23
right child BL has items that are
34:26
smaller than B so it should be the left
34:28
subtree of B then we have C prime L has
34:35
things that are bigger than B but
34:37
smaller than C okay so smaller than C
34:41
bigger than B and then we come here see
34:47
R is going to be smaller than a bigger
34:54
than B bigger than C okay so smaller
34:59
than a bigger than B bigger than C
35:01
bigger than C smaller than a and then AR
35:09
has things that are bigger than a also
35:11
bigger than B bigger than C so bigger
35:15
than C bigger than a it's going to show
35:17
up over there I said that preserves the
35:20
search tree property
35:24
the heights of BLC Prime now see
35:28
ar-ar-ar unchanged because of the
35:31
transformation the balance factors that
35:35
change are in those pink nodes a B and C
35:39
the balance factors are zero minus one
35:44
and zero okay that's a little different
35:49
from the previous case where it was zero
35:52
zero and zero but otherwise the
35:54
structural changes are pretty much the
35:56
same again if you look at the height of
36:01
the sub tree rooted at this point okay
36:04
so prior to the insertion this was H
36:07
minus 1 H up to this point h plus 1 h
36:10
plus 2 if you look out here you got h at
36:14
this level h plus 1 h plus 2 okay so the
36:18
height of the sub tree rooted at this
36:20
point is the same before and after the
36:23
transformation and so the balance
36:27
factors further up if you go to the
36:29
parent of C the grandparent they're all
36:31
stay the same as they were before the
36:32
insert okay so again this rotation fixes
36:36
the problem alright the third case is
36:41
pretty much the same except that the
36:44
insertion now takes place here okay so
36:48
if the insertion takes place out there
36:49
this height goes up by one and the new
36:53
balance factors are going to look like
36:55
that the transformation is the same this
37:00
fellow becomes the new root a and B
37:02
occupy the same places as they did
37:04
before the sub trees fall in the same
37:07
places it's only the balance factors
37:09
that are different this is a bounce
37:11
factor one and zero previously it was
37:13
zero and minus one so that's the only
37:19
difference the balance factors of a B
37:20
and C are different amongst the three
37:22
cases but in all three cases the
37:26
transformation fixes the imbalance
37:30
problem it also terminates the second
37:33
phase you don't move any further up
37:35
toward the root
37:41
all right any questions about an insert
37:44
and the fact that in log n time you can
37:50
in fact do the insert the first phase of
37:53
course is log n because the height was
37:55
log N and then the backward retrace is
37:58
also log in because you just go back up
38:01
a path whose height is log in and at
38:05
each point you do order one work but the
38:12
nice thing about the insert algorithm
38:14
isn't just that it works in log n time
38:17
but it does only one rotation or at most
38:20
one rotation to fix the imbalance okay
38:25
in many applications that's important
38:27
because we will later see applications
38:29
where a rotation cannot be done in order
38:33
one time in a simple AVL tree it can but
38:37
when you extend AVL trees to other
38:39
applications or dictionaries then
38:43
rotations may take more than order one
38:46
time well let's turn our attention to
38:52
well I guess not yet let's just make a
38:56
connection between LR ll ro and our our
39:00
rotations ok so some people referred to
39:04
things called single rotations and
39:06
double rotations with single refers to
39:09
ll and RR and double rotation refers to
39:13
the LR and RL the more complex rotation
39:16
and to see why these are called double
39:21
rotations we can see a connection ok
39:24
between the double and two singles ok so
39:30
an LR rotation is really an LR followed
39:33
so it's really an RR followed by an LL
39:35
and we'll see that in a moment
39:37
and the RL is an LL followed by an RR ok
39:42
let's see a picture for one of these two
39:43
cases the LR
39:48
right so the LR is given by this
39:51
situation it's one of the three cases
39:54
okay so the first thing I'm going to do
39:56
here is with respect to B okay for the
40:02
moment mentally picture this as the a
40:04
node and do an RR rotation with respect
40:07
to this so that is going to bring C up
40:09
here and bring be down there okay
40:13
so I do an RR rotation with respect to
40:15
this node as the a you end up with that
40:18
picture then I'm going to do an LL with
40:21
respect to that node as the a node okay
40:23
and that'll move the C up okay you end
40:26
up with that picture okay so this is the
40:31
before the transformation picture we had
40:35
previously and that's the after
40:37
transformation picture but now I've gone
40:39
from here to there in two steps first do
40:42
an RR and then do an ll okay so you can
40:47
actually even code an RL as one call to
40:51
and RR followed by a call to an LL
40:54
rotation okay all right so ll and lr +
41:00
RL are known as double rotations the
41:02
others are singles okay let's take a
41:10
quick look at how you would remove an
41:11
element or delete an element and here
41:17
what we will see is that while you can
41:19
do the deletion in logarithmic time the
41:22
number of rotations needed is also
41:24
logarithmic and that's bad from the
41:28
stand point or more advanced
41:29
applications for trees it's okay for the
41:34
standard dictionary operation because
41:36
the rotation takes over one but more
41:38
advanced applications and also settle
41:40
mentioned some of these later require
41:42
more complex work to be done when you do
41:45
a rotation all right so want to remove
41:50
an element of course again it's done in
41:53
two phases one is pretend you don't care
41:56
about the fact is an AVL tree take it
41:58
out like you would for an ordinary
42:00
search tree
42:01
and then you have this backward pass
42:05
where you're adjusting balance factors
42:06
and if somebody becomes plus 2 or minus
42:07
2 you do a rotation ok so the setup is
42:10
very similar all right suppose you had
42:17
to remove the 8 okay so we follow a path
42:21
we come down here we throw that node
42:24
away so a deletion always removes one
42:31
physical node it may not be the node
42:34
that originally contained the item
42:35
you're taking out because if you
42:38
remember deletion from a notice degree
42:40
is 2 requires promotion of an element
42:43
further up okay but there is one node
42:45
that is physically thrown away okay and
42:48
we let Q be the parent of that node that
42:50
is physically thrown away if the node
42:54
that is physically thrown away doesn't
42:56
have a parent then you're left with an
42:57
empty tree which is AVL so you don't
43:00
have to do anything okay so we can
43:02
assume that the node that is physically
43:04
thrown away does in fact have a parent
43:08
okay all right so the node Q exists okay
43:18
all right so this node is physically
43:23
thrown away its parent is Q when you
43:28
throw away this node the height of the
43:30
sub tree rooted out here decreases it
43:32
was previously 1 it becomes 0 since
43:34
you're coming from the right side the
43:35
balance factor is going to go up by one
43:38
okay so that balance factor in this case
43:41
becomes 2 and we have something that's
43:46
no longer AVL and we have to move into a
43:48
rectification stage
43:55
all right so Q is the parent of the node
44:01
that is physically thrown out and then
44:03
we're going to retrace the path from
44:05
here up toward the root either fixing
44:08
balance factors of finding nodes that
44:10
are plus 2 or minus 2 and performing
44:12
rotations all right so when you come to
44:19
a node the new balance factor of Q if
44:22
you're coming from the left subtree okay
44:25
that means the height of the left
44:26
subtree became less by 1 so your balance
44:28
factor decreases by 1 if you're coming
44:31
from the right side the balance factor
44:32
goes up by 1 right if the new balance
44:40
factor at Q becomes plus 1 or minus 1
44:43
that means previously it was 0 so now
44:48
what's happened is one sub trees become
44:50
a little shorter than the other but the
44:51
height of that sub tree rooted at Q
44:54
hasn't changed from what it was before
44:55
okay so if the new balance factors plus
44:58
1 or minus 1 there's no change in the
45:01
height of the sub tree rooted at Q and
45:03
so you can stop if it becomes 0 then the
45:09
height of the sub tree rooted is Q has
45:11
decreased by 1 and you have to continue
45:14
going up if it becomes plus 2 or minus 2
45:18
you've become imbalanced and you go to
45:20
fix the imbalance all right so we
45:24
classify the imbalance okay again the a
45:28
node is the fellow that's become plus 2
45:29
or minus 2 if you deleted from the left
45:33
sub tree you call it an L type if you
45:36
delete it from the right sub tree you
45:37
call it an R type let's take a look at
45:42
the R type so we delete it from the
45:44
right subtree of a okay the new balance
45:48
factor is going to become plus 2 okay
45:50
because the height of the right subtree
45:52
is decreased by 1 so balance factor
45:53
increases which means previously it was
45:56
plus 1 okay so if the old balance factor
46:02
was plus 1 that means that a must have a
46:04
left child
46:07
because it's the height of its left
46:10
subtree is one more than the height of
46:11
its right subtree okay so it's got to
46:13
have a left child B if the balance
46:16
factor of B is zero I'll call this R
46:18
zero if the balance factor of B is one
46:20
I'll call it R 1 the balance factor of B
46:23
is minus one I'll call it our minus one
46:25
and then for each of these three cases
46:27
I'll have a rotation as we'll see the
46:31
rotation is the same as one of the
46:33
earlier ones so it's not a new rotation
46:35
okay all right so look at R 0 so R 0 is
46:41
given by this this is the before
46:43
deletion we're going to delete from the
46:45
right side of this fellow so the height
46:47
here drops to H minus 1 and then the
46:50
balance factor there becomes 2 okay so
46:55
the way you handle this is we're going
46:58
to do a rotation around here so this one
47:02
moves up and you end up with the
47:04
configuration that's shown out there so
47:09
if you look at the configuration here on
47:11
the right ok
47:13
the height of the sub tree rooted here
47:18
okay so you got h h plus 1 h plus 2 if
47:24
you look at it over here h h plus 1 h
47:27
plus 2 so the height of the sub tree
47:29
rooted at this position is unchanged
47:31
from before to after the deletion which
47:36
means you can terminate the process you
47:37
don't go back any further
47:39
okay so subtree height is unchanged you
47:42
terminate the process so in this case a
47:49
single rotation surfaces of this single
47:52
rotation surfaces
47:56
again now you don't know that this is
47:58
really the same as the ll rotation if
48:04
you go to the r1 case okay so the
48:09
balance factor of B was previously a 1
48:12
so I'm going to delete from here and the
48:15
height here has to decrease by 1 and
48:17
then it becomes plus 2 over there okay
48:19
so you got it look like that and this
48:24
time I will again do an ll rotation okay
48:30
so do the same thing I did previously
48:31
it's only the balance factors change
48:34
okay but now if you look at the heights
48:36
okay
48:37
the height here we saw was H plus 2
48:39
before okay if you look at it now it's H
48:42
minus 1 h h plus 1 so the height has
48:45
gone down by one okay so you can't stop
48:49
here you go to keep going back up and
48:51
when you go up one node the height you
48:53
may do another rotation there and the
48:55
height goes down by one and so on okay
48:57
so the Heights reduced by one you can't
49:00
stop you going to continue okay what do
49:03
we fix the balance of that level
49:04
probably creating problems further up
49:07
the tree right so this is the same as
49:11
the ll or our zero stuff the third case
49:18
is the R minus one so the balance factor
49:21
here is minus one that's the definition
49:22
of the R minus one case deletion is done
49:27
from the right subtree away so the
49:28
height here goes down by one so it's got
49:30
it look like that okay because the
49:34
balance factor of C could be anything it
49:35
could be zero plus one minus one so I'm
49:39
just using a variable there be okay now
49:44
we will perform an LR rotation okay so
49:48
this fellow will be promoted up two
49:51
levels and then you place everybody else
49:52
exactly as you would in an LR rotation
49:55
so you end up with something that looks
49:57
like this and if you look at the height
50:00
here okay it's H minus 1 h h plus 1
50:04
whereas prior it was h plus 2 so again
50:08
the height
50:10
has gone down I haven't shown the
50:14
balance factors of a and B they depend
50:16
upon the value of it'll be okay but if
50:19
you knew little B you can figure out the
50:21
balance factors out there okay all right
50:25
the height has gone down by one so you
50:27
can't stop you have to continue going
50:30
further up and as you go further up you
50:33
may perform more rotations okay but
50:37
again each rotation takes order one time
50:39
and so you do it most log and rotations
50:43
on the backward pass spending a total of
50:45
log n time for the delete all right
50:49
finally okay I get that we've seen one
50:52
rotation for an insert log n for a
50:54
delete some experimental studies with
50:58
random numbers insertions okay if you do
51:01
insertions about half the time there are
51:04
no rotations so just like inserting into
51:07
an unbalanced binary search tree about
51:11
one-fourth of the time you do a single
51:13
rotation and about one-fourth of the
51:17
time you do a double rotation okay so
51:21
the expensive rotations are only done
51:23
one-fourth of the time half the time
51:25
there's really no loss in performance as
51:29
far as that individual rotation is
51:31
concerned of course over a sequence
51:33
you're doing a lot better because now
51:34
you're guaranteed logarithmic time for
51:37
operation was before you could be doing
51:39
order n time per operation okay so I
51:44
guess we'll stop here