WEBVTT 1 00:00:00.100 --> 00:00:01.300 Hi and welcome back 2 00:00:01.300 --> 00:00:03.000 in this video we are going to be recording 3 00:00:03.000 --> 00:00:04.970 our deletion of nodes. 4 00:00:06.430 --> 00:00:09.100 Before we do that though, we need 5 00:00:09.100 --> 00:00:11.400 a couple more helper methods. 6 00:00:12.440 --> 00:00:15.850 We need to be able to find the parent node 7 00:00:15.850 --> 00:00:18.870 of a given node and we also need to be 8 00:00:18.870 --> 00:00:22.610 able to find the rightmost node of a branch. 9 00:00:22.610 --> 00:00:24.160 So that we can then replace it. 10 00:00:25.370 --> 00:00:27.650 So let's code def find parent, 11 00:00:32.150 --> 00:00:34.560 which is going to take an int 12 00:00:36.450 --> 00:00:38.480 and is going to return a node. 13 00:00:40.750 --> 00:00:42.510 Let's code def find parent 14 00:00:42.510 --> 00:00:45.780 and also let's code def find rightmost. 15 00:00:47.766 --> 00:00:49.140 Now we're going to take a node 16 00:00:49.140 --> 00:00:50.370 and it's going to return another node 17 00:00:50.370 --> 00:00:52.430 so it's gonna take a node which is 18 00:00:52.430 --> 00:00:54.980 the start of the branch. 19 00:00:54.980 --> 00:00:57.210 So looking at this here, 20 00:00:58.850 --> 00:01:02.530 if we give it seven, find rightmost 21 00:01:02.530 --> 00:01:05.450 will give us eight, because that's the right most 22 00:01:05.450 --> 00:01:07.520 node in this entire branch. 23 00:01:09.250 --> 00:01:11.850 Find parent, if we give it seven, 24 00:01:11.850 --> 00:01:13.490 will give us this node. 25 00:01:14.532 --> 00:01:15.365 Okay? 26 00:01:17.480 --> 00:01:20.826 So let's code these two methods. 27 00:01:20.826 --> 00:01:23.180 What we're gonna do for find parent 28 00:01:23.180 --> 00:01:26.010 is just the same thing we did for find, 29 00:01:26.010 --> 00:01:27.700 I'm gonna open up here, 30 00:01:29.290 --> 00:01:30.800 go through all the nodes, 31 00:01:30.800 --> 00:01:33.680 but instead of checking whether the value we provided 32 00:01:33.680 --> 00:01:35.550 is equal to the current node value, 33 00:01:35.550 --> 00:01:37.310 we're gonna check the left and the right. 34 00:01:37.310 --> 00:01:40.630 So I'm gonna see if any of the children have this value 35 00:01:40.630 --> 00:01:43.180 and if they do we're gonna return the current node. 36 00:01:44.090 --> 00:01:46.400 So if I find parent I'm gonna say current node 37 00:01:46.400 --> 00:01:50.620 is self.head and then while current node is not empty 38 00:01:50.620 --> 00:01:54.820 we're gonna say if current node left exists 39 00:01:54.820 --> 00:01:58.830 and current node left.value is equal to the value 40 00:02:00.490 --> 00:02:05.490 or, and I'm gonna put this divide there because in Python 41 00:02:06.214 --> 00:02:09.340 that is useful for getting new lines, 42 00:02:09.340 --> 00:02:11.140 splitting things into new lines. 43 00:02:11.140 --> 00:02:15.410 Current node.right and current ndoe.right.value equal value. 44 00:02:17.460 --> 00:02:18.970 If you don't include this by the way 45 00:02:18.970 --> 00:02:21.720 it just gives you an error because it says, 46 00:02:21.720 --> 00:02:24.360 what does this mean, this is not part of the if statement, 47 00:02:24.360 --> 00:02:25.960 if you include this it realises that. 48 00:02:25.960 --> 00:02:28.560 What do you want us to split this statement here 49 00:02:28.560 --> 00:02:30.590 into two lines for readability. 50 00:02:30.590 --> 00:02:32.940 So that's why you include that backslash there. 51 00:02:34.150 --> 00:02:39.150 So if there is a left node and the value matches, 52 00:02:39.240 --> 00:02:42.400 or there is a right node and the value matches, 53 00:02:42.400 --> 00:02:44.140 that means we are the parent. 54 00:02:44.140 --> 00:02:46.100 Because one of the two children have 55 00:02:46.100 --> 00:02:47.700 the value we're looking for. 56 00:02:47.700 --> 00:02:52.327 So we return current node, and then we're gonna just do 57 00:02:53.470 --> 00:02:54.900 the same thing we did in the find. 58 00:02:54.900 --> 00:02:56.160 If the value that we're looking for 59 00:02:56.160 --> 00:02:58.050 is greater than the current node value, 60 00:02:58.050 --> 00:03:03.050 we're gonna say current node is current node right. 61 00:03:03.360 --> 00:03:07.130 And of course this has to be current node elif, 62 00:03:09.010 --> 00:03:13.240 the value is less than current node.value. 63 00:03:13.240 --> 00:03:16.190 We're gonna say current node equals current node.left. 64 00:03:18.090 --> 00:03:21.610 Now you may notice that at no point here 65 00:03:21.610 --> 00:03:23.390 are we returning the head. 66 00:03:24.730 --> 00:03:28.180 We start off at the head but we check the two children, 67 00:03:28.180 --> 00:03:33.180 and we return the head if the children have the value. 68 00:03:34.510 --> 00:03:37.670 We never return the head if the head has the value, 69 00:03:37.670 --> 00:03:40.460 or indeed there is no way that we will ever 70 00:03:42.220 --> 00:03:44.720 be able to delete the head with this. 71 00:03:45.660 --> 00:03:49.450 So what we're going to do is say if self.head 72 00:03:49.450 --> 00:03:54.420 and self.head.value equal value return self.head. 73 00:03:55.420 --> 00:03:58.540 The reason I'm doing this will become clearer as we 74 00:03:58.540 --> 00:04:01.620 continue and indeed as we are going to 75 00:04:01.620 --> 00:04:03.720 delete a node with two children, 76 00:04:03.720 --> 00:04:08.720 because if we are looking to delete the head, 77 00:04:10.480 --> 00:04:15.000 checking the children isn't going to give us the head. 78 00:04:15.000 --> 00:04:17.060 It's only going to give us the head if the children 79 00:04:17.060 --> 00:04:18.580 have the value we're looking for. 80 00:04:18.580 --> 00:04:21.510 Not if the head has the value we're looking for. 81 00:04:21.510 --> 00:04:23.570 It'll become clearer soon, I promise. 82 00:04:25.170 --> 00:04:27.750 Let's then move on to find rightmost. 83 00:04:27.750 --> 00:04:30.740 Find rightmost is a pretty straightforward method here. 84 00:04:30.740 --> 00:04:34.780 All that we have to do is starting at this node here 85 00:04:34.780 --> 00:04:38.660 go right until we reach the end. 86 00:04:39.990 --> 00:04:44.830 So all we do, is we say current node equals node, 87 00:04:44.830 --> 00:04:47.440 while current_node.right 88 00:04:47.440 --> 00:04:50.050 current_node equals current_node.right. 89 00:04:50.050 --> 00:04:52.450 And then at the end we will return current_node. 90 00:04:53.490 --> 00:04:56.420 So again all we're doing is we are saying, 91 00:04:56.420 --> 00:04:59.740 current_node will be it's right node until 92 00:04:59.740 --> 00:05:01.380 there is nothing at the right. 93 00:05:01.380 --> 00:05:03.230 And when there's nothing at the right, 94 00:05:03.230 --> 00:05:04.480 we'll just return the current node, 95 00:05:04.480 --> 00:05:06.800 because that is gonna be the right most node. 96 00:05:07.910 --> 00:05:11.360 Once again, I'll show you the diagram here. 97 00:05:11.360 --> 00:05:13.030 What we've got is, let's say we say 98 00:05:13.030 --> 00:05:15.110 find right most of this branch, 99 00:05:16.150 --> 00:05:19.820 what we'll do is we will start at seven, 100 00:05:20.890 --> 00:05:22.820 check the right most node, the right node 101 00:05:22.820 --> 00:05:25.360 and we say current_node is now eight 102 00:05:25.360 --> 00:05:27.590 and then we say is there another right node? 103 00:05:27.590 --> 00:05:30.160 No, so we'll return the eight. 104 00:05:30.160 --> 00:05:33.120 And that is indeed the largest node in the branch. 105 00:05:33.120 --> 00:05:35.410 It's never going to go left, because as soon 106 00:05:35.410 --> 00:05:38.670 as you go left you're no longer the largest node. 107 00:05:38.670 --> 00:05:40.230 So we'll just go right forever 108 00:05:40.230 --> 00:05:41.790 until we reach the end. 109 00:05:43.490 --> 00:05:45.117 Okay? 110 00:05:45.117 --> 00:05:48.340 Let's then get into the delete. 111 00:05:49.960 --> 00:05:51.480 We're gonna take a value. 112 00:05:51.480 --> 00:05:54.920 That is gonna be an integer, and is going to delete. 113 00:05:55.990 --> 00:05:58.130 What we have to take into consideration is that 114 00:05:58.130 --> 00:06:02.550 we may have no children, one child, or two children. 115 00:06:03.580 --> 00:06:07.100 So let's first get the to_delete which is gonna be 116 00:06:07.100 --> 00:06:11.292 self.find(value) and to_delete_parent which is gonna be 117 00:06:11.292 --> 00:06:14.130 self.find_parent(value) 118 00:06:14.130 --> 00:06:16.740 so now we have the one we wanna delete 119 00:06:16.740 --> 00:06:18.210 and the parent of that one. 120 00:06:19.640 --> 00:06:21.740 And then we have a couple of statements. 121 00:06:21.740 --> 00:06:25.870 If_to_detele.left and to_delete.right that means 122 00:06:25.870 --> 00:06:30.870 we have two children elif to_delete.left or to_delete.right 123 00:06:34.800 --> 00:06:38.130 we have one of the two that means we have one child, 124 00:06:39.760 --> 00:06:41.580 and finally no children. 125 00:06:44.010 --> 00:06:45.610 Okay? 126 00:06:45.610 --> 00:06:47.710 So these are our options. 127 00:06:47.710 --> 00:06:49.730 If we have two children we're gonna deal with 128 00:06:49.730 --> 00:06:53.050 deleting the node here, if we have one child 129 00:06:53.050 --> 00:06:54.770 we're going to deal with deleting the node here, 130 00:06:54.770 --> 00:06:57.200 and if we have no children we're gonna deal 131 00:06:57.200 --> 00:06:59.400 with deleting the node down there. 132 00:06:59.400 --> 00:07:02.500 Let's start with no children, you know how 133 00:07:02.500 --> 00:07:05.890 to do this already to some extent and once again 134 00:07:05.890 --> 00:07:08.860 I'll show you the diagram just to make it clear. 135 00:07:10.500 --> 00:07:14.340 Let's say we want to delete node three, okay. 136 00:07:14.340 --> 00:07:15.930 This node has no children. 137 00:07:16.790 --> 00:07:19.440 In order to delete node three, the first thing 138 00:07:19.440 --> 00:07:22.990 we have to know is whether node three is the left 139 00:07:22.990 --> 00:07:24.950 child or the right child. 140 00:07:25.810 --> 00:07:27.010 Why? 141 00:07:27.010 --> 00:07:29.580 Because what we're gonna do is we're gonna say five 142 00:07:30.790 --> 00:07:33.360 has a child which is three on the left. 143 00:07:34.790 --> 00:07:38.890 Let's make five left point to none instead of three. 144 00:07:40.240 --> 00:07:42.940 That means we essentially delete this link there 145 00:07:42.940 --> 00:07:44.940 and Python will delete the three for us. 146 00:07:46.200 --> 00:07:51.200 So if to_delete equals to_delete_parent.left 147 00:07:54.300 --> 00:07:57.120 we're gonna say to_delete_parent.left is none. 148 00:07:58.784 --> 00:08:02.910 Otherwise if to_delete is equal to to_delete_parent.right 149 00:08:05.827 --> 00:08:08.470 we're gonna say to_delete_parent.right is none. 150 00:08:09.820 --> 00:08:13.330 And there is a final option, which is now 151 00:08:13.330 --> 00:08:15.580 where the the other stuff we coded earlier becomes 152 00:08:15.580 --> 00:08:16.530 a bit more obvious. 153 00:08:17.840 --> 00:08:20.610 It could be the node we wanted to delete, 154 00:08:20.610 --> 00:08:23.720 and it's parent left are not the same. 155 00:08:25.030 --> 00:08:26.680 It could also be the node we wanna delete 156 00:08:26.680 --> 00:08:28.630 and it's parent right are not the same. 157 00:08:29.580 --> 00:08:30.720 When? 158 00:08:30.720 --> 00:08:32.110 Well let's have a look. 159 00:08:33.020 --> 00:08:35.070 Imagine you want to delete the root node. 160 00:08:37.890 --> 00:08:41.660 The root node is not it's parents' left or right 161 00:08:41.660 --> 00:08:43.060 because it doesn't have one. 162 00:08:44.310 --> 00:08:48.450 Indeed in this case to_delete and to_delete_parent 163 00:08:48.450 --> 00:08:49.390 will be the same. 164 00:08:50.450 --> 00:08:51.560 Why? 165 00:08:51.560 --> 00:08:55.040 Because to_delete is gonna find the root node, 166 00:08:55.040 --> 00:08:58.900 to_delete_parent is actually also going to give us 167 00:08:58.900 --> 00:09:02.500 the root node because we're looking for the head's value. 168 00:09:03.970 --> 00:09:05.750 So these two are going to be the same, 169 00:09:05.750 --> 00:09:08.420 these if statements are both going to be false, 170 00:09:08.420 --> 00:09:10.120 and this is where we'll end up at. 171 00:09:11.030 --> 00:09:13.290 The else where we want to delete the head 172 00:09:13.290 --> 00:09:16.360 all we have to do is self.head is none. 173 00:09:17.270 --> 00:09:20.850 Assuming of course the head has no children. 174 00:09:20.850 --> 00:09:23.730 This is what this else is doing. 175 00:09:23.730 --> 00:09:25.510 If the head has no children, 176 00:09:25.510 --> 00:09:28.570 that means the head is the last element in the tree. 177 00:09:28.570 --> 00:09:31.060 It means the head has no children it means this. 178 00:09:32.210 --> 00:09:35.630 So all we have to do is set it to none and then 179 00:09:35.630 --> 00:09:37.880 the six will get deleted by Python. 180 00:09:39.560 --> 00:09:40.393 okay? 181 00:09:41.430 --> 00:09:44.370 If we have a child it becomes a little bit different. 182 00:09:45.340 --> 00:09:48.070 Once again we have to do the same thing. 183 00:09:48.070 --> 00:09:52.680 If to_delete is equal to to_delete's parent left 184 00:09:52.680 --> 00:09:57.680 now we wanna say tdp left to_delete_parent.left 185 00:09:58.490 --> 00:10:01.360 is equal to, let's go back to our diagram. 186 00:10:01.360 --> 00:10:02.910 Let's say we wanna delete five, 187 00:10:04.420 --> 00:10:07.490 we have to say that the parent which is six, 188 00:10:07.490 --> 00:10:12.490 the parent's left must be equal to the child of five. 189 00:10:15.420 --> 00:10:18.670 The child of five could be at the left or it could be 190 00:10:18.670 --> 00:10:20.540 at the right, we don't know. 191 00:10:21.580 --> 00:10:22.820 So what to do? 192 00:10:22.820 --> 00:10:27.230 To_delete_parent.left is to_delete.right 193 00:10:27.230 --> 00:10:28.480 or to_delete.left. 194 00:10:32.770 --> 00:10:35.830 So again what we've done here is use the or syntax 195 00:10:35.830 --> 00:10:40.150 in Python to say that to_delete_parent.left has to be 196 00:10:40.150 --> 00:10:43.580 to_delete_parent.right but if it's none 197 00:10:43.580 --> 00:10:45.180 use to_delete.left instead. 198 00:10:46.970 --> 00:10:51.060 So that's a pretty handy way of going about it. 199 00:10:57.730 --> 00:11:00.280 Then again we do the same thing but with the right. 200 00:11:02.020 --> 00:11:05.010 Finally there's one last option, which is when 201 00:11:05.010 --> 00:11:08.010 to_delete_parent and to_delete are the same. 202 00:11:08.010 --> 00:11:10.940 If they are the same that means that self.head 203 00:11:10.940 --> 00:11:15.200 must become the right or the left nodes. 204 00:11:17.170 --> 00:11:20.318 In that way we will essentially be replacing one of them. 205 00:11:20.318 --> 00:11:25.010 What's happening here is of course, 206 00:11:25.010 --> 00:11:28.970 let me see if I can hide that, move that there, 207 00:11:28.970 --> 00:11:30.510 and show it to you like this. 208 00:11:30.510 --> 00:11:31.970 Yes, that is a little bit better. 209 00:11:31.970 --> 00:11:33.470 Assuming we have one child, which is 210 00:11:33.470 --> 00:11:36.513 for example this branch here, in this case 211 00:11:39.380 --> 00:11:42.793 if to_delete is the parent's left which it is 212 00:11:42.793 --> 00:11:45.779 in this case, what we want to do is set 213 00:11:45.779 --> 00:11:50.779 to_delete_parent which is six left node to be equal 214 00:11:51.960 --> 00:11:56.420 to this left node. 215 00:11:56.420 --> 00:11:57.253 Okay? 216 00:11:58.260 --> 00:12:00.390 Sorry, by that I mean, if this node 217 00:12:00.390 --> 00:12:02.130 is at the left of this one. 218 00:12:02.130 --> 00:12:04.250 If this one is at the left of this one we wanna set 219 00:12:04.250 --> 00:12:09.030 this left to be either the left or the right, 220 00:12:09.030 --> 00:12:10.830 depending on which one is available. 221 00:12:12.100 --> 00:12:13.330 Okay? 222 00:12:13.330 --> 00:12:16.232 If we wanted to delete say twelve, 223 00:12:16.232 --> 00:12:20.180 we'll check, is twelve the right child of nine? 224 00:12:20.180 --> 00:12:21.630 This would be done down here. 225 00:12:22.880 --> 00:12:26.780 Is twelve equal to to_delete_parent.right? 226 00:12:26.780 --> 00:12:28.040 Is it the same one? 227 00:12:28.040 --> 00:12:30.390 Is twelve equal to to_delete.parent.right? 228 00:12:30.390 --> 00:12:34.700 Yes, so we set to_delete_parent's right node 229 00:12:34.700 --> 00:12:38.830 to be equal to the left or the right of twelve. 230 00:12:38.830 --> 00:12:40.670 In this case it'll be eleven. 231 00:12:40.670 --> 00:12:43.190 Notice how we can do left or right, 232 00:12:43.190 --> 00:12:46.230 because we know that twelve only has one child. 233 00:12:46.230 --> 00:12:48.370 That's what this if statement here checks. 234 00:12:51.350 --> 00:12:54.400 And finally if you only have one of these branches and you 235 00:12:54.400 --> 00:12:59.400 want to delete the root or the head node, that means that 236 00:12:59.980 --> 00:13:02.260 to_delete and to_delete_parent are the same 237 00:13:02.260 --> 00:13:03.370 because they're both the head. 238 00:13:03.370 --> 00:13:05.830 And if that's the case all we wanna do 239 00:13:05.830 --> 00:13:10.830 is say the head is now five or whatever it was on the right. 240 00:13:11.020 --> 00:13:12.910 So we'll essentially be deleting six. 241 00:13:15.070 --> 00:13:17.390 Okay hopefully this makes a little bit of sense. 242 00:13:17.390 --> 00:13:22.390 It's really tricky when you start off to really 243 00:13:22.430 --> 00:13:23.785 wrap your head around this. 244 00:13:23.785 --> 00:13:26.450 So what I encourage you is to draw these out. 245 00:13:26.450 --> 00:13:27.930 Actually I have a lot of drawings of these 246 00:13:27.930 --> 00:13:30.480 mine maps... they're no mine maps but of these 247 00:13:30.480 --> 00:13:34.740 binary trees beside me as I was planning this section out 248 00:13:34.740 --> 00:13:36.540 because it didn't want to get it wrong. 249 00:13:36.540 --> 00:13:39.120 And it is confusing, it's confusing even after 250 00:13:39.120 --> 00:13:42.880 you've been at it for many years, so don't feel 251 00:13:42.880 --> 00:13:46.620 bad about having to draw this out on paper. 252 00:13:46.620 --> 00:13:47.990 It's something that we all do, 253 00:13:47.990 --> 00:13:50.480 so I definitely encourage you to do that. 254 00:13:51.770 --> 00:13:53.120 The last thing that we've got left 255 00:13:53.120 --> 00:13:55.460 is the leading two children. 256 00:13:55.460 --> 00:13:57.060 We're going to do this in the very next video, 257 00:13:57.060 --> 00:13:58.750 just because this one is getting a bit long, 258 00:13:58.750 --> 00:14:02.420 and it's gonna be a little bit trickier. 259 00:14:02.420 --> 00:14:05.000 There's a few if statements that have to go in here. 260 00:14:05.000 --> 00:14:07.370 So let's look at this in the very next video. 261 00:14:07.370 --> 00:14:08.320 I'll see you there.