Binary Search Trees: Part 2

Carol and I continue our lesson on binary search trees. This time we focus in on how to add a new entry to the tree.

Transcript

The following transcript was automatically generated by an algorithm.

00:00 : there's a mountain and you're skiing
00:02 : down the mountain
00:04 : you're not going to explore multiple
00:07 : paths because the only way is down so
00:10 : you only Traverse one of the many paths
00:14 : one of the trails I like this analogy I
00:18 : want to go skiing but
00:23 : so I guess we left off at
00:28 : we've seen how a binary tree can be
00:33 : traversed
00:35 : how you can add insert a new node into a
00:39 : binary tree then how you can find an
00:42 : existing value in a binary tree
00:46 : um
00:47 : and
00:49 : we haven't completed the crud I think we
00:53 : kind of we kind of did a hand wavy way
00:56 : of seeing how to create a new node
01:00 : um
01:03 : hold on
01:07 : um
01:08 : um oh and we didn't write down we talked
01:11 : about retrieval
01:13 : um I didn't write down
01:16 : the algorithm but the algorithm is
01:20 : basically
01:21 : you you kind of walk through it but
01:24 : basically the algorithm is
01:28 : um
01:30 : while
01:32 : while uh
01:35 : haven't well uh current node
01:40 : is
01:42 : not null
01:45 : and
01:48 : uh
01:50 : node value
01:52 : is not equal to the Target let's say
01:55 : like we haven't found it yet
01:58 : um
02:00 : then
02:06 : then if the current node
02:09 : is if the note that's called it no value
02:14 : if the note value
02:16 : England language it might be like
02:18 : current note that value or something if
02:21 : no value is if the target
02:24 : is
02:26 : is greater than the note value
02:31 : um
02:33 : then you then current node
02:39 : is the new
02:43 : dot is equal to the right child let's
02:47 : see
02:49 : uh else if Target is less than the no
02:53 : value then current node
02:56 : becomes the left child
02:59 : right that that that's more or less the
03:02 : algorithm
03:03 : there might be some details I'm missing
03:05 : but that's the idea and what is the Big
03:09 : O of this algorithm
03:11 : oh and and at the end if
03:14 : uh if they match or else then they match
03:21 : math
03:23 : uh well actually else it's not a match
03:28 : yet because the current note might be
03:30 : null
03:31 : so
03:33 : ah I'll just hand wave that as if Target
03:37 : is equal to no value then return current
03:43 : node let's say and then if you fall out
03:46 : of all of that
03:49 : uh
03:50 : else if
03:52 : no
03:54 : is no
03:57 : then return
03:59 : something like this sure
04:02 : um
04:04 : um it's actually a good exercise to code
04:07 : this up in whatever language you're
04:10 : comfortable with
04:12 : um but um
04:14 : I guess the what what is the big goal of
04:17 : this algorithm to retrieve a node in the
04:20 : in the binary tree I'm trying to think
04:23 : I'm going to try to think out loud on
04:25 : this one because
04:27 : I don't think it's
04:29 : Big O of in because
04:34 : is it Big O of like half of n because
04:37 : it's we're splitting everything in half
04:39 : in time like my where my brain is going
04:42 : is kind of like I know it doesn't it's
04:45 : not
04:46 : gonna grow
04:47 : in quite in step with the length or the
04:51 : size of our binary search trade but it
04:53 : is going to grow if we have a much much
04:56 : larger tree it's going to be larger than
04:59 : if we have a small tree but by but I
05:03 : Thinking by
05:04 : path
05:08 : try what by house
05:11 : by half it's a half of in I I don't
05:14 : think that's right actually
05:16 : um what is it oh is it the log yeah okay
05:22 : yes
05:24 : um that's the one
05:26 : um right so
05:30 : it it's login
05:33 : um
05:35 : and I would like to illustrate why
05:38 : um okay that would probably be good
05:41 : um so yeah the the bigger retrieval is
05:45 : login and
05:47 : the way to see why
05:51 : is this tree structure let's say you
05:54 : have a fully balanced oh it only works
05:56 : if it's a fully balanced tree if it's a
06:00 : completely unbalanced tree such as this
06:03 : one
06:04 : then it will be a big O of n
06:06 : because
06:08 : um because that's just like a linked
06:10 : list and you have to Traverse the whole
06:11 : link list sure uh so
06:15 : um but similarly to the binary search
06:20 : scenario
06:23 : um with each additional
06:25 : step we take and when I say step I mean
06:29 : the number of iterations of this while
06:31 : loop right uh with the with the binary
06:34 : search it was also like a loop right you
06:37 : you you go in a loop and in enter each
06:41 : iteration of the loop you shrink the
06:43 : search space in half right correct yeah
06:46 : so and we we call that the number of
06:49 : steps you take
06:51 : um so I use the word step here
06:54 : to mean each iteration of the loop
06:58 : uh and and in the case in in the case of
07:02 : the binary tree each step you take
07:04 : you're traversing down a level in the
07:07 : tree right yeah right like the first
07:10 : step you take you start from the root
07:12 : and then Traverse down one level to each
07:16 : child one of its children
07:19 : and so forth
07:21 : um so what I want to say is
07:25 : um
07:27 : um and just for succinct yes I uh I'm
07:31 : not going to draw the circles anymore
07:33 : um so
07:37 : um
07:38 : so like we have
07:41 : I've written out
07:45 : I want to draw a fully
07:50 : um
07:52 : balance and
07:55 : full tree
08:01 : oh hold on I messed up that that
08:04 : shouldn't be a four
08:06 : that should be like a nine or something
08:12 : eight
08:15 : data so
08:18 : um you can actually already kind of see
08:20 : the signs of uh
08:24 : of the exponential going on here because
08:28 : um
08:29 : if you count how many uh things are at
08:34 : each level
08:36 : so level one
08:39 : we have uh one node
08:42 : uh level two we have two notes
08:48 : and level three we have four notes now
08:52 : each time we're doubling right yes
08:55 : and if you go to level four we're gonna
08:58 : get eight notes and then sixteen notes
09:01 : and so forth
09:02 : so this is so the um
09:09 : so
09:10 : um the number of nodes
09:14 : there will be so the number again we're
09:18 : assuming a fully
09:21 : balanced tree
09:23 : and this may not always be the case so
09:26 : I'll caveat that
09:29 : um
09:29 : but we're if we assume the fully
09:31 : balanced tree
09:33 : then the number of elements that will be
09:36 : in a tree of level n
09:41 : it's like so the question is how many
09:45 : elements are in a
09:48 : fully balanced
09:52 : tree
09:54 : uh having n levels
09:59 : what was the answer to that
10:02 : so this is where my um my bad math
10:05 : skills are going to show themselves but
10:07 : we already have the first three levels
10:09 : calculated yeah but but as a formula
10:12 : yeah exactly it's a formula so it's like
10:15 : it's like
10:17 : okay so we don't know what n is
10:20 : we're like solving for n like n is
10:24 : unknown
10:26 : um but it should be
10:30 : so I know every every time we're
10:32 : doubling it every time we go through a
10:34 : level
10:35 : so what's the formula going to be if
10:39 : that's out
10:43 : ins
10:44 : Square it's not N squared
10:48 : I mean that's it's n Square for each
10:50 : level we go down correct but we don't
10:53 : know but we don't know how many levels
10:54 : we have
10:55 : uh right uh this might help uh if we um
11:01 : if we for now we'll discard level one
11:05 : that at level two
11:08 : we have two
11:11 : and then at level three I see the
11:14 : pattern I have two times two
11:16 : and then level four we have two times
11:18 : two times two
11:20 : and then level five we have two times
11:22 : two times two times two uh five times
11:25 : Etc
11:30 : so do you multiply two by itself
11:34 : uh that many times
11:38 : um and so that's an exponent certain
11:41 : exponential so that means it's two to
11:44 : the
11:45 : n
11:47 : okay
11:48 : two to the n
11:54 : 2 to the n
11:59 : and if I ask the inverse question now
12:04 : um
12:08 : how many
12:09 : how many
12:12 : levels
12:14 : are in a tree
12:18 : in a fully
12:20 : balanced tree
12:23 : that contains
12:25 : uh
12:27 : uh let's not use n this time that
12:29 : contains e elements
12:35 : what's the answer to that that's the
12:38 : exactly inverse question right
12:41 : is and so an element is
12:44 : just a number
12:46 : or it does it could be a person it could
12:49 : be anything but um yeah in simple
12:52 : example is a number
12:55 : so it's going to be
12:57 : the number
13:00 : to five we're going to be dividing
13:04 : by n
13:07 : no that's not right I'm sorry I told you
13:09 : my math skills are Rusty I need to I
13:11 : need to do some studying up here it's
13:13 : going to be the number of elements okay
13:14 : we've got the number of elements
13:19 : this is the well this is the exact
13:23 : inverse of
13:25 : um of the exponent the exponent so it's
13:29 : like
13:30 : before I was saying
13:34 : um
13:34 : if
13:36 : if the tree has
13:38 : three levels
13:41 : then you're gonna say
13:45 : um
13:46 : well to to the uh it's actually two
13:50 : minus two at two to the N minus one
13:54 : actually
13:56 : uh because
13:59 : um if it has one level
14:04 : um
14:05 : well okay
14:08 : um
14:09 : I don't want to confuse you too much but
14:11 : but for for level one
14:14 : it the answer is one because there's
14:17 : only one node oh hold on this is wrong
14:21 : sorry
14:23 : um
14:25 : how many elements are in uh
14:29 : okay so if if it's um
14:38 : I'm confusing two issues one one is how
14:42 : many elements are in that level
14:44 : but another is how many elements are in
14:48 : the entire tree
14:50 : and those are slightly different so
14:54 : level three there are four elements you
14:57 : can see these four numbers yeah
15:00 : uh but in a tree in the whole tree there
15:03 : are actually seven elements
15:08 : seven total let's say because we're
15:11 : adding up these three here as well right
15:15 : um and then there's a in level two if we
15:18 : don't count the third level we just
15:21 : pretend it's a tree that only has these
15:24 : three things then there's three total
15:27 : and then level one there's just one tool
15:32 : I kind of skipped over that and it tend
15:36 : to go too fast
15:38 : um and if we did one more level then the
15:43 : level four
15:46 : I'm not gonna draw them out just because
15:48 : it's tedious but level four would have
15:50 : eight elements
15:52 : but the total number would be eight plus
15:55 : what we already had which was seven
15:57 : which we would have fifteen dollar
16:01 : um Etc
16:03 : and the way you well the pattern
16:09 : might emerge
16:11 : um you might see it if you just look at
16:14 : it and realize that
16:16 : the other element like if you count the
16:19 : number of elements in a level say the
16:22 : third level there are four
16:25 : um the other elements in the tree is
16:29 : always going to be one less than the
16:32 : number of elements in that level
16:35 : um
16:36 : like this four and there's three from
16:40 : from the top
16:41 : and then if if it if it's level four and
16:44 : it has eight
16:46 : then
16:47 : there's going to be seven above it I see
16:52 : um
16:53 : and and so forth there might be multiple
16:57 : ways to arrive that at that conclusion
16:59 : but basically
17:01 : uh you might come up with the answer
17:04 : that it is you you double the number of
17:09 : uh elements at that level and then U
17:12 : minus one
17:18 : okay
17:19 : so we can do that as a four yeah I'm I'm
17:23 : very very uh slow with math I promise
17:26 : I'm sorry sorry Toby that's not helpful
17:28 : for this you know click on the feet I
17:30 : usually have to write it out and think
17:31 : and that's not a good thing but I have
17:33 : room to improve
17:34 : um let's see okay so that formula is
17:37 : makes a lot of sense so let's say we
17:40 : have okay how many levels are in a fully
17:42 : balanced tree that contains e elements
17:44 : we know the number of elements
17:46 : so we
17:49 : can
17:51 : so if if we had a lookup table yes then
17:55 : then it would just be a lookup to answer
17:57 : this question right
18:00 : if I wrote all of these things down
18:03 : sure then you you'll be like okay it
18:06 : contains eight elements okay
18:09 : 15.
18:11 : how many levels no it contains uh 15
18:15 : elements because this this 15 is what
18:18 : we're trying to match so right if it
18:20 : contains 15 elements then there needs to
18:24 : be four levels if it contains uh Seven
18:27 : Elements then there needs to be three
18:30 : levels
18:31 : um if it's greater than seven but uh
18:36 : less than 15
18:38 : it still needs to be at least four
18:40 : levels because there's some spilling
18:42 : over from level three
18:47 : so and and that uh the thing that
18:51 : expresses this relationship it's the
18:54 : inverse of this
18:55 : to uh uh to the end power
19:00 : uh equation
19:02 : and the inverse of the exponential
19:05 : equation
19:07 : is what do you remember okay because
19:11 : this we looked at this last time and we
19:14 : were like well
19:16 : if you plot this
19:19 : thank you the log the log is the inverse
19:23 : yes I do remember that sorry okay yeah
19:25 : yeah so so the the the exponential it
19:29 : looks like this yeah and then if we just
19:31 : flip this and then turn it 90 degrees it
19:35 : it looks like that
19:37 : so so this guy
19:40 : is the exponential and uh that other guy
19:44 : is the lock
19:46 : got it okay
19:48 : okay and and there are inverses of each
19:51 : other so so yeah so
19:54 : yeah so
19:56 : so this would be log a log base 2
20:01 : because we had the base of the exponent
20:04 : was two log base 2 of uh well e
20:09 : um
20:10 : so yeah log base 2 of e so
20:14 : um and this minus one that's just to be
20:18 : precise right but again when we're doing
20:21 : Big O we don't care about the little
20:23 : details like that so so at the end we're
20:27 : just gonna say oh it's a it's a log
20:29 : function
20:31 : um and therefore
20:33 : uh if you look at what the algorithm is
20:36 : doing
20:39 : at most it's going to travel the entire
20:43 : height of the tree right
20:47 : it's it's basically it's there's a
20:50 : mountain and you're skiing down the
20:52 : mountain
20:53 : through through one very narrow path
20:58 : you're not going to explore multiple
21:00 : paths because the only way
21:04 : is down is downwards so you'll only
21:08 : Traverse one of the many paths on the
21:12 : mountain oh one of the trails I like
21:15 : this analogy of skiing oh I want to go
21:18 : skiing but um
21:21 : um but yeah and and that is basically
21:23 : the height of
21:25 : the mountain or the tree
21:28 : uh and and now the height of the
21:31 : mountain right that's the number of
21:34 : levels of the tree
21:36 : and that is log
21:38 : base 2 of E
21:40 : and therefore
21:42 : uh the amount of iterations of this
21:46 : while loop that will have to do
21:49 : is at most the height of the tree
21:52 : and that is a log of N and therefore
21:56 : this algorithm's runtime is at worst
21:59 : Pico of log of n
22:01 : if we have a balanced strength I want to
22:04 : put a pin back in that and I feel like
22:05 : we'll Circle back around to it but yeah
22:09 : yes if if tree is balanced
22:13 : the more we talk about this the more I
22:15 : see like how important that is yeah
22:17 : exactly
22:19 : um
22:20 : so
22:22 : um and okay I think that was really good
22:25 : to like
22:29 : get into the details of that and uh see
22:33 : that
22:34 : about that uh so all about creating a
22:38 : nerd well
22:39 : creating a note is actually just binding
22:43 : the place where you're supposed to be
22:47 : and then and then
22:51 : and then sticking it
22:53 : uh under the node right so
22:58 : it'll be similar so basically spine
23:02 : uh the number you are closest to more or
23:08 : less
23:09 : which is going to be bigger of login
23:14 : uh using same same as retrieve
23:21 : and then you're just gonna
23:24 : add
23:25 : or to closest to or or
23:28 : at the bottom of the tree
23:34 : uh closest to which
23:37 : um
23:42 : let me think
23:48 : I'm thinking about the case of a
23:50 : collision and what to do in that case
23:53 : um yes
23:55 : I also had that question okay so if
23:58 : there's no Collision then it'll
24:01 : definitely go to the to a place where
24:05 : you're gonna be left with a no pointer
24:09 : right and then you can just say oh you
24:12 : oh you already had a null pointer so let
24:15 : me just
24:16 : stick myself in here where it used to be
24:19 : not okay
24:21 : um so maybe I should write this all out
24:24 : then
24:25 : um so
24:27 : while current node
24:31 : um
24:32 : is not no
24:36 : um
24:37 : if
24:38 : Target is greater than node value
24:43 : then
24:44 : current
24:46 : node is Right child
24:51 : uh if Target is less than node value
24:57 : and current node is left child
25:02 : who else if
25:05 : node is the node value what do you do
25:08 : oops
25:13 : um what do you do in this case
25:15 : um
25:16 : let me think I think you can
25:19 : choose to go either left or right I
25:23 : believe
25:24 : let me see what would happen
25:28 : huh
25:32 : I think that can work
25:35 : either way yeah in in some system like
25:38 : you depends on your application so for
25:42 : some applications you don't want to
25:44 : allow duplicate values at all sure like
25:47 : like well this needs to be a primary key
25:51 : right uh we we don't want any duplicates
25:54 : so maybe you just throw an error but
25:56 : let's but if you did want to allow
26:00 : duplicate values then
26:03 : like let's say we wanted to put
26:06 : the value 12 into this tree again
26:09 : and then you'll say like
26:12 : uh well 12 is equal
26:16 : um uh okay you can but we still have to
26:21 : put it in the tree somehow so I don't
26:23 : care I go left or go right you either I
26:27 : could see like you randomly choose but
26:30 : uh you could also just like
26:32 : deterministically say well if it's equal
26:34 : I also go left
26:37 : and then if you did go left
26:40 : then you end up putting the new 12.
26:46 : new 12.
26:47 : uh no the 12 will go oh it's greater
26:51 : yeah I'm sorry yeah yeah
26:53 : totally missing that it's
26:55 : yeah the new 12 will go here yeah and
26:58 : let's say if you wanted to put in 12
27:01 : again
27:02 : then you yeah go okay go left and then
27:06 : go right and then you go left and then
27:09 : the new 12 will go here
27:13 : Etc
27:17 : so you just will end up with a bunch of
27:19 : 12s that are clustered yeah but but you
27:23 : can only add things at the bottom of the
27:27 : tree in this oh not necessarily the
27:29 : bottom but you can only add things at a
27:31 : place where
27:34 : to there's a note that is a leaf these
27:37 : are called leaves okay like they are
27:40 : they don't have bow tie of their
27:43 : um children's set to something already
27:46 : so these guys are called so you can only
27:49 : add yourself under a existing leaf
27:54 : and so so I guess
27:57 : if we go with that approach then you can
28:01 : say if
28:04 : you know if it there then also go to the
28:07 : left
28:10 : left or maybe like this is less than or
28:14 : equal to then we go to the left
28:18 : and then else
28:21 : uh
28:22 : uh no there's no else because
28:25 : um
28:28 : because we covered all the cases it's
28:31 : either greater than or less than or
28:33 : equal to and if it's a null then we're
28:36 : gonna jump out of the while loop
28:39 : uh
28:42 : uh and then I guess at the point at
28:44 : which
28:45 : you jump out of the while loop
28:50 : well that's kind of a problem actually
28:53 : we're gonna need to
28:58 : no I don't want to expose too much
29:01 : of the nitty-gritty but sure parent will
29:05 : need to have a parent note of the
29:08 : current note maybe we can in some tree
29:11 : implementations
29:13 : you can get you can
29:16 : get at the parent node if you have the
29:18 : current node I see
29:21 : let's let's just hand wave and say you
29:24 : can do that
29:25 : but although you if you couldn't do that
29:28 : you could just keep track of what the
29:30 : parent note was while you're doing this
29:32 : Loop stuff right true true yeah so I'm
29:36 : just gonna say parent no then parent
29:38 : node
29:40 : uh
29:43 : uh oh shoot
29:50 : but I didn't I don't know which whether
29:53 : I went left or right from the parent
29:56 : node
29:57 : so
29:58 : so like Japan uh
30:02 : uh left or right child
30:05 : will equal to a new node
30:09 : with the Target value
30:14 : um and I'm hand waving that
30:17 : uh the either left or right trial
30:20 : depending on which direction I went down
30:24 : for the previous turn if that makes
30:26 : sense to get to the current node I think
30:29 : I'm sort of missing something I want to
30:31 : sort of talk through this create okay
30:33 : that you've you've laid out here okay so
30:38 : we we have to create a new note
30:41 : I think maybe we
30:44 : okay maybe we should actually code it
30:46 : but uh yeah yeah talk through it first
30:49 : okay so we're trying to create a new
30:53 : node that's the objective okay so we're
30:56 : going to
30:57 : enter into a while loop what condition
31:00 : is if the current node
31:03 : is not null we we want you know to
31:06 : Traverse until we get to it null node
31:10 : yep the way we're going to do that is
31:13 : with our left foot let's let's set up
31:17 : the current note first so at the
31:19 : beginning we're going to say current
31:21 : node is equal to the root of the tree
31:28 : yep got it well that new
31:33 : Target
31:34 : but wait we have a Target what is the
31:37 : target this target was passed into the
31:39 : function okay Target is the node the
31:42 : value we want to create yeah
31:46 : maybe I should call it new value create
31:49 : maybe use the new
31:53 : value
31:55 : yeah that's that's good that's more
31:57 : clear
31:59 : okay so if the new value is greater than
32:02 : we're going to
32:04 : fall down into the right child if it's
32:06 : equal to or less than
32:10 : right yeah we're going into the left
32:14 : child
32:15 : um
32:16 : so we're going to keep doing that keep
32:18 : keep you know following that pattern of
32:20 : we go left or we go right based on our
32:22 : condition until we get to a null
32:31 : when that happens yeah because of this
32:35 : once we're at our null node we fall out
32:39 : of the while loop like you said and then
32:43 : we write our new value
32:47 : and replace replace the null value with
32:50 : our new value guess what I'm
32:53 : wanting to make sure I'm understanding
32:55 : is sort of what you're talking through
32:57 : here
32:59 : we need to understand our relationship
33:01 : to our parent node at this point there's
33:04 : a gap yeah we need to know whether I am
33:08 : the current node is the left child or
33:12 : the red child of the parent node
33:14 : oh well but but the current note is null
33:17 : that's the problem the current node is
33:21 : null because we already fell out of the
33:24 : while loop
33:26 : so so that that's the case where so this
33:30 : would be like we try to add 12 and then
33:34 : we go here and we go here we go here and
33:36 : then we go here
33:38 : to the left of the last 12. right and
33:42 : and then the current node is no because
33:44 : the last 12 has no left child currently
33:49 : and then we we're going to want to
33:52 : take the parent node and set its left
33:55 : child
33:56 : to the new node we're going to create
33:59 : for the tree
34:03 : so that's more or less what I'm saying
34:05 : so it it depends on whether we took the
34:09 : right uh
34:11 : path or the left path at the previous
34:15 : term
34:18 : so do we need to know hey I took the
34:21 : right path or hey I took the left path
34:22 : yeah so so one way to do it might be
34:26 : like we just keep a little Boolean
34:30 : left or right yeah
34:33 : and it doesn't matter what it starts off
34:36 : with uh
34:39 : Boolean
34:41 : and then yeah if we took the right side
34:44 : we'll say
34:46 : left or right oh I'm gonna call it make
34:49 : it a string actually
34:52 : okay
34:53 : I'll make it empty left or right if we
34:57 : took the right side we'll set it to
35:01 : left and now I said
35:04 : the left if right and then we at the end
35:08 : we can do a little if statement
35:11 : here to say if we previously took the
35:15 : left then we'll set parent note
35:17 : left trial to the new node but if we
35:20 : went right then we'll set turn no to
35:23 : right child instead
35:26 : something like that
35:27 : but I'm just trying to wrap my mind
35:29 : around why why this is necessary like I
35:32 : I I I understand that we need to know
35:35 : did we go left or right but why why do
35:38 : we need to know that why wouldn't we
35:39 : just either go left or right and then
35:41 : put the value in that place so oh the
35:44 : reason is because
35:45 : um let's say you have
35:49 : um let me see
35:51 : um
35:52 : let's say
35:57 : we had a value here
36:02 : to the right of 20 let's say 25 we had
36:07 : 25 here okay
36:10 : so 20 has a right child but no left
36:13 : child
36:15 : so and we want to add
36:18 : 18. okay so we're gonna come down here
36:22 : and we're gonna
36:24 : hit uh
36:26 : to hit this in this spot here
36:32 : um and we're gonna end up with the
36:35 : current node is null
36:38 : always gonna be no at the end of that
36:42 : while loop
36:44 : um and we're gonna know the parent node
36:46 : of the null is 20.
36:50 : uh but we we're gonna want to know to
36:54 : set the new note at the left child of 20
36:57 : and not the right child of 20 because
37:00 : the red child of 20 actually has
37:02 : something in it
37:03 : and if we set the red tile of 20 we're
37:06 : gonna replace the existing thing
37:09 : that
37:11 : that is 25.
37:13 : okay
37:14 : I think that maybe this was part of the
37:18 : whole process all along that I just
37:19 : hadn't really thought through yet is
37:21 : like we always need to know hey did we
37:23 : go right or did we go left you always
37:26 : have to know that no matter what and I
37:28 : we I we just haven't really talked about
37:29 : it yet
37:31 : maybe I don't know
37:35 : okay I think it'll be it will help to
37:38 : actually write out the algorithm
37:41 : uh although we will have 15 minutes
37:46 : um
37:47 : so let me think
38:13 : let me
38:16 : um
38:19 : or it might be because if I write I'm
38:23 : not sure writing it out
38:25 : would necessarily clear it up for you
38:28 : either
38:30 : um because we would run that and then
38:32 : maybe it works
38:34 : and you're like okay but that doesn't
38:37 : necessarily illustrate it either
38:40 : um
38:41 : hmm
38:43 : that there's actually multiple ways of
38:45 : implementing this algorithm in the way
38:48 : the way I chose
38:51 : might not be the cleanest uh but that's
38:54 : just because
38:57 : um
38:58 : I haven't
39:00 : uh thought out all the different
39:03 : but I just haven't thought ahead sure um
39:06 : just I just went into it but um but I
39:11 : think in a way that's good too because
39:16 : like
39:18 : I want to show the naive way because the
39:23 : naive way is more easy to
39:27 : um understand intuitively
39:31 : um so yeah the naive way is sort of like
39:37 : there you can also do it with
39:41 : um the recursive function where
39:46 : um
39:47 : let me think
39:49 : in either case I think it might be worth
39:52 : it might help to visualize it as this
39:57 : like
39:59 : okay I'm gonna draw another tree
40:02 : okay and then and then I'm gonna show
40:04 : you what it would feel like like I want
40:08 : to try to illustrate what it feels like
40:12 : to be the program
40:15 : that that is actually uh doing this uh
40:22 : um
40:23 : okay you have so you have a treat
40:27 : um and you know uh throughout it
40:32 : uh maybe maybe I don't go out again I'm
40:35 : gonna uh it's actually not super easy
40:40 : to just
40:42 : can I just do like this hold on
40:50 : oh that'd be too simple you could just
40:52 : pick that up
40:54 : there you go
41:07 : it works
41:09 : uh okay so so
41:14 : can I like is there like uh pointer
41:18 : function or something
41:20 : I can select all these guys and move
41:23 : okay
41:24 : all right that works
41:26 : okay so this is the tree that we're and
41:30 : we're gonna try to add
41:33 : we're going to try to add a 7 into the
41:38 : tree let's say now
41:40 : for us humans we can see everything here
41:44 : right but for a
41:47 : for the program that's looking at it
41:50 : traversing down the tree it can only
41:52 : look at node by node
41:55 : so
41:57 : it's kind of like
41:59 : um
42:01 : it can only see this
42:04 : yeah
42:05 : right and it's not allowed to see the
42:09 : rest of the tree while it's doing it and
42:12 : when when it's looking at this it's
42:15 : saying well current node is
42:20 : uh six
42:23 : um
42:24 : so and and my and my new value is seven
42:30 : right so so it's like well is it
42:36 : good which way should I go should I go
42:38 : left or should I go right well in this
42:40 : case I should go right mm-hmm and if I
42:43 : go right
42:45 : now I'm looking at this right yeah and
42:48 : and the current node is going to update
42:50 : to nine
42:52 : and again which way should I go the left
42:55 : or right uh in this case I should go
42:58 : left left yeah I'm gonna move the four
43:02 : out of the way here
43:05 : so I'm looking at eight so now the
43:09 : current node is eight yep and then it's
43:13 : like should I go left or should I go
43:15 : right uh and in this case is smaller so
43:18 : we're gonna go
43:20 : to the left and there's nothing here
43:23 : so here where there's not and we
43:28 : were supposed to like notate it like
43:32 : like this sometimes yeah so I'm looking
43:36 : this is a null value
43:38 : and I want to basically when I see a
43:41 : null value then I know I should put
43:44 : myself here
43:45 : I should replace this null value
43:49 : with myself with my new value yeah well
43:51 : technically I have to like generate a
43:54 : new node first and then stick stick the
43:57 : new value inside the new node and then
43:59 : put it here but the problem is
44:03 : um the way of putting yourself
44:06 : in this place
44:08 : is you actually have to ask the parent
44:11 : note the eighth note
44:13 : hey can you
44:15 : make your left child refer to my new
44:20 : node
44:21 : so that's the problem
44:23 : right and if if when you're in this
44:27 : limited view
44:30 : if you don't have access
44:33 : to the parent node then you don't have a
44:36 : way
44:37 : of attaching yourself to the tree first
44:40 : of all which is why you need to have
44:43 : access to your parent somehow
44:47 : if you do get to this place
44:50 : um
44:51 : um and then secondly have an access
44:53 : having access to the parent is not
44:55 : enough because you need to know whether
44:57 : you should insert it yourself to the
45:00 : left or the right of the parent
45:04 : okay so it's like when you're
45:07 : the program and you're on eight your
45:10 : current note is eight
45:12 : you know I have a left path and a right
45:15 : path I can ski down here you do you say
45:18 : okay my new value is seven so I know I
45:21 : need to ski down my left path right then
45:24 : you get to the bottom of that and you
45:26 : have you have no more memory of hey am I
45:28 : on the left you're around the right
45:29 : exactly because you're there now that's
45:32 : exactly what it is so so what you could
45:34 : there's multiple strategies for how to
45:36 : do this like one strategy would be like
45:41 : well okay maybe instead of skiing down
45:45 : here to this no value I'm gonna do
45:48 : everything up here while I still can
45:52 : that's one strategy well that would mean
45:55 : you would add logic to say well if my
46:00 : left child is no then go ahead and stick
46:02 : it in there
46:04 : or if you choose to go right then
46:07 : instead of like moving to the moving the
46:11 : whole frame to the right or moving the
46:13 : whole frame to the left you're gonna say
46:15 : oh if the left side is null and you know
46:20 : then just stick yourself just change
46:23 : your left reference to that
46:25 : if you are planning to go left anyway
46:28 : and ins instead of moving the frame then
46:32 : just attach it yeah you're gonna need a
46:35 : couple more if statement to your code to
46:38 : do that right
46:39 : so it's a it's a trade-off
46:42 : um or
46:43 : what you could do is say
46:46 : uh you know what I'm gonna keep track of
46:49 : who my parent note is
46:53 : that can and if I am on this Frame then
46:56 : my parent node is nine right and I'm
47:00 : gonna also keep track of you know
47:03 : uh my how I got here uh
47:08 : so like relationship
47:12 : relation to parent
47:14 : is left
47:18 : and if I had those two pieces of
47:20 : information inside this Frame then I
47:23 : would know what to do then then if I
47:25 : move down to this Frame and then the
47:27 : current node was null
47:30 : and now I have the parent node and I
47:34 : have the relationship to parent is left
47:36 : then I know okay I should take my parent
47:40 : note and set its left child to the new
47:43 : note that I'm gonna create
47:47 : yeah I'm the I'm I'm understanding my
47:51 : brain's there finally
47:54 : so uh so that's uh
47:58 : that's uh I I think this yeah if this is
48:01 : like uh your first time learning about
48:04 : this data structure
48:07 : uh yes it is it's kind of like yeah I I
48:10 : I'm envious of you
48:13 : it's like that to be seeing this for the
48:16 : first time
48:18 : um
48:18 : I do vaguely remember like the first
48:21 : college lecture that uh I saw about this
48:26 : and uh it was like really weird really
48:30 : kind of foreign to me
48:32 : uh but uh kind of interesting but I
48:36 : didn't totally get the implication of it
48:38 : either even after that entire course
48:41 : even after years later uh I didn't
48:45 : really get it
48:47 : um yeah
48:48 : yeah so far to me this is the coolest
48:51 : data structure we've looked at for some
48:53 : reason I just really like it I think
48:55 : it's very beautiful I think it it
48:57 : reminds me of
48:59 : it's like this intersection of of
49:02 : artistic and
49:04 : and very practical like I don't I can't
49:07 : even describe it but it's a really cool
49:09 : data structure I'm excited to to
49:11 : continue learning about it yeah yeah
49:13 : yeah we can go further
49:15 : um so since we only have a few minutes
49:17 : left I'm going to go uh just like Zoom
49:21 : back out a little bit and look at the
49:22 : big picture
49:24 : um and to say that
49:27 : I actually uh on my YouTube channel I
49:31 : previously did a
49:33 : uh
49:36 : did a video with huichi about how
49:39 : databases work okay and
49:43 : and um
49:47 : very very much related to this concept
49:51 : um although databases don't use binary
49:55 : trees
49:56 : they use something that's called a b
49:59 : tree
50:00 : uh
50:02 : that's almost a binary tree but uh but
50:06 : uh the concept of the vitri is is still
50:10 : similar to the binary tree it's just
50:12 : that each node in the tree
50:14 : the binary tree has a fan out of two
50:18 : whereas a b tree can have any amount of
50:21 : fan out
50:23 : ah so so a b tree can have each node
50:29 : let's say uh I have eight eight elements
50:34 : in each node of the tree
50:39 : and in a b tree I don't know they
50:42 : probably use some Power of Two
50:46 : like 8 16
50:48 : 32 64. stuff like that
50:53 : um so I have eight things in the tree
50:56 : and each thing has a number in it or or
50:58 : well usually it'll be a record of some
51:02 : sort that has additional information but
51:04 : it'll have a key and the key is the
51:07 : thing that we're gonna sort by right
51:11 : we're gonna use it to decide whether
51:13 : we're gonna go to the left or to the
51:15 : right
51:16 : but
51:19 : um let's say
51:20 : you know do you have a key of one
51:24 : and then
51:26 : five
51:29 : eight
51:34 : uh
51:36 : come on
51:37 : what's going on oh I don't have to do
51:39 : this I can just
51:41 : 12
51:43 : uh
51:45 : 30
51:47 : 40 50. uh and then you're gonna fan out
51:52 : basically
51:55 : do eight more of these guys
52:00 : and well I'm gonna run out of room
52:03 : because it it because there's like eight
52:06 : more of these guys and each one is Big
52:09 : right
52:10 : yeah interesting
52:13 : um
52:14 : and Etc uh okay it's gonna be too
52:18 : tedious for me to do sure but but you
52:20 : just yeah just imagine there's um eight
52:23 : more and then at the next level
52:26 : still will be uh eight times eight which
52:29 : is 64. so at level three there's already
52:33 : 64.
52:35 : eight cell boxes
52:38 : um
52:40 : and which means
52:42 : um which every level
52:45 : you're so so this would be like um
52:49 : eight to the n
52:51 : instead of 2 to the n
52:54 : so it um
52:57 : so if you have a tree of n levels you
53:01 : will have eight to the N Things
53:04 : have eight to the N uh notes in the tree
53:09 : um
53:12 : but each node actually has eight
53:15 : elements in it
53:17 : it's it's yeah so which means the amount
53:23 : although the amount of processing you
53:25 : have to do
53:26 : at each node is greater
53:29 : because you not only choosing to go to
53:33 : the left or right you're choosing
53:35 : between eight different paths to go down
53:39 : and in order to do that you're gonna
53:41 : have to go through like you start with
53:43 : the first cell and you figure out if the
53:45 : target is in between one and five
53:49 : and then you figure out if the target is
53:51 : in between five and eight until you hit
53:54 : the correct uh range and then once
53:57 : you've hit the range then you go down uh
54:00 : that
54:02 : that trail that okay yeah
54:06 : um so that's uh that's B trees but I
54:12 : think
54:14 : um maybe a good analogy to this is like
54:18 : uh in a library you organize things
54:22 : usually by the first letter right
54:27 : so you can imagine there's a shelf for a
54:31 : a shelf for B
54:33 : Etc right right and and those are your
54:35 : ranges at the top at the top level maybe
54:38 : the bin one is or the ace and Bin two is
54:43 : all the B's Etc and maybe some there's
54:46 : some letters that are not as popular so
54:49 : you jam multiple ones together or
54:52 : something like X Y is z
54:54 : can all go on that one x y z shelf or
54:58 : something like that
55:01 : um and so you organize them in ranges
55:05 : but but it could be when your library
55:07 : gets really big then
55:10 : instead of shelves
55:13 : you have sections and each section has
55:16 : multiple shelves in it right yes
55:19 : so you have instead of an a shelf you
55:22 : have an a section which is an entire
55:25 : room
55:26 : and then inside that room you have to
55:29 : stop stop uh organize it that's your
55:33 : level two right and then you and then
55:36 : you organize the shelves inside the a
55:39 : room by the second letter of the uh of
55:43 : the author's name or something like that
55:45 : right sure yeah and and that's kind of
55:49 : what you're doing with with the beach
55:51 : and even with the binary tree you're
55:53 : kind of doing it that way you're just
55:56 : saying like well everything that's
55:59 : like less than six it can go into this
56:03 : side of the building
56:05 : greater than six it can go to the other
56:07 : side of the building and then I'm gonna
56:10 : subdivide it's it's just because like in
56:13 : computers everything's more Dynamic than
56:15 : the physical space so you can just sort
56:19 : of reorganize things and change them
56:22 : very quickly and that's what the binary
56:25 : tree is doing
56:26 : but uh conceptually it's same as
56:30 : dividing up physical space and try to
56:33 : organize stuff within it
56:36 : cool I'll have to keep that in mind
56:38 : because that that conceptual analogy
56:41 : that's really helpful