1 00:00:00,510 --> 00:00:05,400 OK, so in this lecture, we are going to be talking about something called Avielle trees. 2 00:00:07,490 --> 00:00:12,230 So to do that, we're going to take a look back at the binary search tree stuff that we've been doing. 3 00:00:12,410 --> 00:00:20,000 So one of the major issues that we had with the binary search tree was the worst case input into it. 4 00:00:20,010 --> 00:00:25,220 So that was when we had something in descending, sorted order or ascending sorted order. 5 00:00:25,910 --> 00:00:32,810 And if you remember back to that, it caused a minor search tree to basically become an imbalanced tree 6 00:00:32,810 --> 00:00:37,760 to the point of it just being a linked list, which wasn't good because one of the good things about 7 00:00:37,760 --> 00:00:44,290 the binary search she was its structure that gave us that log in search time. 8 00:00:44,300 --> 00:00:51,650 But when it was a linked list, we had to basically abide by the time complexity of the link list because 9 00:00:52,460 --> 00:00:54,890 it was the same size of the input, so it was linear time. 10 00:00:55,580 --> 00:00:58,700 So let's go ahead and just recap on that right here. 11 00:00:58,770 --> 00:01:04,940 We're going to have these two examples of descending and descending sorted order input just to show 12 00:01:04,940 --> 00:01:07,060 you once again what we're talking about. 13 00:01:08,170 --> 00:01:11,410 So we start out here with this input five, four three two one. 14 00:01:12,010 --> 00:01:13,660 So the route now will be five. 15 00:01:13,870 --> 00:01:17,710 The four comes in, it becomes the left child because it's less than five. 16 00:01:18,280 --> 00:01:19,180 Three comes in. 17 00:01:19,190 --> 00:01:20,380 It's less than five and four. 18 00:01:20,380 --> 00:01:24,280 So we have another left child and so on and so forth down to one. 19 00:01:24,290 --> 00:01:27,250 So you notice this is just like completely left leaning. 20 00:01:27,550 --> 00:01:29,710 And so it's essentially a linked list at this point. 21 00:01:31,210 --> 00:01:34,480 So if we do it the other way we start with one is the rule. 22 00:01:35,560 --> 00:01:36,880 Two is greater than one. 23 00:01:37,360 --> 00:01:40,240 Three is greater than one or two and so on and so forth. 24 00:01:40,250 --> 00:01:44,460 Now we just have a right leaning tree that's basically a linked list as well. 25 00:01:44,470 --> 00:01:49,960 So that's kind of what we're talking about with the issue with standard binary search tree. 26 00:01:51,500 --> 00:01:54,440 The Avielle tree fixes this problem. 27 00:01:55,720 --> 00:02:01,600 By self-balancing, so it belongs to a class of trees that we refer to as self-balancing. 28 00:02:02,170 --> 00:02:09,250 There are some other trees and I'm not going to go over that can do similar things like red black trees 29 00:02:09,250 --> 00:02:12,820 might be one of them, but I'm not going to cover that. 30 00:02:12,820 --> 00:02:15,790 I'm just going to go over one of them and I pick the real tree. 31 00:02:15,810 --> 00:02:17,500 So that's what we'll be looking at. 32 00:02:18,100 --> 00:02:19,330 How does it achieve this? 33 00:02:19,360 --> 00:02:24,790 Well, what it does is it actually assigns a special number to each node that is referred to as the 34 00:02:24,790 --> 00:02:25,870 balance factor. 35 00:02:26,790 --> 00:02:33,390 The balance factor for a certain node is decided by subtracting the height of the rights of tree coming 36 00:02:33,390 --> 00:02:40,680 off that node from the left some tree, so we do less of tree from that node minus rates of tree. 37 00:02:41,340 --> 00:02:46,290 If you're thinking about the height, you basically just follow the path from that node to the left. 38 00:02:46,290 --> 00:02:53,010 To get the height of the last century, you would find the biggest path down to a root node from that 39 00:02:53,550 --> 00:02:55,040 initial left pointer. 40 00:02:55,050 --> 00:03:01,050 So if you're at a node, head to the left, go down the longest path to the bottom of the tree, and 41 00:03:01,050 --> 00:03:01,950 that will be your height. 42 00:03:04,300 --> 00:03:07,780 Then same thing for the rights of Tree, of course, the height of the wrath of tree. 43 00:03:08,230 --> 00:03:12,340 And after all, these balance factors are assigned to each specific node. 44 00:03:12,880 --> 00:03:18,520 We then are going to check to see if any of those balance factors are greater than one or less than 45 00:03:18,520 --> 00:03:19,270 negative one. 46 00:03:19,900 --> 00:03:24,610 You can also think of this as just taking the absolute value of the balance factor. 47 00:03:24,940 --> 00:03:34,720 And if it is greater than or equal to one or sorry, if it is greater than one, then that is a problem. 48 00:03:35,790 --> 00:03:42,900 So in the case that it is greater than one, we will need to perform something we call a rotation on 49 00:03:42,900 --> 00:03:49,170 that subject area and that will rebalance the trees so we can get that time complexity that we want 50 00:03:49,170 --> 00:03:51,540 and maintain the structure of the tree. 51 00:03:52,370 --> 00:03:53,160 That's ideal. 52 00:03:55,150 --> 00:04:02,200 So I'm I go over just some examples of rotations, but first, we're just going to calculate the balance 53 00:04:02,200 --> 00:04:10,240 factors of these four different scenarios that we'll be running into, where each one will require different 54 00:04:10,240 --> 00:04:10,810 rotations. 55 00:04:10,810 --> 00:04:12,970 So let's just look at the balance factors first. 56 00:04:13,690 --> 00:04:15,700 So let's start on this one over on the left. 57 00:04:15,970 --> 00:04:20,230 This is going to be like a tree example just has three nodes. 58 00:04:20,710 --> 00:04:22,690 Let's go ahead and look at this bottom one. 59 00:04:22,690 --> 00:04:27,880 So bottom node, we have a height of zero minus a height of zero. 60 00:04:27,880 --> 00:04:28,690 So that's zero. 61 00:04:30,450 --> 00:04:31,260 The next one. 62 00:04:31,710 --> 00:04:33,120 Let's head down the last century. 63 00:04:33,870 --> 00:04:39,690 We have one, so the height of the century is one minus zero for the rates of tree is one. 64 00:04:39,900 --> 00:04:41,340 So balance factor of one. 65 00:04:42,460 --> 00:04:48,340 One to four, the last century, zero four, the rates of trade, so to minus zero is two. 66 00:04:49,030 --> 00:04:50,270 And that is a problem. 67 00:04:50,300 --> 00:04:51,610 That's why I've highlighted in red. 68 00:04:51,610 --> 00:04:57,520 So we said that if it's greater than one, that is an issue, if the absolute value is greater than 69 00:04:57,520 --> 00:04:58,720 one, that is an issue. 70 00:05:00,680 --> 00:05:05,270 So let's go ahead and do this other example, zero for the bottom. 71 00:05:05,630 --> 00:05:09,170 Then we have zero minus one that's minus one. 72 00:05:09,920 --> 00:05:14,780 Then we have zero minus one two, which is going to be minus two. 73 00:05:15,170 --> 00:05:16,870 Once again, that's an issue. 74 00:05:16,880 --> 00:05:18,560 It is less than negative one. 75 00:05:18,560 --> 00:05:23,570 Or if you're thinking about the absolute value, it is greater than one. 76 00:05:23,570 --> 00:05:25,820 The absolute value of this is two, which is greater than one. 77 00:05:27,720 --> 00:05:29,100 So let's see this other one. 78 00:05:29,280 --> 00:05:30,670 We have zero again. 79 00:05:30,990 --> 00:05:35,940 Then we have zero minus one, so minus one. 80 00:05:36,390 --> 00:05:40,800 Then we have one two minus zero, so that gives us two. 81 00:05:42,620 --> 00:05:44,330 Zero down here on this one. 82 00:05:44,510 --> 00:05:52,130 Then we have one one two zero one and we have zero minus one two, so that's going to be minus two zero 83 00:05:52,130 --> 00:05:52,580 minus two. 84 00:05:53,900 --> 00:05:56,720 OK, so let's start on the left again. 85 00:05:56,720 --> 00:06:01,970 And now we're going to go through some different slides where we talk about these actual rotations that 86 00:06:01,970 --> 00:06:05,600 we're going to have to do to balance these four different scenarios. 87 00:06:05,630 --> 00:06:07,070 So let's look at this one first. 88 00:06:08,270 --> 00:06:12,060 That one is going to be called an El Al rotation, which stands for the left left. 89 00:06:12,080 --> 00:06:15,620 And so it's essentially the turns that we are making. 90 00:06:15,620 --> 00:06:19,600 So we're taking the left and a left from the violating node. 91 00:06:20,030 --> 00:06:24,210 But technically, we can just say the imbalance is due to the height of a sub tree. 92 00:06:24,770 --> 00:06:28,460 That is the left child of the left child. 93 00:06:30,080 --> 00:06:37,280 So that is going to be our legal rotation, the violation notice here when we're going down to get our 94 00:06:37,280 --> 00:06:44,030 height from there, we went left and left to get that height. 95 00:06:44,570 --> 00:06:47,060 So that was one to minus zero. 96 00:06:47,070 --> 00:06:49,550 So we're considering this height. 97 00:06:49,880 --> 00:06:53,330 That was problematic to give us this bounce factor here. 98 00:06:54,590 --> 00:06:58,310 And to do that due to the rotation, you see this yellow arrow. 99 00:06:58,310 --> 00:07:03,410 We're taking this node and we're actually bringing it just down to here, right here. 100 00:07:04,190 --> 00:07:08,660 So the three is going to go here and the two is going to be pointing to the three. 101 00:07:08,840 --> 00:07:11,180 The three will be the right child at the two. 102 00:07:11,210 --> 00:07:12,140 So let's look at that. 103 00:07:13,340 --> 00:07:18,790 Just like that, the three came down here and became the right child of the two. 104 00:07:18,800 --> 00:07:20,870 So that was a left left rotation. 105 00:07:20,870 --> 00:07:28,760 And the left left is not for the rotation that we're doing it because it's it's named after the fact 106 00:07:28,760 --> 00:07:32,780 that it's a left turn and a left turn made this the violating node. 107 00:07:34,380 --> 00:07:35,450 The problem with the height. 108 00:07:37,120 --> 00:07:39,940 So let's look at a right right rotation. 109 00:07:40,270 --> 00:07:43,180 So that is just the opposite of the left left. 110 00:07:43,480 --> 00:07:51,700 So we have, you know, a right turn and a right turn here to get our height and the fact that this 111 00:07:51,700 --> 00:07:58,240 has zero and this was to me to have this imbalanced balance factor here. 112 00:07:58,840 --> 00:07:59,470 Same thing. 113 00:07:59,470 --> 00:08:00,790 We're going to bring it down here. 114 00:08:01,090 --> 00:08:06,340 Take this note, and we're going to send it right here and the two is going to have a left child of 115 00:08:06,340 --> 00:08:07,000 one now. 116 00:08:07,980 --> 00:08:12,990 So we see that right here now, we're all balanced after we do that rotation, so that is a right right 117 00:08:12,990 --> 00:08:13,680 rotation. 118 00:08:16,600 --> 00:08:22,030 A left right rotation, just like it sounds and just like we saw before, we have a left turn and a 119 00:08:22,030 --> 00:08:29,500 right turn for our problematic height issue with the balance factor for this one, though, there's 120 00:08:29,500 --> 00:08:38,110 kind of like two steps, like there's a couple sub steps, we'll still consider it one rotation as far 121 00:08:38,110 --> 00:08:43,990 as when we're going to implement this in code, but we actually are going to have to do two little mini 122 00:08:43,990 --> 00:08:44,500 steps. 123 00:08:45,460 --> 00:08:54,070 The first step is going to be to take the low air node here and bring that up in between these two nodes 124 00:08:54,070 --> 00:08:54,310 here. 125 00:08:55,570 --> 00:09:01,060 So we're taking this lower note, bring it up in between here, that gives us something like this. 126 00:09:01,660 --> 00:09:04,480 So now we have three and then two and then one. 127 00:09:05,590 --> 00:09:10,420 And what we're going to do at that point is we're going to do what we did for that left left rotation. 128 00:09:10,780 --> 00:09:14,470 We're going to take this three up here and move that three down here. 129 00:09:16,060 --> 00:09:18,060 So it's two little steps here. 130 00:09:18,070 --> 00:09:22,690 We took the two, put it in here, then we took the three and we're bringing it down here, and that 131 00:09:22,690 --> 00:09:25,150 gives us a nice balance again. 132 00:09:26,230 --> 00:09:27,370 So you can break it. 133 00:09:27,370 --> 00:09:29,980 It's a little easier, I think, to break into two steps. 134 00:09:29,980 --> 00:09:33,310 But if you want to just think about it in one rotation. 135 00:09:34,330 --> 00:09:44,440 An analogy I kind of like to think of is like, you know, little spheres or what have you with strings 136 00:09:44,440 --> 00:09:44,950 on them. 137 00:09:45,520 --> 00:09:53,290 And so I imagine that I had some type of, you know, the thing that I'm moving from the bottom right 138 00:09:53,290 --> 00:09:53,680 here. 139 00:09:54,340 --> 00:10:00,280 Like, if I had this and there was a string going here and a string going here and we had gravity and 140 00:10:00,280 --> 00:10:08,170 I took this and brought it up through here, then it would basically be, you know, if I brought the 141 00:10:08,170 --> 00:10:10,120 two and I brought it like way up here. 142 00:10:10,660 --> 00:10:16,840 The strings that connected to here and here would be pointing down to the three there and to the one 143 00:10:16,840 --> 00:10:17,650 just like this. 144 00:10:18,860 --> 00:10:25,400 So if you want to think about the rotation in that sense that you grab this and just bring it up through 145 00:10:25,400 --> 00:10:28,370 here and then you draw lines down like this. 146 00:10:29,870 --> 00:10:34,100 That's another way you can think of it, but it's kind of nice to break it in the steps, as we'll see 147 00:10:34,100 --> 00:10:40,700 in the near future here, because when you have, you know, bigger sub trees where there's more nodes 148 00:10:40,700 --> 00:10:46,490 coming off of these nodes down here, like larger centuries, it gets a little confusing when you're 149 00:10:46,490 --> 00:10:49,220 trying to think about changing pointers and things like that. 150 00:10:49,220 --> 00:10:55,490 So that's why I think the two step idea is a little bit better, but totally up to you. 151 00:10:57,120 --> 00:11:02,580 Right, Leffler wrote rotation, so let's let's think the opposite of the last one, we're going right 152 00:11:02,580 --> 00:11:03,510 and then left. 153 00:11:04,450 --> 00:11:05,800 For the balance factor issue. 154 00:11:06,610 --> 00:11:12,010 That's why it's called right left rotation, same thing, we're going to take this, bring it up through 155 00:11:12,010 --> 00:11:16,510 here and then we're going to take this one and bring it back down. 156 00:11:17,560 --> 00:11:18,760 So we do that first. 157 00:11:19,360 --> 00:11:24,130 We took the two, put it in between these two and then the ones coming back down here to be the left 158 00:11:24,850 --> 00:11:26,770 sub three of the two. 159 00:11:27,880 --> 00:11:28,570 Just like that. 160 00:11:31,370 --> 00:11:37,520 OK, so now I'm going to go over some bigger examples just so you know how to do it with a more realistic 161 00:11:37,520 --> 00:11:38,000 tree. 162 00:11:38,270 --> 00:11:44,180 So I already have some balance factors here that I forgot to feed in, so let's go ahead and populate 163 00:11:44,180 --> 00:11:45,440 it with the balance factors. 164 00:11:49,040 --> 00:11:57,500 So I already left those two there so that they can anti-climactic intro to this, but we have zero here, 165 00:11:58,160 --> 00:12:01,850 one for this, you know, zero here, this is not a problem. 166 00:12:02,510 --> 00:12:04,490 One two minus one, that's just one. 167 00:12:05,360 --> 00:12:06,320 This was zero. 168 00:12:06,320 --> 00:12:16,280 But this is going to be an issue here because we have one to three minus one gives us to appear. 169 00:12:17,290 --> 00:12:24,460 So this is a situation in which we are going to have to do a left left rotation because if we look at 170 00:12:24,460 --> 00:12:25,480 the violating, no. 171 00:12:27,480 --> 00:12:31,140 If we go down this direction. 172 00:12:32,710 --> 00:12:37,660 Towards where it was, the height was problematic, we have a left left. 173 00:12:38,470 --> 00:12:47,470 And so this is where we're going to have to basically think about the fact that we're going to just 174 00:12:47,470 --> 00:12:55,240 be talking about three nodes essentially all the time because you take two turns like two pointers that's 175 00:12:55,240 --> 00:12:56,920 going to connect you with three nodes. 176 00:12:56,920 --> 00:13:00,760 So it start on this one, the violin and Owen, and then we take a left and a left. 177 00:13:01,480 --> 00:13:07,450 So we're always going to be talking about three nodes that we're going to do a rotation on. 178 00:13:08,470 --> 00:13:10,870 So, you know, the height was one to three. 179 00:13:11,320 --> 00:13:18,160 We're only going to perform the rotation on these three nodes here. 180 00:13:18,460 --> 00:13:23,860 We're not going to do anything with this fourth, as far as the type of rotation we're doing and the 181 00:13:23,860 --> 00:13:25,620 movements we're doing. 182 00:13:25,630 --> 00:13:33,640 So just keep that in mind, like the turns are, you know, two pointers because we're going to be rotating 183 00:13:33,910 --> 00:13:34,870 three nodes there. 184 00:13:36,480 --> 00:13:38,490 So let's see how we would do this. 185 00:13:38,730 --> 00:13:43,290 So just like our left left examples we've gone through before. 186 00:13:43,440 --> 00:13:49,140 What we're going to do is we're actually going to take our tin up here and we're going to bring it down 187 00:13:49,650 --> 00:13:53,310 as the right cemetery of eight. 188 00:13:54,440 --> 00:14:05,180 But there is an issue, and that is that we have this 9:00 right here is already there. 189 00:14:05,420 --> 00:14:09,520 So this already has a right century. 190 00:14:09,530 --> 00:14:12,950 So what are we going to do with that? 191 00:14:13,950 --> 00:14:19,830 Well, since it is part of this sub tree, we're actually going to just be able to connect it. 192 00:14:20,250 --> 00:14:21,990 So let's go ahead and look at that. 193 00:14:21,990 --> 00:14:25,020 Let's move the nine out of the way for a second. 194 00:14:27,260 --> 00:14:34,520 We bring the tin down, and since nine was part of that left some tree initially. 195 00:14:34,850 --> 00:14:36,020 So let's go back here. 196 00:14:37,710 --> 00:14:47,730 Nine was on the in the last century of 10, when we break 10 of 10 has a right century here that we're 197 00:14:47,730 --> 00:14:50,040 leaving on there 18. 198 00:14:50,460 --> 00:14:56,040 But when we detach this from the eight, this point right here, it's just doesn't really have anything 199 00:14:56,040 --> 00:14:57,010 that it's pointing to. 200 00:14:57,030 --> 00:15:02,040 So what we're going to do when we bring this down here, we're going to have this left pointer point 201 00:15:02,040 --> 00:15:04,620 to this sub tree right here. 202 00:15:05,430 --> 00:15:06,330 So that's what we do. 203 00:15:06,330 --> 00:15:07,620 We move the ten down here. 204 00:15:08,370 --> 00:15:13,830 The ten is right here and then we connect the nine to this 10 right here. 205 00:15:14,980 --> 00:15:22,030 And then we have a tree that no longer has any problems if you calculate the balance factors again. 206 00:15:23,050 --> 00:15:26,980 You will see that this tree is no longer problematic. 207 00:15:27,430 --> 00:15:30,730 So that was a left left rotation. 208 00:15:32,240 --> 00:15:36,230 So now we're going to look in a bigger example of a right right rotation. 209 00:15:36,560 --> 00:15:40,100 So let's go ahead and check that out. 210 00:15:40,160 --> 00:15:41,720 So what will this look like? 211 00:15:43,020 --> 00:15:47,490 We'll start with our balance factors, so zero zero. 212 00:15:48,790 --> 00:15:50,410 Zero for this one minus one. 213 00:15:51,980 --> 00:15:54,080 It's go out of this leaf that zero. 214 00:15:55,280 --> 00:15:56,510 This is here as well. 215 00:15:56,840 --> 00:16:01,160 This is serious, well, this is minus one because zero minus one. 216 00:16:02,200 --> 00:16:03,890 This is one one minus zero. 217 00:16:04,900 --> 00:16:06,700 This is one minus one to. 218 00:16:07,950 --> 00:16:10,800 This is one two minus one to three. 219 00:16:12,140 --> 00:16:16,670 But this is problematic because it's one to minus one to three four. 220 00:16:16,790 --> 00:16:24,350 So this is going to be an interesting one because we're actually rotating with the note on a pretty 221 00:16:24,350 --> 00:16:25,280 big tree here, so. 222 00:16:26,500 --> 00:16:28,240 Let's go ahead and walk through it. 223 00:16:29,440 --> 00:16:37,450 So this is a right, right, because if we're going down the direction that you know, the larger hype 224 00:16:37,630 --> 00:16:42,190 that caused this imbalance, we would take a right and a right. 225 00:16:43,160 --> 00:16:45,050 So remember, we're talking about those three notes. 226 00:16:45,100 --> 00:16:47,810 That's why we're just doing right and right for this right, right? 227 00:16:47,860 --> 00:16:51,390 Location rotation and thinking about these three a.m. 228 00:16:51,920 --> 00:16:56,050 This note up here is actually going to come down just like we talked about before. 229 00:16:56,060 --> 00:16:58,550 We're going to bring it down and it's going to be right here. 230 00:16:58,560 --> 00:17:03,650 But once again, we have this sub tree right here that we're going to need to connect to. 231 00:17:03,650 --> 00:17:04,850 So let's take a look. 232 00:17:06,040 --> 00:17:12,760 So things kind of moved out of the way, but what I did there was I took the 10 and I moved it over 233 00:17:12,760 --> 00:17:13,150 here. 234 00:17:14,170 --> 00:17:19,410 So we started like this and I took this and I moved out here so we could look at this section. 235 00:17:19,690 --> 00:17:22,060 So that's what we're doing. 236 00:17:22,660 --> 00:17:28,180 I still have the place we were going to want to put the 10 with this arrow here, but we're going to 237 00:17:28,180 --> 00:17:30,280 need to think about this one. 238 00:17:30,340 --> 00:17:32,710 So what do you think is going to happen with this 12? 239 00:17:33,460 --> 00:17:38,170 Or if we think back to the previous example of left left and we're just thinking about it, the inverse 240 00:17:38,170 --> 00:17:39,010 situation here. 241 00:17:39,430 --> 00:17:42,910 We broke the tin off and it has this sub tree over here connected. 242 00:17:42,910 --> 00:17:44,800 But now it has nothing connected here. 243 00:17:45,580 --> 00:17:53,590 So just like the last time, we're going to take this and fill that void with this sub tree here since 244 00:17:53,590 --> 00:17:55,060 we need to move the tender to here. 245 00:17:56,510 --> 00:18:01,700 And that's what we will do, so now we put 10 in the place that we needed to. 246 00:18:02,360 --> 00:18:08,090 We brought it down here and then the fact that it had this kind of empty pointer here that was previously 247 00:18:08,090 --> 00:18:11,300 pointing to something we're going to take this country. 248 00:18:12,390 --> 00:18:17,420 That was the one that was right here, and we're going to attach it to this right. 249 00:18:17,430 --> 00:18:18,690 So three of the 10. 250 00:18:23,230 --> 00:18:26,840 OK, so now we have a balanced view. 251 00:18:27,850 --> 00:18:31,000 And brought it up here just to make it look a little bit better. 252 00:18:32,620 --> 00:18:35,350 Now let's look at left, right and a bigger example. 253 00:18:36,630 --> 00:18:38,190 So we have zero. 254 00:18:38,790 --> 00:18:43,830 We have one here, zero kindness going randomly now to fill these balance factors. 255 00:18:44,370 --> 00:18:49,050 But you can do all the Leafs first and do it level by level if you wanted. 256 00:18:50,650 --> 00:18:52,180 We have zero here. 257 00:18:52,240 --> 00:18:58,480 You kind of want to count up from the bottom, though that is an important point because you want to 258 00:18:58,480 --> 00:19:03,550 if you encounter a balance factor somewhere here in this sub tree, you'll want to do a rotation on 259 00:19:03,550 --> 00:19:04,120 that first. 260 00:19:04,120 --> 00:19:10,120 You want like, you know, if you when you encounter a problematic balance factor like down here, like 261 00:19:10,120 --> 00:19:13,390 you would do that rotation without necessarily thinking about. 262 00:19:14,320 --> 00:19:17,390 The bigger ones, you know, you're rotating it in that type of way. 263 00:19:19,410 --> 00:19:23,100 So we have minus one here, this is one minus two. 264 00:19:24,500 --> 00:19:28,130 One to one to three, that's minus one zero. 265 00:19:28,260 --> 00:19:32,510 That's a leaf of zero because it's a leaf zero, because it's one on one. 266 00:19:33,300 --> 00:19:39,410 Then this is two because we have one two three and then we have one to. 267 00:19:41,260 --> 00:19:48,940 So actually, that's not three one to three four is the maximum, and then we have one two, so four 268 00:19:48,940 --> 00:19:50,470 minus two gives us two. 269 00:19:53,160 --> 00:20:00,150 So remember back to the left right rotation, we're doing left right because this was the direction 270 00:20:00,150 --> 00:20:05,050 that had for that threw off the balance factor, and I did not tell her that read apologies for that. 271 00:20:05,070 --> 00:20:10,390 I would only just have this read because it is the violating balance factor. 272 00:20:10,410 --> 00:20:11,220 The violating, no. 273 00:20:12,420 --> 00:20:13,200 So just for 10 minutes. 274 00:20:13,200 --> 00:20:14,310 Read my apologies. 275 00:20:16,010 --> 00:20:22,160 We're going to take this further left right rotation because it was the direction of the violating hate 276 00:20:22,160 --> 00:20:23,030 that caused the problem. 277 00:20:24,020 --> 00:20:25,340 And we're going to take this A.. 278 00:20:25,370 --> 00:20:29,720 Move it up between these for the first step, so we'll have 10, 12 and 18. 279 00:20:31,470 --> 00:20:36,840 And then we're going to take this and move it down here, this 18 will come down here. 280 00:20:38,280 --> 00:20:41,760 So that is how we're going to perform this rotation. 281 00:20:44,450 --> 00:20:46,760 So let's look at what we did right here. 282 00:20:47,540 --> 00:20:49,220 We have the 18 and the 10. 283 00:20:49,520 --> 00:20:52,340 We kind of broke it apart because we're going to move the 12 in here. 284 00:20:53,150 --> 00:20:59,660 So we have this section in this section that took this section right here and this section right here 285 00:21:01,010 --> 00:21:02,170 and split them apart. 286 00:21:02,180 --> 00:21:04,880 And then we have this coming up here. 287 00:21:06,110 --> 00:21:06,500 So. 288 00:21:09,500 --> 00:21:15,740 We initially moved the 10 to this, because if we think about it, we're moving, we've brought this 289 00:21:15,740 --> 00:21:20,240 tent away and we're moving this 12, that's leaving this thing hanging. 290 00:21:20,960 --> 00:21:24,080 So we're going to need to connect this 11 to it. 291 00:21:25,800 --> 00:21:26,940 So that's why we did that. 292 00:21:28,020 --> 00:21:34,180 And so now we have this point where we're connecting the 12 to here and 18 to the 12. 293 00:21:34,650 --> 00:21:41,250 So the 11 was initially on the 12, but now it's going off to the 10 because we lost attending in there. 294 00:21:43,470 --> 00:21:46,410 And so that's what it looks like, completed after the first step. 295 00:21:47,590 --> 00:21:50,560 The next thing is to bring this. 296 00:21:51,680 --> 00:22:00,650 Eighteen up here, down below the 12, so this is basically another left left rotation to the second 297 00:22:00,650 --> 00:22:05,300 part of it is basically the same as the left left rotation, just like we talked about before. 298 00:22:08,020 --> 00:22:10,820 So to do that, things like shifting a little bit here. 299 00:22:10,900 --> 00:22:15,970 But let's look, let's look back at that took the 18 and just moved it down here. 300 00:22:16,900 --> 00:22:22,330 So this whole 18 century got moved down when you need to put it right here. 301 00:22:22,690 --> 00:22:25,990 So this got left hanging here after 18. 302 00:22:26,710 --> 00:22:32,470 So that's why we're going to take this sub tree, which is the area we want to move the 18 to and we're 303 00:22:32,470 --> 00:22:35,830 going to attach it to the left sub tree of the 18. 304 00:22:37,960 --> 00:22:43,120 So that's what we do, we attach this and we end up with a tree like this. 305 00:22:43,690 --> 00:22:48,730 So our balance factors are no longer an issue in this tree. 306 00:22:51,010 --> 00:22:53,980 All right, now, let's look at a right left example. 307 00:22:55,810 --> 00:22:58,270 So let's do our balance factors. 308 00:22:58,810 --> 00:23:02,470 We have zero one zero. 309 00:23:03,520 --> 00:23:04,240 One here. 310 00:23:04,480 --> 00:23:11,860 One two one two one zero zero zero one one. 311 00:23:12,580 --> 00:23:20,500 And then right here we have a problem because it's one and then we have a one to three. 312 00:23:21,450 --> 00:23:27,930 So one minus three is negative two, so I think this balance factor up there, but this is the one that 313 00:23:27,930 --> 00:23:34,670 is problematic right now because as the balance factor that is the absolute value is greater than one. 314 00:23:34,680 --> 00:23:35,070 So. 315 00:23:36,440 --> 00:23:43,310 We have right left for this rotation because we're going down to the height that was the offender, 316 00:23:43,320 --> 00:23:46,280 so what we're going to do is move this note up. 317 00:23:47,030 --> 00:23:48,650 So think about the last example we have. 318 00:23:48,650 --> 00:23:50,390 This is basically the inverse of that. 319 00:23:51,200 --> 00:23:56,060 We're taking this note right here or moving it up between this 18 and this 26. 320 00:23:57,470 --> 00:24:05,180 And then the next thing we'll do is we will move the 18 down to here, so into this spot right here 321 00:24:05,930 --> 00:24:07,010 where this 25 was. 322 00:24:08,600 --> 00:24:09,470 So let's do that. 323 00:24:09,470 --> 00:24:14,360 We break these apart right here and we move to 25 in between. 324 00:24:17,090 --> 00:24:18,440 So we have those right there. 325 00:24:21,390 --> 00:24:25,500 And we connected those, and now we need to move the 18 down to here. 326 00:24:26,070 --> 00:24:29,640 So we're going to do that and move the 18 down to here. 327 00:24:31,330 --> 00:24:38,260 And then that 23 is going to connect because of we move, the 18, 20 three was connected to this 25, 328 00:24:38,260 --> 00:24:41,050 but only move the 18 is left hanging right here. 329 00:24:42,000 --> 00:24:45,150 And so now we're going to take that twenty three and connect it to here. 330 00:24:46,690 --> 00:24:53,790 Another way to think of it is that twenty three was part of 18th right century, and since we need to 331 00:24:53,790 --> 00:25:00,450 move 18 to this spot and push twenty three out of the way, we will still keep it as the right cemetery. 332 00:25:01,380 --> 00:25:03,990 So that's why we put it here on the right cemetery. 333 00:25:06,250 --> 00:25:09,100 OK, and now we can just connect this whole thing back up. 334 00:25:09,280 --> 00:25:15,220 And we have a balanced three, you know, balance enough, not violated any more. 335 00:25:17,320 --> 00:25:22,720 OK, so hopefully that explained all of the rotations. 336 00:25:23,440 --> 00:25:29,080 I might try and include some links to some visualizations and animations you can look at online. 337 00:25:29,110 --> 00:25:31,240 It's really just kind of practicing these. 338 00:25:31,570 --> 00:25:39,760 She go through insert a bunch of values into a binary search tree with examples and just draw it out 339 00:25:39,760 --> 00:25:45,240 on paper or something like that is probably the easiest and make the rotations as you're inserting. 340 00:25:45,250 --> 00:25:50,890 So each time you insert a new node, recalculate all the balance factors from the bottom up. 341 00:25:51,880 --> 00:25:59,410 And then basically the second you have a violating node that you notice like you should definitely go 342 00:25:59,410 --> 00:26:04,460 through and perform a rotation on that before you insert anything else. 343 00:26:04,480 --> 00:26:08,230 So you can maintain the balance tree throughout the insertion process. 344 00:26:09,490 --> 00:26:10,030 OK. 345 00:26:10,360 --> 00:26:16,300 So with that, I'll see you in the next lecture and we'll be looking at how to write some code to implement 346 00:26:16,300 --> 00:26:16,630 this.