WEBVTT 1 00:00:00.080 --> 00:00:01.270 Hi, and welcome back. 2 00:00:01.270 --> 00:00:04.120 Let's look at deleting nodes from a binary tree 3 00:00:04.120 --> 00:00:05.963 when they have two children. 4 00:00:07.120 --> 00:00:10.750 So when the to_delete node has two children, 5 00:00:10.750 --> 00:00:14.350 we must do something a bit special. 6 00:00:14.350 --> 00:00:16.543 Let me bring up my diagram once again. 7 00:00:17.440 --> 00:00:20.190 We've looked at this before, just a quick recap. 8 00:00:20.190 --> 00:00:22.663 Let's say we want to delete the node nine. 9 00:00:23.690 --> 00:00:24.780 What we must do 10 00:00:24.780 --> 00:00:29.720 is find the rightmost node in the left branch, 11 00:00:29.720 --> 00:00:32.500 so eight, or, if you prefer, 12 00:00:32.500 --> 00:00:36.190 the leftmost node in the right branch, 11. 13 00:00:36.190 --> 00:00:38.929 Because we've coded a find_rightmost, 14 00:00:38.929 --> 00:00:40.130 we're gonna stick to that. 15 00:00:40.130 --> 00:00:42.530 We're gonna use eight, in this case, 16 00:00:42.530 --> 00:00:44.300 but you can use 11 if you prefer, 17 00:00:44.300 --> 00:00:48.063 so we're gonna find the rightmost node in the left branch. 18 00:00:48.940 --> 00:00:52.440 We will also need its parent, 19 00:00:52.440 --> 00:00:56.123 because the parent will have to point to the children. 20 00:00:58.090 --> 00:00:59.773 Something that we know, 21 00:01:00.810 --> 00:01:04.580 is that the rightmost node in this branch 22 00:01:04.580 --> 00:01:06.323 has nothing to its right. 23 00:01:07.730 --> 00:01:08.960 Hopefully that makes sense. 24 00:01:08.960 --> 00:01:11.140 The rightmost node in this branch 25 00:01:11.140 --> 00:01:13.060 doesn't have anything to its right, 26 00:01:13.060 --> 00:01:16.630 because if it did, that would be the rightmost. 27 00:01:16.630 --> 00:01:19.610 So when you go as far right as you can, 28 00:01:19.610 --> 00:01:23.693 this node has either zero or one children, 29 00:01:24.650 --> 00:01:25.613 not two. 30 00:01:27.629 --> 00:01:32.600 So that is important because as part of deleting nine, 31 00:01:32.600 --> 00:01:35.210 we are going to have to delete eight, essentially. 32 00:01:35.210 --> 00:01:37.033 We're going to move eight up here, 33 00:01:38.170 --> 00:01:41.540 which means that seven has to point down here 34 00:01:44.540 --> 00:01:45.890 like that. 35 00:01:45.890 --> 00:01:47.600 So essentially we have deleted eight, 36 00:01:47.600 --> 00:01:49.070 and if eight had two children 37 00:01:49.070 --> 00:01:51.660 this would get extremely complicated 38 00:01:51.660 --> 00:01:53.680 because we'd be deleting a node of two children 39 00:01:53.680 --> 00:01:55.600 by deleting another node of two children, 40 00:01:55.600 --> 00:01:57.360 this is quite simple. 41 00:01:57.360 --> 00:02:01.100 If 7.5 had other children, this would be fine, 42 00:02:01.100 --> 00:02:02.853 'cause seven points to 7.5, 43 00:02:02.853 --> 00:02:05.303 7.5's children stay there, so that's okay. 44 00:02:08.314 --> 00:02:12.860 And of course, if eight has no children, then that's fine. 45 00:02:12.860 --> 00:02:16.280 We don't have to worry about it, so no problem. 46 00:02:16.280 --> 00:02:18.270 Let's start with this scenario, 47 00:02:18.270 --> 00:02:21.270 the scenario where we want to delete, say nine, 48 00:02:21.270 --> 00:02:24.660 and that has a node in this structure here. 49 00:02:24.660 --> 00:02:26.260 So the first thing we have to do 50 00:02:27.500 --> 00:02:30.860 is see whether the node we want to delete 51 00:02:30.860 --> 00:02:33.663 is at the left or at the right of its parent. 52 00:02:35.410 --> 00:02:37.560 So if to_delete 53 00:02:37.560 --> 00:02:42.060 equal to_delete_parent.left, let's say, 54 00:02:42.060 --> 00:02:44.010 I'm gonna delete this pass, by the way, 55 00:02:45.803 --> 00:02:48.743 elif to_delete is equal to to_delete_parent.right, 56 00:02:51.211 --> 00:02:52.190 and of course else, 57 00:02:52.190 --> 00:02:53.230 what happens when they're the same, 58 00:02:53.230 --> 00:02:55.980 when you wanna delete the root and it has two children. 59 00:02:58.290 --> 00:03:00.130 Now, for all of these we're going to need 60 00:03:00.130 --> 00:03:03.940 the rightmost node in the left branch, 61 00:03:03.940 --> 00:03:06.430 so we're gonna say rightmost 62 00:03:06.430 --> 00:03:09.580 equal self.find_rightmost 63 00:03:11.215 --> 00:03:12.715 of to_delete.left, 64 00:03:16.540 --> 00:03:18.650 and rightmost parent 65 00:03:18.650 --> 00:03:20.200 is going to be self.find_parent 66 00:03:21.730 --> 00:03:26.023 of the rightmost.value. 67 00:03:27.800 --> 00:03:29.707 Once again, find_parent, 68 00:03:30.750 --> 00:03:34.200 which is up here, takes in a value, 69 00:03:34.200 --> 00:03:35.530 and sort of goes through the tree, 70 00:03:35.530 --> 00:03:37.760 and tells us what the parent is 71 00:03:37.760 --> 00:03:39.503 of the value we're looking for. 72 00:03:40.370 --> 00:03:43.660 So here we've got the rightmost node in the left branch, 73 00:03:43.660 --> 00:03:47.610 and we've also got the rightmost_parent of that node. 74 00:03:47.610 --> 00:03:50.400 We know that it is a rightmost node 75 00:03:51.340 --> 00:03:55.720 because that is a left branch. 76 00:03:55.720 --> 00:03:57.400 To delete left, return true, 77 00:03:57.400 --> 00:03:58.880 or it wasn't none, 78 00:03:58.880 --> 00:04:01.940 so we know that this is not going to be none, 79 00:04:01.940 --> 00:04:03.040 so therefore this is fine. 80 00:04:03.040 --> 00:04:04.410 Accessing rightmost.value like that, 81 00:04:04.410 --> 00:04:07.360 without checking or without catching any exceptions is okay, 82 00:04:07.360 --> 00:04:10.440 because rightmost.value will return something. 83 00:04:10.440 --> 00:04:12.540 We know that because we have two children. 84 00:04:15.180 --> 00:04:19.050 Now, if we wanna delete something on the left, 85 00:04:19.050 --> 00:04:20.770 what do we have to do? 86 00:04:20.770 --> 00:04:22.820 Let's go back to the diagram. 87 00:04:22.820 --> 00:04:25.190 Let's say we want to delete 88 00:04:25.190 --> 00:04:26.240 Well, let's start with the right one. 89 00:04:26.240 --> 00:04:27.790 Let's say we wanna delete nine. 90 00:04:27.790 --> 00:04:32.790 So the first thing we have to do is find out eight, 91 00:04:33.180 --> 00:04:36.490 which we've done that, we've done the rightmost node. 92 00:04:36.490 --> 00:04:37.520 Then we have to say, 93 00:04:37.520 --> 00:04:40.800 the rightmost node's right 94 00:04:40.800 --> 00:04:44.650 now has to be equal to 12, right? 95 00:04:44.650 --> 00:04:47.350 If eight is going to replace nine, 96 00:04:47.350 --> 00:04:51.443 eight's right must be what used to be nine's right. 97 00:04:52.710 --> 00:04:53.810 Let's start with that. 98 00:04:54.862 --> 00:04:59.097 Rightmost.right has to be equal to to_delete.right, 99 00:05:02.060 --> 00:05:05.030 so that means that the rightmost node here, eight, 100 00:05:05.030 --> 00:05:07.803 is going to replace nine by pointing at 12. 101 00:05:10.570 --> 00:05:15.520 The to_delete's parent now no longer has to point at nine. 102 00:05:15.520 --> 00:05:17.320 It has to point at eight. 103 00:05:17.320 --> 00:05:21.810 So to_delete's parent has to point to the rightmost node. 104 00:05:21.810 --> 00:05:22.920 Let's do that. 105 00:05:22.920 --> 00:05:27.147 To_delete_parent.right equal rightmost. 106 00:05:28.310 --> 00:05:31.030 And by the way, I apologise profusely. 107 00:05:31.030 --> 00:05:34.480 We said we were gonna do the right first, so that's there. 108 00:05:34.480 --> 00:05:38.880 If you wanted to do the left, it would be exactly the same, 109 00:05:38.880 --> 00:05:40.380 but this would be in the left. 110 00:05:42.710 --> 00:05:46.440 So we found that the rightmost node's right 111 00:05:46.440 --> 00:05:49.360 must point to what used to be the to_delete's right, 112 00:05:49.360 --> 00:05:50.860 so eight is gonna point to 12. 113 00:05:51.846 --> 00:05:55.350 To_delete_parent.right has to point to eight 114 00:05:55.350 --> 00:05:59.160 because to_delete is equal to to_delete's right, 115 00:05:59.160 --> 00:06:00.600 so we're deleting nine, 116 00:06:00.600 --> 00:06:03.370 therefore the parent's right has to point somewhere else. 117 00:06:03.370 --> 00:06:07.670 If we had another two-child node here on the left, 118 00:06:07.670 --> 00:06:09.160 it would be this left, 119 00:06:09.160 --> 00:06:10.920 that has to point somewhere else, 120 00:06:10.920 --> 00:06:12.513 so that is what this is doing. 121 00:06:14.960 --> 00:06:16.310 Hopefully that makes sense. 122 00:06:18.070 --> 00:06:22.760 Finally, if we are deleting this one, 123 00:06:22.760 --> 00:06:24.490 if we are deleting the head, 124 00:06:24.490 --> 00:06:26.350 we're gonna find the rightmost node, again, 125 00:06:26.350 --> 00:06:28.990 in the left subtree, which is gonna be five, 126 00:06:28.990 --> 00:06:30.740 and what we have to do is say 127 00:06:30.740 --> 00:06:34.620 the rightmost node right must be nine, 128 00:06:34.620 --> 00:06:38.163 which is, again, this line here, 129 00:06:39.670 --> 00:06:43.290 but now, to_delete_parent equals rightmost, 130 00:06:43.290 --> 00:06:45.700 this is sort of correct, 131 00:06:45.700 --> 00:06:47.400 but to_delete_parent is to_delete, 132 00:06:49.300 --> 00:06:51.520 so it's the same node because they're both the head, 133 00:06:51.520 --> 00:06:54.657 so what we'll do is self.head is rightmost. 134 00:06:59.460 --> 00:07:01.620 So if we wanna delete this one, 135 00:07:01.620 --> 00:07:04.973 the head must become the rightmost node. 136 00:07:06.210 --> 00:07:08.940 That's the five, so the five would move up to here. 137 00:07:08.940 --> 00:07:11.363 Hopefully this makes a little bit of sense. 138 00:07:12.410 --> 00:07:14.470 There is, however, 139 00:07:14.470 --> 00:07:16.833 one more thing that we have to think about. 140 00:07:18.010 --> 00:07:20.460 Let's run, again, through our algorithm 141 00:07:20.460 --> 00:07:22.240 for deleting the nodes. 142 00:07:22.240 --> 00:07:24.460 Notice how we've not used the rightmost parent, by the way. 143 00:07:24.460 --> 00:07:25.883 That's really the problem. 144 00:07:27.440 --> 00:07:29.573 Let's imagine we're trying to delete nine. 145 00:07:30.690 --> 00:07:35.123 So to_delete is the parent's right, so this is correct. 146 00:07:36.130 --> 00:07:37.100 The first thing we're doing is 147 00:07:37.100 --> 00:07:38.190 we're finding the rightmost node 148 00:07:38.190 --> 00:07:41.450 and setting its right to be the to_delete.right, 149 00:07:41.450 --> 00:07:46.233 so essentially moving this 12 down to the eight, like that. 150 00:07:47.306 --> 00:07:49.760 This is correct: if we wanna move the eight up here, 151 00:07:49.760 --> 00:07:51.010 that's what it has to do. 152 00:07:52.030 --> 00:07:56.510 Then we're setting the parent to_delete_parent.right 153 00:07:56.510 --> 00:07:58.423 to be the rightmost node, 154 00:07:59.950 --> 00:08:00.783 and as you can see, 155 00:08:00.783 --> 00:08:03.010 there is something that's a little bit off, 156 00:08:03.010 --> 00:08:05.120 which is that we've deleted the nine, 157 00:08:05.120 --> 00:08:07.540 but we've also deleted the seven, 158 00:08:07.540 --> 00:08:10.103 'cause nothing's pointing to the seven. 159 00:08:11.160 --> 00:08:12.770 So we have to fix this. 160 00:08:12.770 --> 00:08:15.800 What we have to do is say, 161 00:08:15.800 --> 00:08:19.463 eight left must point to seven. 162 00:08:20.749 --> 00:08:24.540 Seven's right must point to eight's left. 163 00:08:27.870 --> 00:08:30.250 So what we have to do is 164 00:08:30.250 --> 00:08:31.423 rightmost_parent.right equals rightmost.left, 165 00:08:35.661 --> 00:08:39.411 and then rightmost.left equal to_delete.left. 166 00:08:43.640 --> 00:08:44.880 Now once again, we're gonna go through this algorithm. 167 00:08:44.880 --> 00:08:47.960 We're gonna change the others in just a moment. 168 00:08:47.960 --> 00:08:48.793 The first thing we're doing 169 00:08:48.793 --> 00:08:51.773 is setting rightmost_parent's right, so that's this guy, 170 00:08:52.900 --> 00:08:54.870 equal to rightmost's left 171 00:08:54.870 --> 00:08:58.060 Oh sorry, rightmost_parent is this guy, seven. 172 00:08:58.060 --> 00:09:00.800 Seven's right is gonna be, now, 7.5. 173 00:09:04.745 --> 00:09:08.940 The rightmost.left is now gonna be to_delete's left, 174 00:09:08.940 --> 00:09:11.120 so seven, so the eight 175 00:09:12.900 --> 00:09:15.023 is now going to point to seven. 176 00:09:17.190 --> 00:09:19.960 The rightmost's right 177 00:09:19.960 --> 00:09:22.993 is going to point to to_delete's right, 178 00:09:26.240 --> 00:09:28.020 and to_delete_parent's right 179 00:09:28.020 --> 00:09:30.913 is going to point to the rightmost node. 180 00:09:32.140 --> 00:09:33.640 Now, as you can see, this is a bit convoluted. 181 00:09:33.640 --> 00:09:34.670 I'm just gonna move it in a moment. 182 00:09:34.670 --> 00:09:35.710 It's gonna make sense. 183 00:09:35.710 --> 00:09:38.930 Nothing is pointing to nine, so we can delete it. 184 00:09:38.930 --> 00:09:40.350 These arrows we can delete. 185 00:09:40.350 --> 00:09:41.850 We can move the eight up here. 186 00:09:43.960 --> 00:09:45.680 Does that make sense? 187 00:09:45.680 --> 00:09:46.513 I hope so. 188 00:09:47.620 --> 00:09:51.810 So these four steps get us to this position. 189 00:09:51.810 --> 00:09:53.810 Of course this one is here to the right. 190 00:09:56.320 --> 00:09:57.680 I'm gonna undo these changes, 191 00:09:57.680 --> 00:09:59.680 just because we have, still, 192 00:09:59.680 --> 00:10:02.053 one more scenario to go through, unfortunately. 193 00:10:02.930 --> 00:10:05.620 I'm sorry: you did not see that. (laughs) 194 00:10:05.620 --> 00:10:07.740 This is for the next bit. 195 00:10:07.740 --> 00:10:10.590 And we also need these bits of code here 196 00:10:10.590 --> 00:10:13.253 in the other parts as well. 197 00:10:15.188 --> 00:10:17.293 So this is needed in all occasions. 198 00:10:20.910 --> 00:10:21.743 So 199 00:10:22.960 --> 00:10:25.880 we have one more scenario. 200 00:10:25.880 --> 00:10:27.123 Let me show it to you. 201 00:10:28.610 --> 00:10:30.690 We have this scenario here. 202 00:10:30.690 --> 00:10:32.750 So I'm gonna copy this, then I'm gonna do this, 203 00:10:32.750 --> 00:10:34.880 then I'm gonna delete it, and I'm gonna paste it in here. 204 00:10:34.880 --> 00:10:37.543 This is another scenario that we have to think about. 205 00:10:39.110 --> 00:10:40.070 What I'm going to do is 206 00:10:40.070 --> 00:10:42.460 I'm just going to modify it slightly. 207 00:10:42.460 --> 00:10:45.850 I'm going to add another node here, 208 00:10:45.850 --> 00:10:46.897 let's say 6.5, 209 00:10:49.754 --> 00:10:53.637 that's going to be to the left of seven, of course. 210 00:10:56.180 --> 00:10:57.993 So we have this scenario here. 211 00:10:59.340 --> 00:11:01.253 Nine is the node we want to delete. 212 00:11:03.030 --> 00:11:05.980 Seven is the rightmost node; it's got nothing to its right. 213 00:11:07.050 --> 00:11:08.970 Nine is also the rightmost parent 214 00:11:08.970 --> 00:11:10.840 because seven is the rightmost, 215 00:11:10.840 --> 00:11:12.320 therefore the parent is nine. 216 00:11:12.320 --> 00:11:14.820 Six is still to_delete_parent. 217 00:11:15.670 --> 00:11:19.123 Let's try to delete nine using our little algorithm. 218 00:11:20.180 --> 00:11:23.770 First, the rightmost_parent's right 219 00:11:23.770 --> 00:11:26.843 is going to be the rightmost's left. 220 00:11:28.900 --> 00:11:31.490 So this guy 221 00:11:31.490 --> 00:11:35.250 is going to point to 6.5. 222 00:11:35.250 --> 00:11:36.140 This is what we're doing here. 223 00:11:36.140 --> 00:11:40.790 Rightmost_parent, nine, is the rightmost's left, 6.5. 224 00:11:43.793 --> 00:11:48.503 Then we're saying rightmost.left is to_delete.left, 225 00:11:49.750 --> 00:11:53.330 which this makes very little sense 226 00:11:53.330 --> 00:11:56.613 because it is going to point to itself. 227 00:11:59.005 --> 00:12:00.847 Rightmost.right is to_delete.right. 228 00:12:03.740 --> 00:12:06.080 Okay, so finally something that makes a little bit of sense. 229 00:12:06.080 --> 00:12:06.913 This is okay. 230 00:12:06.913 --> 00:12:07.746 We wanna do that. 231 00:12:08.780 --> 00:12:11.927 Finally, to_delete_parent's right is the rightmost. 232 00:12:14.140 --> 00:12:15.230 Nothing points to nine. 233 00:12:15.230 --> 00:12:16.993 We get rid of all of them, 234 00:12:18.580 --> 00:12:21.360 but also we've accidentally deleted 6.5, 235 00:12:22.670 --> 00:12:26.270 and seven points to itself, which is not ideal either. 236 00:12:26.270 --> 00:12:29.483 We're gonna get into many infinite loops if we do that. 237 00:12:31.550 --> 00:12:35.790 We don't wanna do that, so how do we do this? 238 00:12:35.790 --> 00:12:37.360 Well, it's actually pretty simple. 239 00:12:37.360 --> 00:12:41.260 The whole problem in this scenario is that 240 00:12:41.260 --> 00:12:45.360 to_delete is equal to the rightmost_parent, 241 00:12:45.360 --> 00:12:47.870 and then we're sort of setting some properties 242 00:12:47.870 --> 00:12:50.020 that we have to move around 243 00:12:50.020 --> 00:12:53.593 from to_delete and rightmost_parent, like say these, 244 00:12:55.060 --> 00:12:59.413 that we just cannot do because they are the same thing. 245 00:13:00.830 --> 00:13:05.320 When they are the same thing, the only thing we have to do 246 00:13:06.410 --> 00:13:09.890 is get the rightmost's right node 247 00:13:09.890 --> 00:13:12.093 and make it 12, 248 00:13:13.586 --> 00:13:16.260 and get six and point it to seven. 249 00:13:16.260 --> 00:13:19.393 This is all we have to do when they are the same. 250 00:13:20.820 --> 00:13:22.563 Now, nothing points to nine, 251 00:13:23.620 --> 00:13:26.483 and seven becomes the one we wanted. 252 00:13:28.650 --> 00:13:30.370 So as you can see, 253 00:13:30.370 --> 00:13:31.760 maybe that was a bit too fast, 254 00:13:31.760 --> 00:13:33.610 all we have to do is rightmost.right, 255 00:13:34.580 --> 00:13:37.903 which is seven's right equal to_delete.right, 256 00:13:38.870 --> 00:13:43.220 and to_delete_parent's right is the rightmost. 257 00:13:43.220 --> 00:13:46.550 So we only want to do these two lines. 258 00:13:46.550 --> 00:13:50.693 That means we need these two for when they are not the same. 259 00:13:51.810 --> 00:13:53.420 So if 260 00:13:55.154 --> 00:13:56.487 rightmost_parent 261 00:13:59.510 --> 00:14:01.517 is not equal to to_delete, 262 00:14:02.580 --> 00:14:03.993 run these two lines. 263 00:14:07.374 --> 00:14:11.580 If rightmost_parent is not equal to to_delete, 264 00:14:11.580 --> 00:14:13.500 run those two lines, 265 00:14:13.500 --> 00:14:14.440 and down here, 266 00:14:14.440 --> 00:14:16.780 if rightmost_parent is not equal to to_delete, 267 00:14:16.780 --> 00:14:18.173 run those two lines. 268 00:14:19.930 --> 00:14:24.103 Notice how we've got our if statements here, 269 00:14:25.170 --> 00:14:27.700 and these blocks of code are always the same 270 00:14:27.700 --> 00:14:30.200 in all if statements, so we can just extract them. 271 00:14:31.520 --> 00:14:35.020 We can just remove them from the if statements there 272 00:14:35.020 --> 00:14:36.163 and move them up here. 273 00:14:38.660 --> 00:14:41.200 Similarly, rightmost.right is to_delete.right, 274 00:14:41.200 --> 00:14:44.913 this can also be extracted and put here, 275 00:14:50.600 --> 00:14:52.420 and this now becomes a little bit simpler. 276 00:14:52.420 --> 00:14:54.530 So once again, going back to our diagram, 277 00:14:54.530 --> 00:14:56.320 I'm gonna just delete 278 00:14:56.320 --> 00:14:58.450 or actually, let's not delete those clouds just yet. 279 00:14:58.450 --> 00:15:01.080 Let's say, once again, we wanna delete nine, 280 00:15:01.080 --> 00:15:03.850 so we've got our little algorithm. 281 00:15:03.850 --> 00:15:05.870 We find the rightmost node, which is seven. 282 00:15:05.870 --> 00:15:08.070 We find the rightmost_parent, which is nine. 283 00:15:09.590 --> 00:15:12.480 Is the node we wanna delete equal to the rightmost_parent? 284 00:15:12.480 --> 00:15:15.910 Yes, so we jump straight through this if statement 285 00:15:15.910 --> 00:15:16.950 and into here. 286 00:15:16.950 --> 00:15:19.330 The rightmost.right node, 287 00:15:19.330 --> 00:15:21.910 this one down here which doesn't exist yet, 288 00:15:21.910 --> 00:15:24.333 is going to be to_delete's right. 289 00:15:27.060 --> 00:15:31.150 Now, is to_delete the parent's right 290 00:15:31.150 --> 00:15:32.390 uh, left node? 291 00:15:32.390 --> 00:15:34.830 Is it the parent's right? 292 00:15:34.830 --> 00:15:35.940 Yes. 293 00:15:35.940 --> 00:15:37.893 So we point that there. 294 00:15:39.750 --> 00:15:40.700 That's all we need. 295 00:15:42.760 --> 00:15:47.353 Now, let's go back to having something like an eight here. 296 00:15:49.240 --> 00:15:51.870 Now, the rightmost node becomes the eight. 297 00:15:51.870 --> 00:15:54.223 The rightmost_parent becomes the seven. 298 00:15:55.239 --> 00:15:57.639 To_delete becomes nine, to_delete_parent is six. 299 00:15:58.650 --> 00:16:00.150 So this is our other scenario, 300 00:16:01.010 --> 00:16:04.010 and what we wanna do is, once again, we wanna delete nine, 301 00:16:04.010 --> 00:16:08.057 find eight, find seven as rightmost's rightmost_parent. 302 00:16:08.057 --> 00:16:11.080 Is rightmost_parent equal to to_delete? 303 00:16:11.080 --> 00:16:13.930 No, so we go into this if statement. 304 00:16:13.930 --> 00:16:15.030 Rightmost_parent.right 305 00:16:17.800 --> 00:16:21.510 must equal to the rightmost's left, 306 00:16:21.510 --> 00:16:22.343 and by the way, 307 00:16:23.506 --> 00:16:26.160 we'll just add this 7.5 back here. 308 00:16:27.562 --> 00:16:28.993 7.6, that's okay. 309 00:16:31.010 --> 00:16:32.980 So the rightmost_parent's right 310 00:16:32.980 --> 00:16:34.993 must equal the rightmost's left, 311 00:16:36.126 --> 00:16:38.600 so it has to point to 7.6. 312 00:16:38.600 --> 00:16:43.600 The rightmost's left must equal to_delete's left, 313 00:16:43.890 --> 00:16:48.053 so this eight here must now point to seven. 314 00:16:49.920 --> 00:16:53.200 The rightmost's right, this guy was the rightmost, 315 00:16:53.200 --> 00:16:57.623 the right must point to to_delete's right, so down here. 316 00:16:58.760 --> 00:17:02.430 And finally, because nine is at the right of the parent, 317 00:17:02.430 --> 00:17:05.340 six must point on the right to the rightmost node, 318 00:17:05.340 --> 00:17:06.173 which is eight. 319 00:17:07.250 --> 00:17:12.250 Then we can delete nine, move it up here, and we got it. 320 00:17:12.340 --> 00:17:13.840 We got exactly what we wanted. 321 00:17:15.780 --> 00:17:20.470 Now, this is an extreme mind-boggling algorithm, 322 00:17:20.470 --> 00:17:21.630 at least when you're starting, 323 00:17:21.630 --> 00:17:26.290 and I would not expect you to sort of grasp it immediately, 324 00:17:26.290 --> 00:17:29.433 and again, draw this out on paper. 325 00:17:30.280 --> 00:17:32.670 Don't feel bad for drawing it out. 326 00:17:32.670 --> 00:17:33.730 Everybody draws it out. 327 00:17:33.730 --> 00:17:35.510 I have many drawings of this stuff, 328 00:17:35.510 --> 00:17:37.570 and even with these diagrams 329 00:17:37.570 --> 00:17:42.570 I can see that it's not so obvious to understand, 330 00:17:42.980 --> 00:17:45.760 and especially when you have 100 lines of code 331 00:17:45.760 --> 00:17:49.070 well, not 100, but 50 lines of code 332 00:17:49.070 --> 00:17:52.500 to delete a node in a data structure, 333 00:17:52.500 --> 00:17:55.070 you know that it's pretty complicated. 334 00:17:55.070 --> 00:17:57.610 Hopefully this helps, though. 335 00:17:57.610 --> 00:17:59.370 It can pop up in interviews. 336 00:17:59.370 --> 00:18:01.500 It can pop up in coding challenges. 337 00:18:01.500 --> 00:18:03.690 It's sort of a good thing to know in general 338 00:18:03.690 --> 00:18:05.420 for when you're dealing with databases, 339 00:18:05.420 --> 00:18:08.000 and data that you have to search through very quickly 340 00:18:08.000 --> 00:18:09.050 and so forth, 341 00:18:09.050 --> 00:18:12.210 and generally, just knowing about binary trees, 342 00:18:12.210 --> 00:18:13.240 and that they exist, 343 00:18:13.240 --> 00:18:16.330 and a little bit of a notion on how to use them, 344 00:18:16.330 --> 00:18:19.310 is gonna make you a more well-rounded developer, 345 00:18:19.310 --> 00:18:23.480 but I've never had to use them in my day-to-day job. 346 00:18:23.480 --> 00:18:26.880 So understand it. 347 00:18:26.880 --> 00:18:28.010 Know it's there. 348 00:18:28.010 --> 00:18:29.020 Don't feel like 349 00:18:29.020 --> 00:18:31.570 you have to remember this algorithm line-by-line, 350 00:18:31.570 --> 00:18:32.547 'cause you don't have to, 351 00:18:32.547 --> 00:18:34.290 and you can always come back to the course 352 00:18:34.290 --> 00:18:36.340 and watch the video again if you need to. 353 00:18:37.740 --> 00:18:39.080 So that's it for this video. 354 00:18:39.080 --> 00:18:42.403 Hopefully this help, and I'll see on the next one.