Binary Search Trees: Part 3

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:01 : we had some questions about specifics
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:36 : algorithm I think um log in
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:00 : add them back just add them back yeah
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:27 : then you're adding you're adding back
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:23 : before already had two existing children
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:51 : helpful
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:42 : found dead
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:10 : temporarily forget about this deleting a
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:21 : login
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:00 : login again
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:37 : I've been thinking about this and
39:39 : thinking about this and I don't have
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
50:22 : about that
50:24 : um are we at time we're at time we are
50:28 : at time maybe we can put that next time
50:30 : yeah I I don't want to rush this
50:32 : actually so let's talk about that next
50:35 : time uh this and this this is called
50:38 : um
50:40 : this is called a tree rotation
50:44 : tree rotation
50:47 : and I'll talk about this next time