1
00:00:00,012 --> 00:00:04,427
In this video and the next we are going 
to take you to the next level and here 

2
00:00:04,427 --> 00:00:08,732
under the hood into implementations of 
balanced pioneer research trees. 

3
00:00:08,732 --> 00:00:12,867
Now frankly when any great details of all 
balance binary research tree 

4
00:00:12,867 --> 00:00:17,652
implementations get pretty complicated 
and if you really want to understand them 

5
00:00:17,652 --> 00:00:21,617
at a fine grain level there is no 
substitute for reading an advanced 

6
00:00:21,617 --> 00:00:25,897
logarithms textbook that includes 
coverage of the topic and/or studying 

7
00:00:25,897 --> 00:00:29,480
open source Implementations of these data 
structures. 

8
00:00:29,480 --> 00:00:33,261
I don't see the point of regurgitating 
all of those details here. 

9
00:00:33,261 --> 00:00:37,448
What I do see the point in doing, is 
giving you the gist of some of the key 

10
00:00:37,448 --> 00:00:41,599
ideas in these implementations. 
In this first video I want to focus on a 

11
00:00:41,599 --> 00:00:46,778
key primitive, that of rotations which is 
common to All balanced by the [INAUDIBLE] 

12
00:00:46,778 --> 00:00:50,632
of limitations. 
Whether is red, black trees, EVL trees, B 

13
00:00:50,632 --> 00:00:53,827
or B+ trees, whatever all of them use 
rotations. 

14
00:00:53,827 --> 00:00:58,851
In the next video we'll talk a little bit 
more about the details of red, black 

15
00:00:58,851 --> 00:01:02,754
trees in particular. 
So, what is the points behind these 

16
00:01:02,754 --> 00:01:08,277
magically rotation operations? Well the 
goal is to do just constant work, just 

17
00:01:08,277 --> 00:01:13,463
re-wire a few pointers, and yet locally 
re-balance a search tree, without 

18
00:01:13,463 --> 00:01:17,084
violating the search tree properties/g 
Property. 

19
00:01:17,084 --> 00:01:22,348
So there are two flavors of rotations, 
left rotations and right rotations. 

20
00:01:22,348 --> 00:01:27,453
In either case, when you invoke a 
rotation it's on a parent child pair, in 

21
00:01:27,453 --> 00:01:31,313
a search tree. 
If it's a right child of the parent, then 

22
00:01:31,313 --> 00:01:35,392
you use a left rotation. 
We'll discuss that on this slide. 

23
00:01:35,392 --> 00:01:40,887
And a right rotation is, in some sense, 
an inverse operation which you use when 

24
00:01:40,887 --> 00:01:46,123
you have a left child of the parent. 
So what's the generic picture look like 

25
00:01:46,123 --> 00:01:51,509
when you have a node x in a search tree 
and it has some right child y? Well x, in 

26
00:01:51,509 --> 00:01:56,486
general, might have some parents. 
x might also have some left subtree. 

27
00:01:56,486 --> 00:02:03,359
Let's call that left subtree of x, A. 
It could, of course, be And then Y has 

28
00:02:03,359 --> 00:02:08,383
it's 2 subtrees, lets call the left 
subtree of Y B and the right subtree C. 

29
00:02:08,383 --> 00:02:12,312
It's going to be very important that 
rotations preserve the search tree 

30
00:02:12,312 --> 00:02:16,782
property so to see why that's true lets 
just be clear on exactly which elements 

31
00:02:16,782 --> 00:02:19,867
are bigger then which other elements in 
this picture. 

32
00:02:19,867 --> 00:02:24,485
So first of all Y being a right child of 
X, Y's going to be bigger than x. 

33
00:02:25,527 --> 00:02:30,127
Now all of the keys which line the 
subtree a because they're to the left of 

34
00:02:30,127 --> 00:02:32,992
x these keys are going to be even smaller 
than x. 

35
00:02:32,992 --> 00:02:37,922
By the same token anything in the subtree 
capital c, that's to the right of y so 

36
00:02:37,922 --> 00:02:40,822
all that stuff's going to be even bigger 
than y. 

37
00:02:40,822 --> 00:02:46,148
What about sub tree capital B? What about 
the nodes in there? Well, on the one 

38
00:02:46,148 --> 00:02:51,574
hand, all of these are in x's right sub 
tree, right? To get to any node in B, you 

39
00:02:51,574 --> 00:02:55,210
go through x and then you follow the 
right child to y. 

40
00:02:55,210 --> 00:03:00,561
So that means everything is B is bigger 
than x, yet, at the same time, it's all 

41
00:03:00,561 --> 00:03:05,116
in the left sub tree of y so these are 
all Things smaller than y. 

42
00:03:05,116 --> 00:03:10,214
Summarizing all of the nodes in b have 
keys strictly in between x and y. 

43
00:03:10,214 --> 00:03:15,717
So now that we're clear on how all of 
these search keys in the different parts 

44
00:03:15,717 --> 00:03:20,815
of this picture relate to each other, I 
can describe the point of a left 

45
00:03:20,815 --> 00:03:24,442
rotation. 
Fundamentally the goal is to invert the 

46
00:03:24,442 --> 00:03:27,699
relationship. 
Between the nodes x and y. 

47
00:03:27,699 --> 00:03:31,286
Currently x is the parent and y is the 
child. 

48
00:03:31,286 --> 00:03:37,361
We want to rewire a few pointers so that 
y is now the parent and x is the child. 

49
00:03:39,168 --> 00:03:44,217
Now what's cool is given that is our goal 
is pretty much a unique way to put all 

50
00:03:44,217 --> 00:03:47,191
these pieces back together to accomplish 
it. 

51
00:03:47,191 --> 00:03:51,435
So lets just follow our nose. 
So remember the goal Y should be the 

52
00:03:51,435 --> 00:03:56,390
parent and X should be the child. 
Well, X is less then And why and there's 

53
00:03:56,390 --> 00:04:01,024
nothing we can do about that. 
So if x is going to be a child of y, its 

54
00:04:01,024 --> 00:04:05,430
got to the left child. 
So your first question might be well what 

55
00:04:05,430 --> 00:04:10,042
happened that x is parent. 
So x use to have some parent lets call it 

56
00:04:10,042 --> 00:04:14,342
p and x's new parent is y. 
Similarly y used to have parent x and 

57
00:04:14,342 --> 00:04:19,188
there's a question what should y new 
parent be? Well y is just going to 

58
00:04:19,188 --> 00:04:23,122
inherit x's old parent p. 
SO this change has no bearing for the 

59
00:04:23,122 --> 00:04:26,661
search tree property. 
Either of this collection of nodes was 

60
00:04:26,661 --> 00:04:31,321
P's left sub tree, in that case all these 
nodes were less than P, or this sub tree 

61
00:04:31,321 --> 00:04:35,981
was P's right sub tree which in that case 
all of these are bigger than P, but P can 

62
00:04:35,981 --> 00:04:39,562
really care less , which of X or Y is 
it's direct descendant. 

63
00:04:39,562 --> 00:04:44,122
Now lets move on to thinking about 
how...what we should do with the 

64
00:04:44,122 --> 00:04:47,910
sub-trees A, B and C. 
So, we have 3 sub-trees we need to 

65
00:04:47,910 --> 00:04:53,086
re-assemble into this picture, and 
fortunately we have 3 slots available. 

66
00:04:53,086 --> 00:04:57,671
X has both of its child pointers 
available and Y has its right child 

67
00:04:57,671 --> 00:05:01,515
available. 
So what Can we put where? Well, a, is the 

68
00:05:01,515 --> 00:05:04,882
sub tree of stuff which is less than both 
x and y. 

69
00:05:04,882 --> 00:05:07,825
So, that should sensibly be x's left 
child. 

70
00:05:08,979 --> 00:05:14,084
That's exactly as it was before. 
By the same token, capital C is the stuff 

71
00:05:14,084 --> 00:05:19,420
bigger than both x and y, so that should 
be, y, the bigger nodes child, right 

72
00:05:19,420 --> 00:05:23,581
child just as As before. 
And what's more interesting is what 

73
00:05:23,581 --> 00:05:28,161
happens to subtree capital B. 
So B used to be Y's left child but that 

74
00:05:28,161 --> 00:05:31,805
can't happen anymore, 'cause now X is Y's 
left child. 

75
00:05:31,805 --> 00:05:36,941
So, the only hope is to slot capital B 
into the only space we have for it, X's 

76
00:05:36,941 --> 00:05:40,335
right child. 
Fortunately for us this actually works, 

77
00:05:40,335 --> 00:05:43,315
sliding B into the only open space we 
have for it. 

78
00:05:43,315 --> 00:05:47,141
X's right child does indeed preserve the 
switch tree property. 

79
00:05:47,141 --> 00:05:51,494
Recall we notice that every key in 
capital B is strictly between X and Y, 

80
00:05:51,494 --> 00:05:56,140
therefore it better be and X's right sub 
tree and it better be in Y's right sub 

81
00:05:56,140 --> 00:05:58,974
tree, but it is, that's exactly where we 
put it. 

82
00:06:00,069 --> 00:06:04,284
So that's a left rotation, but if you 
understand a left rotation then you 

83
00:06:04,284 --> 00:06:08,282
understand a right rotation as well. 
because a right rotation is just the 

84
00:06:08,282 --> 00:06:11,629
inverse operation. 
So that's when you take a parent child 

85
00:06:11,629 --> 00:06:16,200
pair, where the child is the left child 
of the parent, and now you again want to 

86
00:06:16,200 --> 00:06:19,853
invert the relationship. 
You want to make the old child the new 

87
00:06:19,853 --> 00:06:24,883
parent and the old parent the new child. 
And once again given this goal there's 

88
00:06:24,883 --> 00:06:30,147
really a unique way to reassemble the 
components of this picture so that the 

89
00:06:30,147 --> 00:06:33,904
goal's accomplished, so that y is now the 
parent of x. 

90
00:06:33,904 --> 00:06:39,374
So what are the laudable properties of 
rotations? Well first of all I hope it's 

91
00:06:39,374 --> 00:06:44,627
clear that they can be implemented. 
In a constant time or you were doing a 

92
00:06:44,627 --> 00:06:49,816
rewiring a constant number of pointers. 
Further more as have discussed they 

93
00:06:49,816 --> 00:06:54,853
preserve the search tree property. 
So these nice properties are what make 

94
00:06:54,853 --> 00:06:59,862
rotations the ubiquitous primitive common 
to all balanced search tree 

95
00:06:59,862 --> 00:07:02,907
implementations. 
So this of course, is not the whole 

96
00:07:02,907 --> 00:07:05,633
story. 
In a complete specification of a balanced 

97
00:07:05,633 --> 00:07:10,156
search tree implementation, you have to 
say exactly when and how you deploy these 

98
00:07:10,156 --> 00:07:12,932
rotations. 
You'll get a small taste of that in the 

99
00:07:12,932 --> 00:07:16,845
next video but if you really want to 
understand it in more depth, I again 

100
00:07:16,845 --> 00:07:21,203
encourage you to check out either a 
comprehensive Data structures textbook. 

101
00:07:21,203 --> 00:07:25,397
Check out a number of balance search tree 
demonstrations, which are readily 

102
00:07:25,397 --> 00:07:28,173
available on the web. 
Or have a peek at an open source 

103
00:07:28,173 --> 00:07:29,780
implementation of one of these data 
structures.