# Binary Search Trees: Part 3

Published on May 6th 2023Duration: 50:52Watch on YouTube

Carol and I continue our lesson on binary search trees. This time we focus on how to delete a node from the tree.

## Transcript

The following transcript was automatically generated by an algorithm.

• 00:00 : now we're gonna
• 00:02 : calm this tree from left to right you
• 00:05 : see yes let's see I see now
• 00:07 : we're gonna count the numbers from
• 00:10 : smallest to largest
• 00:13 : like this
• 00:14 : yeah okay
• 00:17 : so this is like you just I'm just gonna
• 00:19 : replace three with the smallest item in
• 00:23 : my larger side and in threes
• 00:26 : larger side and everything still works
• 00:29 : all the rules still hold
• 00:31 : and we can still do the scanning and
• 00:34 : we're
• 00:36 : and we're walking the numbers in order
• 00:39 : still
• 00:47 : okay so last time we like
• 00:50 : we went into details about
• 00:54 : um
• 00:55 : how to add a node to a tree
• 00:59 : um
• 01:03 : but what is the pickle of this algorithm
• 01:06 : so the note to the tree adding the note
• 01:09 : so we said like we're gonna we're gonna
• 01:11 : like this window we're gonna move it
• 01:14 : down the tree and we can only ski down
• 01:17 : One path we can
• 01:22 : um
• 01:23 : and when you find the place
• 01:27 : to insert yourself you're gonna insert
• 01:29 : yourself right
• 01:31 : um and that place is always under a leaf
• 01:36 : node so a note that has room
• 01:39 : has null pointers either on its left
• 01:43 : child or its right child so you can
• 01:45 : insert yourself there
• 01:49 : um yeah so that's the algorithm
• 01:52 : um
• 01:53 : and do we write it down here
• 01:56 : yeah we wrote it down here more or less
• 01:58 : uh
• 02:05 : about how to know whether you need to
• 02:08 : insert yourself
• 02:09 : to the parents left side or the right
• 02:11 : side
• 02:12 : right
• 02:13 : um and there I I think there are
• 02:16 : different
• 02:17 : ways to do it and I I kind of
• 02:21 : came up with a way on the Fly which will
• 02:25 : probably work it may not necessarily be
• 02:27 : the most elegant way but that doesn't
• 02:29 : really matter that's just the details
• 02:32 : um that what I want to get at now is
• 02:35 : like what was the big goal of this
• 02:40 : yeah yeah where is it login
• 02:44 : um because we only have to I feel like
• 02:48 : I'm gonna butcher this explanation but
• 02:50 : I'll try we only have to
• 02:52 : for each level we go down it's only like
• 02:55 : one more operation
• 02:59 : like I I don't feel like that's a good
• 03:02 : explanation of why how many how many
• 03:05 : levels are there to the tree relative to
• 03:09 : n which is the number of notes in the
• 03:12 : entire tree
• 03:16 : that that's the key
• 03:18 : yeah and believe it or not I actually
• 03:21 : have looked at this since we last talked
• 03:23 : because I know it was a hard subject or
• 03:25 : hard for me
• 03:26 : um
• 03:28 : tree that has all these notes I think
• 03:31 : there's seven here seven yep and given a
• 03:35 : tree with seven nodes
• 03:37 : there are three levels right right so
• 03:41 : that's the key the connection between
• 03:44 : the number of elements in the full tree
• 03:48 : if I tell you there are this number of
• 03:51 : elements n elements
• 03:53 : how many levels High tall is this three
• 03:57 : and that relationship is represented
• 03:59 : with
• 04:00 : log of n a log base 2 of N More
• 04:04 : specifically okay
• 04:07 : so yeah
• 04:08 : because the other side the other
• 04:11 : relationship is exponential like if I
• 04:15 : told you
• 04:16 : I had a tree that has
• 04:19 : three levels
• 04:21 : then you know that the uh the size the
• 04:27 : number of notes in the tree is two
• 04:29 : two to the third power two to the Third
• 04:34 : well minus one
• 04:36 : that's not important but that that one
• 04:39 : makes way more sense I um
• 04:42 : I I can wrap my head around but so I
• 04:44 : just really have to drive home that the
• 04:46 : login is the inverse of that one exactly
• 04:49 : it's just the inverse of power of taking
• 04:52 : up power okay
• 04:55 : yep so that's why we get the log
• 04:58 : um
• 04:59 : so cool uh I think this and updating is
• 05:03 : I'm gonna skip over updating because
• 05:06 : that's not super interesting it's just
• 05:09 : you just retrieve the note and then you
• 05:11 : update it oh actually no you can't just
• 05:15 : update a thing
• 05:17 : uh or not the key anyway but when I say
• 05:21 : updating I really mean like you're not
• 05:23 : updating the key but maybe the data
• 05:25 : that's associated with the key
• 05:28 : but what about if the so if you're
• 05:32 : updating the data
• 05:34 : not the is the is the key the thing that
• 05:37 : is compared the key is like yeah nine
• 05:41 : versus eight versus imagine each note is
• 05:45 : not just a number but it's like a
• 05:47 : customer it has all kinds of customer
• 05:49 : data but the number is just the customer
• 05:53 : ID
• 05:54 : okay
• 05:55 : yeah or or or instead of sorting by the
• 05:59 : ID which might not be super useful you
• 06:02 : might want to sort by the customer last
• 06:04 : name okay which gets us back to that
• 06:08 : zone Book application right
• 06:10 : so so
• 06:12 : um yeah so if I say up
• 06:15 : these were not updating is our
• 06:17 : comparison value whatever that may be
• 06:19 : correct yeah okay if you need to change
• 06:22 : the key that's a big deal you will need
• 06:25 : to remove it and then add a new one back
• 06:28 : in basically
• 06:30 : um and but if you're just updating the
• 06:32 : phone number which is not the key
• 06:36 : then it's you're just retrieving the
• 06:39 : note and then changing a field inside
• 06:40 : that's all you're doing
• 06:45 : so for that reason I'll just skip the
• 06:48 : updating that uh that basically it's
• 06:51 : also a bigger login okay
• 06:55 : because it's same as retrieval um so
• 06:57 : let's talk about deletion today which is
• 07:00 : the most funky one of all of them
• 07:04 : um
• 07:05 : uh so
• 07:08 : maybe I'm running out of room over there
• 07:10 : so just write delete
• 07:12 : how do you delete a node from a tree
• 07:18 : um
• 07:19 : well if
• 07:22 : if it were
• 07:24 : like let's say you have five
• 07:30 : um
• 07:33 : three
• 07:36 : seven
• 07:41 : two
• 07:45 : or so I'm doing everything in order
• 07:48 : okay
• 07:51 : um
• 07:53 : so it's something like this
• 07:58 : um
• 08:00 : if you need to delete a leave now
• 08:04 : obviously that's very easy
• 08:07 : yeah you did delete six just get rid of
• 08:11 : it but if you needed to delete
• 08:15 : um what is the term for a non-leaf is it
• 08:19 : an internal node it might be an internal
• 08:22 : node it's a non-leaf node
• 08:25 : um so if you need to delete an internal
• 08:27 : node
• 08:29 : uh it's actually
• 08:32 : um
• 08:34 : well I don't want to say
• 08:37 : hard but uh definitely harder than just
• 08:41 : getting rid of something so
• 08:44 : let's try to think about when I had to
• 08:47 : look it up to remind myself how to do it
• 08:50 : okay um so let's say I needed to uh
• 08:55 : remove three
• 08:58 : from this tree
• 09:02 : how would we do this
• 09:04 : okay
• 09:06 : well
• 09:08 : you're going to have to handle all its
• 09:11 : children I mean I I right off the bat
• 09:13 : that's the first thing that comes to
• 09:15 : mind is like if I remove three
• 09:18 : two and four in this instance are gonna
• 09:21 : have to be reorganized appropriately
• 09:24 : within the rules of the
• 09:27 : binary tree uh-huh
• 09:31 : right
• 09:34 : so my instinct and I I'm guessing that
• 09:37 : this is not at all right but I'm just
• 09:39 : gonna say it anyway is that we would
• 09:41 : remove everything under the node like we
• 09:44 : we have to remove everything every child
• 09:47 : too like we have to remove them all okay
• 09:50 : three two and four also must be removed
• 09:53 : and put back in
• 09:55 : but there's got to be some other
• 09:57 : solution to my first thought okay just
• 10:03 : yeah okay so done two would go here
• 10:07 : and then four would go here afterwards
• 10:11 : but that's I mean depending on how big
• 10:13 : the the
• 10:15 : tree is how many children are under the
• 10:18 : removed no that could be a lot yeah it
• 10:21 : could be a lot if you're removing the
• 10:23 : root for example yeah
• 10:30 : all of the tree except right for that
• 10:33 : one node which would be deleting your
• 10:35 : tree and redo starting it
• 10:38 : yeah which would would be the Big O of
• 10:41 : that
• 10:43 : that would be
• 10:45 : big out of in yeah because you're
• 10:48 : recreating
• 10:49 : thing yeah yeah exactly so
• 10:53 : let's not do that
• 10:57 : uh okay
• 10:59 : so
• 11:01 : um
• 11:04 : what else can we do
• 11:08 : um and I have to admit
• 11:10 : I don't
• 11:13 : this is non-intuitive for me
• 11:16 : and I had to review it but even now I'm
• 11:19 : not so
• 11:21 : um I I I'm not so certain and in a way
• 11:24 : that's good because
• 11:27 : um I think we should really understand
• 11:29 : why
• 11:31 : we should do this
• 11:33 : and
• 11:35 : um
• 11:39 : then
• 11:42 : uh let's say so one idea okay so it so
• 11:48 : maybe we'll try to
• 11:50 : come up with another strategy okay and I
• 11:54 : I kind of know in the back of my mind I
• 11:57 : I know what the correct answer is but
• 11:59 : I'm gonna try to forget about that just
• 12:02 : for a moment okay
• 12:04 : um
• 12:04 : so
• 12:07 : well
• 12:08 : we could
• 12:11 : um
• 12:12 : well okay three used to be here
• 12:15 : and threes left child was two and it's
• 12:19 : right how it was four
• 12:21 : right right
• 12:23 : um and
• 12:25 : we need to stick to children
• 12:29 : under five right
• 12:34 : um
• 12:34 : so maybe we make one of them the left
• 12:38 : child of five
• 12:40 : both of them are going to be smaller
• 12:43 : than five so either one should work
• 12:46 : so maybe if I put two as the left child
• 12:50 : of five
• 12:52 : then uh
• 12:55 : that I can put four as the right child
• 12:58 : of two and that seems to work for this
• 13:01 : case
• 13:04 : okay yes
• 13:06 : um but that kind of that can break down
• 13:08 : uh and I'll show you why
• 13:12 : um that can break down because
• 13:15 : well let's not make another I'm just
• 13:17 : gonna reuse this same tree
• 13:20 : um
• 13:21 : a breakdown if I want to move this move
• 13:27 : this
• 13:30 : if I want to remove five no so I'm on a
• 13:34 : case where
• 13:37 : your immediate children are also
• 13:40 : internal notes right okay
• 13:45 : um
• 13:48 : actually I'm a little confused hold on
• 13:53 : sure
• 13:54 : uh
• 14:00 : do I want to
• 14:03 : go down no I I don't I don't want to do
• 14:06 : live just yet
• 14:09 : I'm gonna add more children to these
• 14:12 : guys
• 14:13 : uh
• 14:14 : uh oh boy
• 14:16 : this is gonna be one
• 14:19 : this is going to be two and a half
• 14:22 : the
• 14:28 : the well these things
• 14:33 : I have to make some room here well this
• 14:36 : is gonna be
• 14:38 : three and a half
• 14:41 : this is gonna be four and a half okay
• 14:44 : and I want to remove
• 14:46 : three
• 14:48 : so I'm gonna move three out
• 14:50 : uh and then I have to either choose four
• 14:54 : or two
• 14:55 : to be the immediate descendant of five
• 15:02 : um
• 15:06 : and let's say I choose four
• 15:09 : and then if I choose four
• 15:13 : then two
• 15:15 : can be the The Descent to be the left
• 15:19 : descendant of four
• 15:21 : yep that makes sense
• 15:29 : um so where are they gonna go
• 15:32 : um
• 15:33 : well
• 15:35 : you could
• 15:38 : um
• 15:41 : like four can't have three children so
• 15:45 : one of them is gonna have to go
• 15:48 : uh
• 15:49 : let's say is three point three point
• 15:52 : five has to go uh where's 3.5 going to
• 15:56 : go
• 15:57 : hmm I don't know maybe
• 16:01 : maybe under
• 16:03 : 355 is gonna have to go this way
• 16:07 : because it is
• 16:10 : less than four right
• 16:12 : so we will have to add 3.5 back
• 16:17 : in the subtree
• 16:19 : why can't it go to the right of 4.5
• 16:25 : right because it's a less than four so
• 16:28 : it has to be in the left side of four
• 16:32 : it used to be on the left side of four
• 16:36 : oh okay but I drew the to the lines in
• 16:40 : this way to make rooms yeah
• 16:43 : I'm okay I'm now I'm missing something
• 16:47 : which I probably just
• 16:49 : need a review I thought that okay when
• 16:52 : we're putting a new number in like let's
• 16:55 : say we were just about to add 3.5 for
• 16:57 : the first time yeah 3.5 is the next
• 17:01 : number
• 17:02 : it would be to the right of five
• 17:05 : then to the right of four
• 17:10 : but then we already have a number that's
• 17:14 : um
• 17:17 : it should have been less and less and
• 17:19 : then yeah I'm sorry I'm at last I'm
• 17:22 : getting backwards yeah
• 17:23 : um
• 17:24 : and then it would end up to the left of
• 17:28 : 2.5
• 17:30 : uh right right that's where it would end
• 17:34 : up okay okay I see so we can't just
• 17:36 : stick it to the left of 4.5 okay sorry I
• 17:39 : just have to talk that out thank you yep
• 17:41 : so
• 17:44 : there might be a way to do it like this
• 17:47 : uh but it it'll potentially have to
• 17:51 : rearrange
• 17:53 : all the way down right
• 17:56 : it it
• 17:57 : um
• 17:58 : but
• 18:00 : um
• 18:00 : I think if you did it this way
• 18:05 : this will also be uh Big O of log n
• 18:10 : though because
• 18:13 : right because
• 18:15 : um
• 18:16 : we're just moving down the whole tree
• 18:18 : like the worst case we're going down
• 18:22 : uh to the bottom of the tree
• 18:26 : I think it's like inserting something
• 18:28 : new it would be right
• 18:32 : almost yeah yeah yeah because we're it's
• 18:36 : like inserting because there's like an
• 18:37 : extra child that we need to make room
• 18:40 : for and then we're inserting it in this
• 18:44 : sub tree
• 18:46 : all right
• 18:47 : yeah that's below it
• 18:50 : I think that could work
• 18:52 : um
• 18:54 : okay maybe we've invented a new way to
• 18:57 : do it but though the textbook way is not
• 19:00 : this okay
• 19:02 : so that I kind of wanna
• 19:06 : let me think
• 19:10 : do I think yeah I think this message
• 19:12 : should work
• 19:13 : um I don't know why they don't do it
• 19:16 : this way
• 19:17 : but but the textbook way
• 19:20 : is
• 19:23 : let me see
• 19:26 : I'm gonna go back to what it was first
• 19:29 : here
• 19:33 : was it like this
• 19:35 : uh
• 19:37 : yeah I think so
• 19:39 : and then you had um two more
• 19:41 : you
• 19:42 : oh yeah another level yeah
• 19:47 : yeah oh wait I can undo right
• 19:51 : yes
• 20:13 : yes okay nice job all right
• 20:17 : um
• 20:19 : so
• 20:22 : so I the textbook way to actually do the
• 20:26 : delete so we want to delete three
• 20:30 : is actually
• 20:34 : um
• 20:35 : I think you tick the smallest item
• 20:41 : but see we must let's first remove three
• 20:46 : and then I think you make
• 20:49 : oh I think what you do is
• 20:53 : you replace three
• 20:57 : with the smallest item
• 21:01 : in the
• 21:04 : in the bigger side
• 21:07 : which in this case is 3.5
• 21:14 : does that make sense yeah that does and
• 21:17 : then everything else can stay where it
• 21:18 : is exactly so there's less movement and
• 21:22 : and it also makes sense why that works
• 21:24 : like it it's the smallest
• 21:27 : you could also do the other way around
• 21:28 : which would be you could do the biggest
• 21:31 : item in the smaller side also
• 21:36 : right you could replace yourself with
• 21:39 : 2.5 and that would also work
• 21:42 : yeah it would I'm still trying to wrap
• 21:45 : my mind around why it works but I'm I
• 21:47 : missed it I'm slow thank you yeah I
• 21:51 : think the reason why it works is
• 21:56 : um if
• 21:57 : go back to the binary search algorithm
• 22:00 : for the array
• 22:03 : if you looked
• 22:05 : um well this I'm gonna fix this graph a
• 22:08 : little bit make more room here
• 22:17 : so that they are actually lined up and
• 22:22 : sorted correctly
• 22:30 : okay
• 22:31 : so if you just
• 22:34 : calm the tree from left to right then
• 22:37 : you get an increasing order right
• 22:42 : if you do what if you if you scan this
• 22:45 : tree from left to the right damn it okay
• 22:48 : scan like like there was a line that is
• 22:52 : moving from left to right
• 22:55 : uh
• 22:57 : like this
• 23:00 : there's a line
• 23:02 : and we're gonna
• 23:04 : calm this tree from left to right you
• 23:07 : see yes let's see I see now we're gonna
• 23:11 : count the numbers from smallest to
• 23:14 : largest
• 23:15 : like this
• 23:16 : yes okay
• 23:19 : so the reason why
• 23:23 : just replacing three with the smallest
• 23:27 : item
• 23:29 : in its bigger side is because the number
• 23:33 : is right next to three in this ordering
• 23:36 : yes okay okay and it would be the same
• 23:40 : if we took the biggest item from its
• 23:42 : smaller side it would be the same
• 23:45 : there'd be either number that would be
• 23:47 : immediately to the right or left of that
• 23:49 : number if they were all lined up in a
• 23:51 : row yeah if if it were assorted array
• 23:54 : then yeah 2.5 would be right before 3
• 23:57 : and 3.5 would be right after three
• 24:00 : yes okay
• 24:02 : and then there is why uh so so what we
• 24:07 : talked about with arrays it's really
• 24:09 : annoying to remove stuff because you
• 24:12 : have to shift everybody after it over by
• 24:15 : one
• 24:16 : and that is a bigger of n operation
• 24:19 : right so that's really annoying
• 24:23 : um so we're doing that with trees now
• 24:26 : and the interesting thing with trees is
• 24:29 : uh because the tree is like or arranged
• 24:33 : in this kind of dynamic fashion
• 24:36 : where
• 24:38 : you know we're not all packed into bins
• 24:41 : but we're like just have we know where
• 24:45 : everything is just based on our
• 24:47 : relationship with each other
• 24:49 : you can dynamically change those
• 24:52 : relationships so yeah
• 24:54 : so this is like you just I'm just gonna
• 24:57 : replace three with the smallest item in
• 25:01 : my larger side and in threes
• 25:04 : larger side and everything still works
• 25:06 : all the rules still hold
• 25:09 : and we can still do the scanning and
• 25:12 : we're
• 25:14 : and we're locking the numbers in order
• 25:16 : still
• 25:20 : that's really cool
• 25:21 : yeah
• 25:23 : yeah that's just really neat
• 25:26 : yeah so then the question is
• 25:30 : well let's okay before we say what the
• 25:33 : Big O is
• 25:37 : um I I I I really like I really like
• 25:40 : that scanning thing yeah that's a good
• 25:44 : visual it's it's really cool I'm still
• 25:46 : amazed by it I didn't see that before I
• 25:50 : didn't see that one coming yeah cool
• 25:52 : uh yeah we we discovered it together so
• 25:56 : yeah so this one is going to become null
• 25:59 : at the end of everything
• 26:02 : um so
• 26:03 : um let's try to write this algorithm out
• 26:06 : first so how do you delete a number
• 26:10 : um Fairview
• 26:13 : um first you do the retrieval
• 26:15 : basically like use retrieve algo
• 26:20 : to find
• 26:22 : no you want to delete
• 26:26 : now this is really big now
• 26:30 : because I Zoomed In by a lot I think
• 26:33 : this is fine uh so that was step one and
• 26:36 : step two
• 26:39 : um
• 26:41 : basically replace
• 26:45 : self
• 26:46 : with
• 26:48 : smallest
• 26:51 : note in your
• 26:55 : bigger side
• 26:58 : which would be the right side
• 27:02 : um
• 27:06 : um and then
• 27:08 : um
• 27:11 : uh
• 27:13 : well you're gonna
• 27:15 : well you you're gonna I guess
• 27:18 : Maybe
• 27:19 : this is too broad this statement so
• 27:24 : maybe there's two steps to that I was
• 27:26 : just thinking that but I thought maybe
• 27:27 : you were trying to do a higher level
• 27:29 : right yeah I I think it's helpful to
• 27:33 : like describe things in a higher level
• 27:36 : but uh let's also go lower level okay
• 27:41 : um
• 27:42 : like if a high level statement is very
• 27:46 : clear to humans
• 27:48 : and an ambiguous then that's really
• 27:52 : um but in order to replace yourself with
• 27:55 : the smallest note if first you have to
• 27:57 : Traverse
• 28:02 : introvert well actually
• 28:05 : how to find
• 28:07 : find smallest no
• 28:10 : yeah in the right child now
• 28:14 : interestingly
• 28:15 : the algorithm for finding the smallest
• 28:19 : node in a tree which I'm calling I mean
• 28:23 : the right child is just a tree okay
• 28:26 : right it doesn't matter that it's a sub
• 28:28 : tree a sub tree is still
• 28:31 : a tree and it it has it satisfies all
• 28:35 : the rules of a binary search tree just
• 28:37 : like your larger tree so so I can say
• 28:43 : um
• 28:43 : I need a algorithm
• 28:47 : to find the smallest node in a tree
• 28:51 : so
• 28:53 : maybe we'll come back to that what is
• 28:56 : our goal to find smallness node in
• 29:02 : PST which is short for binary search
• 29:05 : tree
• 29:07 : um
• 29:10 : and then after you've found that
• 29:13 : uh
• 29:15 : remove
• 29:17 : that smallest node
• 29:19 : and then
• 29:22 : we have to uh come back up the tree
• 29:26 : somehow
• 29:30 : uh and and then
• 29:35 : place
• 29:36 : uh three node
• 29:39 : with the smallest
• 29:49 : so that's the algorithm
• 29:52 : um
• 29:55 : let's go over this item
• 29:58 : because it's somewhat interesting uh how
• 30:00 : how to
• 30:02 : how to find smallest
• 30:06 : node in a BST so so uh you can
• 30:14 : note from the tree problem and just
• 30:16 : think about if I gave you any
• 30:19 : binary search tree how do you find the
• 30:23 : smallest node in it
• 30:26 : okay so because I know I am going for
• 30:32 : the smallest I know I'm going to be
• 30:34 : dealing with the left
• 30:36 : hand side yeah so I can immediately cut
• 30:40 : it in half and be like I need to search
• 30:42 : down the left side
• 30:43 : and then I want to go
• 30:48 : keep going left and left and left until
• 30:50 : I hit a null value and I know that
• 30:54 : the value before the null value is the
• 30:57 : smallest exactly yeah yeah so so you
• 31:01 : don't have to do this if statement
• 31:03 : that we would have to do when we're
• 31:05 : searching for something specific
• 31:07 : we're just always going left yeah
• 31:10 : exactly that's the difference and
• 31:13 : uh and what is the well let me write it
• 31:16 : down first so basically
• 31:18 : while uh let's say current node is equal
• 31:23 : to root node
• 31:26 : okay I'll just say root while current
• 31:29 : node
• 31:30 : is not no
• 31:35 : and current node is equal to left note
• 31:38 : right left child
• 31:41 : and then uh oh hold on
• 31:45 : then we're gonna after this loop we're
• 31:47 : gonna lose what the previous one was
• 31:50 : right so we need to be storing it every
• 31:53 : time like maybe I have a private node is
• 31:56 : equal to
• 31:59 : um
• 32:01 : or another way is while
• 32:06 : current notes left
• 32:08 : is not no
• 32:09 : so well
• 32:13 : I like that left node is not null
• 32:20 : when I say left note I mean of current
• 32:23 : note that this is pseudocode so I don't
• 32:26 : have to be precise
• 32:27 : uh well well left note is uh not no then
• 32:34 : current node is equal to left child and
• 32:38 : at the end
• 32:39 : you just say return the current mode
• 32:42 : there's a there's probably an edge case
• 32:45 : that I missed which is if the current
• 32:48 : node is already null
• 32:51 : then that's a problem
• 32:53 : uh but whatever this is pseudo code uh I
• 32:59 : don't have to I don't have to run it so
• 33:01 : I think if you actually program it
• 33:03 : you'll find those edge cases and then
• 33:06 : you have to deal with them
• 33:08 : um so something like this uh what is the
• 33:10 : Big O of this algorithm
• 33:14 : you're gonna have to
• 33:16 : have all the way down
• 33:19 : the levels it's
• 33:22 : yep
• 33:24 : yep
• 33:26 : so again it's login
• 33:29 : uh
• 33:32 : so okay so now that we've figured out
• 33:35 : how to find the smallest node in a
• 33:37 : binary tree binary search tree and we
• 33:40 : know it's uh
• 33:42 : worse it's bigger it's performance
• 33:46 : runtime
• 33:48 : um you come back here
• 33:51 : um
• 33:51 : and I we know this is bigger of login
• 33:54 : this sub step of this deletion algorithm
• 33:59 : um
• 34:00 : so after we find it we're gonna remove
• 34:03 : that
• 34:04 : the smallest note well we're removing it
• 34:08 : from the bottom of a tree right right so
• 34:12 : that's the easiest case it's gonna
• 34:15 : unlink it that that's gonna be a bigger
• 34:17 : one yep
• 34:22 : and then come back up the tree
• 34:26 : um
• 34:27 : it seems like we should have stored our
• 34:30 : starting point yeah somewhere
• 34:33 : we don't actually have to climb back up
• 34:36 : the tree it can it can be just like at
• 34:39 : when we were at
• 34:41 : when we at we're at over here
• 34:44 : right well back then
• 34:48 : it was three that was here so it was
• 34:50 : like this
• 34:52 : uh when we were here we can just call
• 34:55 : into a routine that would go down the
• 34:58 : tree find 3.5
• 35:01 : and then also delete it from that tree
• 35:04 : all in one go and then when that
• 35:07 : function call is done we're back up here
• 35:09 : so that doesn't actually take any extra
• 35:12 : work
• 35:13 : okay yeah so that's not really a step
• 35:17 : even so maybe maybe we don't don't even
• 35:21 : count that
• 35:23 : um but uh yeah uh and then we're gonna
• 35:27 : replace
• 35:29 : the three with the note that was found
• 35:32 : so
• 35:34 : we are
• 35:35 : I mean we could even reuse the note we
• 35:38 : just overwrite the value of the node
• 35:42 : yeah so so that that's that's just a
• 35:46 : bigger of one
• 35:52 : um
• 35:54 : and then this retrieval to find it the
• 35:58 : thing you want to delete is a bigger
• 36:01 : yep
• 36:04 : um so yeah so the whole thing is bigger
• 36:08 : of login because the worst two cases are
• 36:10 : a bigger login
• 36:13 : oh
• 36:15 : so that's how you delete stuff from a
• 36:17 : binary tree
• 36:18 : yeah that's pretty neat I and I'm
• 36:21 : fascinated by the
• 36:23 : the Scott the the concept it's so simple
• 36:27 : and yeah I feel like I would never have
• 36:29 : come up with that
• 36:31 : yeah it's very very intelligent design
• 36:34 : it's very yeah once you see it you're
• 36:37 : like yeah it's very obvious but if you
• 36:40 : had to come up with that yourself it
• 36:43 : might take a while yeah I honestly
• 36:46 : there's there's a lot of problems that
• 36:48 : are like that though uh where
• 36:51 : like finding the simple and elegant
• 36:54 : solution is
• 36:56 : um actually very difficult
• 36:58 : uh like you have to try a lot of
• 37:02 : different solutions and then see that a
• 37:05 : lot of them are bad
• 37:08 : uh before you before you find the one
• 37:11 : it's more of a search
• 37:14 : uh like you're just
• 37:17 : looking in all the different Corners oh
• 37:21 : that
• 37:22 : uh for something good and then when you
• 37:26 : find it
• 37:27 : it's like finding gold
• 37:30 : and then uh
• 37:32 : and then I I that's how I see problem
• 37:35 : solving
• 37:37 : um which is why I think it helps
• 37:42 : and I think that that I there's a lot of
• 37:47 : work problems
• 37:48 : that I've approached that way
• 37:52 : um
• 37:52 : and
• 37:55 : it helps to take things slow I think and
• 37:59 : and not be in a rush to implement the
• 38:02 : first idea that comes to mind
• 38:10 : you know
• 38:12 : producing
• 38:14 : something for someone is this this like
• 38:16 : you have to the productivity
• 38:19 : aspect of you know commercial work
• 38:22 : balancing with like getting the best
• 38:24 : ideas and that sometimes take time and a
• 38:26 : whole bunch of iterations like it seems
• 38:28 : like an eternal like balance issue for
• 38:32 : those of us yeah that are working
• 38:35 : in it so
• 38:37 : yeah
• 38:38 : I I think it's yeah it's uh you have to
• 38:43 : always balance that I agree
• 38:46 : um but even if you're not
• 38:48 : um
• 38:52 : even if you're not working in a company
• 38:55 : you're working on your personal projects
• 38:57 : I think that balance is still an issue
• 39:02 : um even though you can yeah you can if
• 39:04 : you want to take more time
• 39:06 : you can but there's also a limit there
• 39:10 : because if things just keep dragging on
• 39:13 : and on then you feel like you're not
• 39:15 : doing anything
• 39:17 : productive yeah
• 39:20 : um
• 39:21 : okay
• 39:22 : um let me think okay so
• 39:26 : maybe we'll just talk about
• 39:29 : um
• 39:32 : how to keep a tree balanced yes I've
• 39:35 : been waiting for this
• 39:41 : good answers but I I have questions okay
• 39:44 : so
• 39:45 : um so there's several um so there's a
• 39:50 : thing called uh self-balancing trees
• 39:52 : first of all
• 39:56 : um so if we um
• 39:59 : if we Google for self-balancing trees
• 40:07 : this bar on top is in my way
• 40:11 : how can I get rid of that oh it went
• 40:14 : away okay so balancing binary tree
• 40:19 : um
• 40:20 : there's many different variants of cells
• 40:24 : balancing trees and this is the list
• 40:31 : it's like uh
• 40:34 : well it used to be a very um and and in
• 40:37 : some ways like I think the weight
• 40:40 : balance tree no the weight balance tree
• 40:42 : is
• 40:43 : still pretty old okay
• 40:46 : um it's in the 70s so it was a big area
• 40:49 : of research in computer science
• 40:52 : um right probably not today anymore but
• 40:55 : uh
• 40:56 : uh the the they figured out many
• 40:58 : different ways I would say
• 41:01 : probably the most famous one is the red
• 41:04 : black tree
• 41:07 : and and maybe a v L3 are the two most
• 41:11 : famous ones
• 41:12 : but then the weight balance tree made a
• 41:15 : Resurgence a little bit uh in recent
• 41:18 : years
• 41:19 : because uh some
• 41:23 : I want to say Haskell like some
• 41:26 : functional programming languages decided
• 41:29 : to use the weight balance trees
• 41:31 : in instead of the red black trees red
• 41:35 : black trees I believe is
• 41:38 : commonly used I think this is the one
• 41:41 : used in the Java standard Library if you
• 41:45 : use a hash in Java it uses this red
• 41:48 : black tree
• 41:50 : and then the the standard library in
• 41:53 : Haskell uses a weight balance the tree
• 41:57 : um
• 41:59 : and then the AVL tree
• 42:03 : I don't know which one which things
• 42:06 : actually use the avl3 but they're all
• 42:08 : center around one idea which is so I'm
• 42:12 : not going to go into the specifics of
• 42:15 : the individual ones actually okay
• 42:18 : partially because
• 42:21 : uh I haven't studied them recently
• 42:24 : I have studied way balance tree and red
• 42:28 : black tree and I have implemented them
• 42:30 : myself
• 42:31 : but they're complicated enough that if I
• 42:36 : don't study it just like the night
• 42:38 : before I probably won't remember how to
• 42:41 : do them okay
• 42:42 : very fair so so that that's how
• 42:45 : complicated they are like like I'm I'm
• 42:48 : the the sessions I've been doing with
• 42:50 : you just off the cuff the stuff that I
• 42:53 : like know well enough to present them
• 42:55 : and this is not one of them that's fair
• 42:58 : I you talked about the red black tree a
• 43:01 : little bit in the video I watched on
• 43:02 : databases and my head was spinning
• 43:04 : pretty quickly I was like wait wait I
• 43:06 : need to slow down
• 43:08 : it was very complex yeah yeah yeah
• 43:12 : um so
• 43:14 : so
• 43:15 : um but but I'm gonna talk about the
• 43:18 : General ideas that all of them use which
• 43:21 : is simply
• 43:23 : uh detecting when a tree is out of
• 43:26 : balance and then fixing right so so the
• 43:31 : the self boundatories I'll have uh they
• 43:34 : detect
• 43:36 : when a tree is out of balance
• 43:42 : and then
• 43:44 : fix fix it when it deems
• 43:49 : necessary
• 43:52 : um and that's that's in a nutshell
• 43:54 : that's what they do now now before
• 43:57 : drilling into that though I do want to
• 44:01 : mention a devil's advocate argument
• 44:05 : which says
• 44:09 : um
• 44:11 : if you're
• 44:13 : self-balancing trees are not necessary
• 44:19 : if the stuff that's coming in Is Random
• 44:25 : like statistically
• 44:28 : if you have a insertion into the tree
• 44:33 : That Is Random
• 44:35 : then it'll be more or less balanced
• 44:39 : and so maybe you don't really have to
• 44:42 : and and people have done experiments
• 44:45 : and tested this
• 44:47 : and so some people claim that it's not
• 44:50 : necessary as long as your data coming in
• 44:54 : is random but as we have shown
• 44:58 : um often
• 45:00 : you it's very easy to write a program
• 45:02 : that inserts things into a tree that's
• 45:05 : not in a random way right
• 45:07 : yeah it's like like getting things to be
• 45:10 : truly random like it seems like random
• 45:12 : enough to solve this issue is more
• 45:15 : complex than you would think it would be
• 45:17 : is is kind of
• 45:19 : my thought my initial thought yeah it
• 45:22 : could be yeah yeah like random
• 45:24 : generating random numbers is another
• 45:27 : science that you could really dig deep
• 45:29 : into grass
• 45:30 : so so yeah I I agree with that sentiment
• 45:35 : um
• 45:36 : so
• 45:38 : how do you detect when a tree is out of
• 45:42 : balance uh so that's the first question
• 45:44 : and then the second question is how do
• 45:48 : you fix it when it's necessary and what
• 45:51 : what what is necessary mean
• 45:55 : um
• 45:56 : so well one way you could do it is just
• 45:59 : by
• 46:01 : um and this is the weight balance tree
• 46:03 : method is in on each node of the tree
• 46:07 : they would um
• 46:10 : add an extra field
• 46:13 : that tells them
• 46:16 : the number of nodes that are present in
• 46:20 : this subtree
• 46:23 : so
• 46:25 : so they will add an extra field
• 46:28 : and put it in red and so
• 46:32 : here there's
• 46:34 : one and
• 46:37 : here this one
• 46:39 : here there's two
• 46:42 : and here there is well
• 46:46 : one two three four five six here there's
• 46:49 : six
• 46:53 : I should have done the sub tree first so
• 46:55 : this is one
• 46:58 : here is a chip
• 47:03 : uh no this is wrong this should be three
• 47:08 : uh yeah so your number is the number of
• 47:13 : your left child plus the number of your
• 47:16 : right child plus one right that's
• 47:19 : amazing yourself okay yeah because you
• 47:21 : count yourself
• 47:22 : so so yeah so so in weight balance trees
• 47:26 : which might be the one that's easier to
• 47:28 : explain
• 47:31 : uh this is what they do uh oh no again
• 47:34 : this would be three
• 47:36 : forget to add one so this should be ten
• 47:39 : now I think three plus six plus three
• 47:43 : plus one yeah so so uh by this way
• 47:49 : you have a this is like caching the
• 47:52 : account because you could also just go
• 47:55 : through the entire tree and get the
• 47:57 : number
• 47:58 : um but this is hashing the count in each
• 48:02 : note so you can access them quickly and
• 48:04 : the reason you want to access it quickly
• 48:07 : is because you want to be able to tell
• 48:09 : if things are out of balance and in this
• 48:12 : case well 6 is greater than three
• 48:15 : so it is not balanced right
• 48:19 : right so
• 48:21 : um but how much out of balance do you
• 48:24 : deem it necessary to do something about
• 48:27 : it
• 48:28 : um uh that that's a question and that's
• 48:31 : a bit of um
• 48:33 : I don't have a straightforward answer
• 48:36 : either
• 48:38 : in way balance tree it's a parameter
• 48:42 : it is like a factor it's like a ratio
• 48:45 : that you multiply that says if if it's
• 48:49 : this if the left side is this percent
• 48:53 : bigger than the right side then we
• 48:55 : should do something about it
• 48:58 : it makes sense that it might be varying
• 49:00 : degrees of um
• 49:03 : of
• 49:04 : I don't know weightedness that you care
• 49:06 : about for different things yep
• 49:11 : so I think I think that's probably as
• 49:14 : much as I'm gonna say about that um and
• 49:16 : in red black tree they have a very uh
• 49:20 : interesting method of figuring out
• 49:24 : uh sort of when a tree is out of balance
• 49:27 : and you need to do something about it
• 49:29 : and then in the Avo tree I think they
• 49:32 : keep
• 49:33 : the difference
• 49:35 : instead of keeping the absolute number
• 49:39 : of the count
• 49:41 : avo3 they keep the difference between
• 49:45 : the left side and the right side I see
• 49:49 : um and then they try to keep that
• 49:51 : difference Within
• 49:54 : one or within two I believe like that
• 49:59 : they can't be out of balance more than
• 50:01 : two
• 50:05 : there's like there's a factor that
• 50:09 : um
• 50:10 : so
• 50:11 : um so I'm just gonna hand wave over that
• 50:14 : so that's that's how you detect if the
• 50:16 : tree is out of bounds how do you fix it
• 50:19 : when I deem it necessary let's talk