Binary Search 2: Now with Trees

In this session I introduce the binary search tree, in a very roundabout way.

Transcript

The following transcript was automatically generated by an algorithm.

00:00 : but you're you're someone who's looking
00:02 : for that guy and you don't remember the
00:04 : spelling of their entire long weird last
00:07 : name so you just type in the first three
00:10 : letters of their last name and it would
00:13 : be nice
00:14 : to be able to find their phone number
00:16 : that way right you have the retrieval
00:19 : algorithm down now this algorithm is
00:22 : actually exactly the binary search
00:25 : algorithm it's like the the binary
00:28 : search tree
00:30 : completely solves the problem of like
00:32 : well how do we get our our data sorted
00:36 : in the right place because the rules of
00:38 : the data structure
00:39 : sort it for you so
00:47 : um so we we just learned about so last
00:50 : time
00:51 : we learned about
00:54 : um
00:56 : the binary search yes
00:59 : algorithm
01:03 : for a race oh it
01:06 : uh so
01:09 : um and
01:11 : thank you
01:13 : I want to think about like a generalized
01:17 : mechanism
01:19 : for storing and retrieving data and
01:24 : which is what we've been circling around
01:26 : with you know with linked list so I want
01:30 : to generalized
01:32 : mechanism
01:35 : for storage and retrieval
01:41 : um and we talked about like linked lists
01:46 : versus arrays and then last time we
01:49 : talked about you know a specific
01:52 : algorithm you can do with sorted arrays
01:57 : and the binaries now the binary search
02:00 : can only work on sorted arrays so that's
02:05 : something that
02:07 : uh like it was a requirement
02:11 : and it's a pretty big ask right like
02:15 : well how do you get an array to be
02:19 : sorted
02:21 : um and we could talk about array sorting
02:24 : algorithms and the big old have you like
02:27 : read about array sorting algorithms
02:29 : before I have I have it's been a long
02:32 : time it's been many many years but I
02:34 : went to a series of talks about it um
02:36 : one time early on in my in my education
02:40 : process for computer science do you
02:43 : remember the Big O the best the Big O of
02:48 : the best
02:51 : sorting algorithm no I don't remember
02:54 : them okay I'll just tell you well
02:59 : should I just tell you or uh let me
03:02 : continue the story well okay I'll just
03:04 : say how sorting
03:07 : erase
03:09 : is not fast
03:12 : I'll just say that now it it's when when
03:16 : I say not fast
03:18 : then what I usually mean is not better
03:22 : than big old van
03:24 : okay
03:25 : so sorting a like fast is when I if I
03:29 : say something fast
03:31 : I mean Big O of one or Big O of login
03:36 : that's what I mean when I say something
03:39 : as fast
03:41 : so sorting a raise is not fast
03:44 : and we may or may not dig into that this
03:48 : time
03:49 : uh but um
03:53 : so that's something so so which means
03:56 : which dramatically diminishes the value
03:59 : of the binary search algorithm
04:02 : because you're you're telling me
04:05 : in order to use this really really fast
04:08 : method
04:10 : you have to prep it first
04:13 : with something that's not fast
04:17 : and yeah and which makes the binary
04:20 : search much less attractive uh there's a
04:24 : second problem though with uh and and
04:28 : again I'm thinking about a generalized
04:31 : mechanism for storage and retrieval
04:34 : right
04:35 : so I would like for both uh
04:42 : storing new data and retrieving data
04:46 : both to be fast right
04:49 : sure so if
04:52 : and and now now we do have a thing that
04:54 : is fast for retrieving things like the
04:57 : binary search is very fast so like a
05:00 : phone book is um
05:03 : is a good
05:06 : um it's sort of
05:08 : uh reference
05:10 : point for for for like uh
05:14 : you know when you're thinking about what
05:17 : I mean by a generalized mechanism
05:20 : for like an application like a phone
05:23 : book and usually
05:26 : when you for simplistic for Simplicity
05:31 : is sake
05:32 : let's say you can use it you type in
05:39 : in a last name
05:42 : and then I I
05:45 : give
05:46 : you the phone number
05:49 : that does the phone book app okay yeah
05:52 : and and then it can do crud so can do
05:56 : crud
05:57 : which means you must you must be able to
06:01 : add in new phone numbers and along with
06:05 : the phone number the person's last name
06:11 : um
06:15 : you can delete entries you I guess you
06:19 : can update entries like they change
06:20 : their phone number so you can change it
06:23 : and uh and you can retrieve it right and
06:28 : I D ideally I want all of those
06:32 : all of those operations to be fast
06:34 : right
06:36 : right
06:37 : how how would you build that
06:40 : okay how would I build this
06:43 : well
06:46 : I would start with
06:49 : putting something in place
06:52 : um a structure in place whether it was a
06:54 : database or mocking a database depending
06:57 : well you don't have a database no
07:00 : database okay so how's the data being
07:02 : scored yes so the reason the reason I'm
07:06 : not giving you a database is because
07:09 : um
07:11 : I I want to motivate this uh this
07:15 : computer science algorithms because if
07:17 : you dig into what databases do
07:21 : uh they're using data structures
07:24 : I see I see okay so so the stuff the
07:27 : database there's a lot of things that
07:29 : database just do to make the credit fast
07:33 : in most cases but in this case
07:36 : uh we're trying to learn about how those
07:39 : structures work so we have to do it
07:41 : ourselves
07:42 : the names are
07:48 : names are going to be stored in an array
07:50 : I would assume since we're talking about
07:52 : array would that be the correct
07:54 : assumption
07:55 : yeah okay let's say so like we haven't
07:59 : have an array
08:01 : um
08:02 : what do you put in each cell of the
08:05 : array
08:09 : through it out here but my first thought
08:12 : is maybe I have an object
08:15 : that has
08:16 : the name and the phone number
08:19 : yep in it
08:21 : in each slot or in each bin
08:25 : right
08:28 : uh yeah
08:30 : so now
08:32 : so the key thing is so so
08:36 : just so we don't have to go through
08:38 : exhaustively but um how to
08:44 : um
08:46 : how to add an entry
08:49 : and how to retrieve
08:53 : an entry
08:55 : by last name because that was our
08:58 : original requirement
09:01 : what what are our algorithms going to be
09:05 : okay so to add an entry
09:09 : we're going to
09:12 : take the data that we're given
09:14 : put it into an object
09:16 : and then add it to the last available to
09:20 : add it to the end of our array is what I
09:22 : would I think we would add it to the end
09:24 : of the array so what is that push it to
09:27 : the end of the array
09:29 : um we'll just say in most cases it in
09:33 : most cases it's bigger one
09:35 : now let's just say it's bigger one big
09:38 : old one yeah I I can can agree with that
09:41 : yes so that that um
09:44 : action is going to be Big O of one okay
09:46 : so then to retrieve the entry by the
09:49 : last name is
09:52 : going to be a little bit more tricky
09:54 : because we have these objects with the
09:57 : name and phone number
10:00 : they're going to be referenced by their
10:01 : index number so we we have to use
10:04 : something to find
10:07 : we basically have to search through the
10:10 : array until we find
10:13 : the element that
10:16 : matches the name we're looking for
10:21 : um
10:23 : um which is
10:25 : how how long
10:33 : how long
10:35 : yeah yeah so I'll say that's not good
10:39 : enough because I want
10:41 : both operations to be fast not just one
10:45 : okay
10:46 : so back to the drawing board for number
10:48 : two so so so uh well may I just say like
10:54 : actually I should have written this down
10:56 : so attempt one
10:58 : one
10:59 : uh add to the back
11:05 : um and then uh search ho array
11:10 : or match so this is Big O of n
11:14 : and this is bigger one
11:18 : so this is not not good enough so
11:21 : attempt number two
11:23 : can we do something with
11:27 : the fact that we know about the binary
11:31 : search algorithm and and use that to
11:34 : make retrieval fast
11:38 : um yes we can so I was just sort of
11:40 : thinking that
11:42 : in Step One
11:45 : maybe we don't just add to the back of
11:47 : the array maybe we do something
11:49 : different maybe we attempt to
11:53 : sort it as we're
11:56 : you know
11:57 : like
11:59 : insert it
12:01 : inserted in a way that maybe insert it
12:06 : yeah inserted alphabetically
12:12 : uh by last name right yeah but I'm just
12:17 : trying to think through what that Big O
12:19 : would be for yeah what the steps would
12:21 : be I have to sort of think it out yeah
12:23 : I'll write it down to first so this will
12:26 : be a binary search Yeah by last name yep
12:31 : and this we already know is bigger of
12:34 : log and
12:35 : yep which we're happy with yes
12:39 : um so what is the Big O of inserting an
12:43 : entry
12:44 : and we're gonna assume that before the
12:47 : insertion
12:48 : it was already sorted
12:51 : okay we've been maintaining this the
12:53 : whole live in maintaining this the whole
12:55 : time and uh which would be perfectly
12:58 : fine if we started with an empty array
13:01 : and then we just kept maintaining it and
13:04 : every time we insert it we kept it
13:06 : sorted right okay
13:09 : but uh how how do you
13:12 : how do you do this though
13:15 : yeah that's what I'm thinking through
13:17 : right now I'm gonna just sort of talk it
13:19 : out
13:20 : um so
13:22 : the very first piece of data that comes
13:25 : through
13:26 : no matter what that name is it's it's
13:29 : going to be the first one so you put it
13:31 : into slot one
13:33 : um the second name comes through
13:36 : you have to see if the
13:41 : letters are greater or less than you
13:45 : have to do the comparison between
13:48 : what the
13:49 : existing record in the new record and
13:53 : either push it to the end
13:56 : it's greater than or
14:00 : push it to the front which would would
14:03 : be
14:04 : I don't know I guess deleting deleting
14:07 : the existing record
14:08 : shifting it over one adding your new
14:11 : record
14:12 : yeah you have to do the shifting thing
14:17 : that's that's true uh what if there's
14:20 : more than one thing in it yep so now you
14:24 : have two your third one comes through or
14:27 : let's just say you have five now we've
14:29 : skipped a few steps there's five names
14:32 : with values you you're adding a sixth
14:35 : you have to compare
14:38 : the new sixth value
14:41 : with
14:46 : okay so you would start you would start
14:48 : at one side or the other of your array
14:50 : right let's just say you'd start at the
14:52 : beginning you would say
14:54 : you compare it to the first value is it
14:57 : Greater
14:58 : or less than
15:00 : if it's
15:02 : if it's uh greater you're going to move
15:05 : on to the next value and say okay is it
15:07 : greater or less than than this value
15:10 : until you find
15:12 : the the slot that it where it needs to
15:15 : go like in between
15:18 : most likely it's going to be in between
15:20 : yeah so you're going to Loop through
15:22 : each value in the array and compare
15:25 : correct until you find the slot where it
15:29 : fits in correct and then once you find
15:31 : that spot you're gonna have to do some
15:34 : some shifting
15:36 : uh right may may need to shift
15:43 : um
15:44 : elements
15:45 : to the right
15:48 : hover by one
15:51 : and then we're gonna insert
15:54 : new element
15:57 : uh what do you think is the Big O of
16:00 : this algorithm
16:03 : it's in it's going to be in I think yeah
16:07 : yeah it's a bigger event
16:08 : yeah so this whole
16:11 : um
16:12 : well I guess this is bigger one but that
16:15 : doesn't really matter it's uh but this
16:19 : one is bigger than yeah and and this one
16:22 : is take over and
16:24 : well this is figure of one so at the end
16:27 : the whole thing is bigger event
16:30 : um I would say step B
16:34 : there's a faster way to do step B can
16:37 : you think of it
16:41 : is where We're looping through and
16:44 : comparing oh could we use we could use
16:48 : binary search exactly what's that B all
16:51 : right we could just yeah yeah so I'm
16:54 : gonna
16:56 : uh I'm gonna line through this guy
16:59 : okay and uh yeah exactly we can do use
17:03 : binary search
17:04 : uh be
17:06 : Prime
17:08 : is um binary search to find
17:15 : uh the slot
17:18 : which is going to be a bigger login
17:22 : okay unfortunately step C is still gonna
17:26 : be pick up and so so from a theoretical
17:30 : perspective we do not really improve and
17:33 : even though we improved one of the steps
17:37 : um and that's a problem so it's still
17:40 : not good enough basically is the problem
17:44 : um
17:46 : let's take a step back
17:49 : uh
17:52 : uh can you think of a yet another
17:58 : solution to this problem which might
18:01 : have which might be
18:03 : um might solve this for us we're both
18:06 : operations are fast
18:15 : um
18:18 : we're trying to think of another
18:22 : solution to item one which is inserting
18:27 : alphabetically
18:30 : the inserting alphabetically
18:37 : foreign
18:42 : there was another data structure that we
18:44 : learned about before okay that we can
18:47 : use here
18:49 : we need to talk about hashing
18:52 : um hash tables yeah and we use a hash
18:55 : table here
18:58 : um let me think about that yes I think
19:00 : we can
19:03 : yeah
19:05 : how would that look like if we use the
19:08 : hash table for this
19:11 : to refresh my memory on the hash table
19:13 : real quick um
19:15 : so with the hash table we have
19:23 : basically everything is inside instead
19:26 : of being okay I might be wrong about
19:28 : this actually in instead of with the
19:30 : hash table our values aren't stored in
19:33 : an array they're stored in the table
19:36 : which is basically a big object that's
19:39 : the way I think of it in my brain
19:40 : whether that's accurate or not I don't
19:43 : know
19:44 : um
19:45 : so we have our
19:47 : heat value pairs now so we're going to
19:50 : have
19:52 : I guess the last name as our key and
19:57 : then our value is going to be the phone
19:59 : number
20:01 : and then
20:10 : okay but these need to be alphabetical
20:12 : I'm still I'm the wheels are turning in
20:14 : my brain that we still need to maintain
20:18 : okay so so the alphabetical thing
20:24 : um
20:25 : um I didn't explicitly
20:28 : give that requirement okay
20:32 : um although
20:34 : it is relevant so
20:37 : I guess my explicit requirement was you
20:40 : type in a last name and then I'll give
20:43 : you the phone number
20:45 : okay
20:47 : um if that was the only requirement
20:51 : then
20:54 : uh you don't necessarily have to store
20:58 : it alphabetically
21:01 : um
21:02 : so let's just but although there might
21:06 : there is an advantage of storing things
21:09 : alphabetically
21:11 : which is that if you
21:15 : mistype the last name
21:18 : then you'll get the neighbors of the
21:22 : name that you typed
21:26 : um and or like if you if you try to type
21:30 : in
21:31 : just a partial name
21:33 : then you get all the things that match
21:36 : that partial name
21:38 : if you store that or you could get the
21:42 : things that match the partial name if
21:45 : you store things alphabetically
21:48 : um so maybe that's like an
21:51 : that's not a hard requirement but that
21:54 : could be
21:56 : like a good enhancement and actually
21:59 : that that will make a difference but for
22:02 : now for for now let's say we we don't
22:06 : require that if if we don't require that
22:09 : can you do it with the hash table
22:12 : yes so with the hash table
22:15 : we we're just going to
22:19 : do a check to see if
22:21 : the name already exists the name is our
22:24 : key so see if our key exists
22:28 : um yeah
22:29 : I I guess I'm I'm probably kind of
22:32 : Overkill here because that would be like
22:34 : hey if it already exists
22:36 : override the number and that would be
22:38 : like an update but that we're not
22:40 : talking about that right now so okay so
22:42 : if the name doesn't exist
22:44 : we add it we add it to the hash table
22:46 : yeah it's just uh if uh
22:50 : for this um oh if last name
22:53 : entry
22:55 : dozen exist because at the entry
23:00 : the new entry
23:03 : and then retrieval
23:06 : retrieval is just the lookup you know
23:08 : it's just you have your key and you you
23:11 : go grab your your item so it's it should
23:14 : the hash table solution makes a lot of
23:16 : sense in my mind like yeah okay
23:19 : what's the Big O of uh one and two
23:24 : of wanting to
23:26 : um the of one for one step one it's
23:29 : going to be Big O of one
23:32 : no
23:34 : and for two the same because it's just a
23:38 : search it's a retrieval it's a yeah yeah
23:41 : simple look yeah
23:43 : yeah so this is good this is I mean this
23:45 : looks like a that's the first Contender
23:48 : our first real Contender
23:51 : um so that's true uh hash table that's
23:54 : why hash tables are really uh
23:58 : a stable of computer science and
24:01 : databases use it
24:04 : um all kinds of applications use it
24:07 : um I mean if you're using JavaScript
24:10 : then and you're using a JavaScript
24:12 : object then you're using it
24:15 : um
24:16 : so yeah this is a this is a good
24:20 : Contender but uh because of the reason I
24:23 : mentioned before
24:26 : um
24:27 : it might not be the best for all cases
24:30 : so so yeah what if I want some kind of
24:34 : fuzzy search right like I I typed in
24:39 : I have a really long name
24:41 : well I don't and my last name is just
24:43 : two letters but uh but for someone who
24:46 : has a really long last name
24:49 : um you might misspell it so
24:53 : it would be nice to be able to type in
24:56 : or you you're not that person because
24:59 : you probably remember the spelling of
25:01 : your last name but you're you're someone
25:03 : who's looking for that guy and you don't
25:05 : remember the spelling of their entire
25:08 : long weird last name so you just type in
25:12 : the first three letters of their last
25:13 : name and it would be nice
25:16 : to be able to find their phone number
25:18 : that way right
25:20 : yeah um and with a hash table that's not
25:24 : possible
25:25 : you're just gonna get nothing if you
25:28 : misspell any part of the last name
25:31 : right it's an exact it's like it's
25:33 : looking for the whole
25:35 : the whole name is a piece so we we want
25:37 : to do some sort of we want the ability
25:39 : to do some sort of search where we find
25:42 : any last name with the three letters
25:45 : c-a-r you know in sequence we want
25:48 : everything to come back that has car in
25:51 : sequence
25:52 : all right so so we want so nil
25:54 : requirement
25:57 : so now that we have made now we have a
26:01 : winner we're not satisfied we're gonna
26:03 : change the yard markers uh every current
26:07 : we want partial Mark matches uh
26:11 : So like
26:12 : um
26:14 : maybe they type in Jeff
26:17 : and then if you it should be able to
26:21 : give you like Jefferson
26:24 : and stuff like that yeah um
26:27 : so
26:30 : um now
26:34 : I guess the reason I want to bring this
26:36 : up
26:38 : is that
26:39 : we could satisfy this
26:43 : with
26:45 : attempt to or not not satisfy but we
26:48 : could get the retrieval to be good
26:52 : with attempt two
26:55 : our solution too yes because
26:59 : um because the binary search
27:02 : we have a sorted array sorted by the
27:05 : last name and we can really quickly find
27:08 : the right place
27:10 : in all of our names
27:12 : and then and then you can just once you
27:15 : find the spot
27:17 : uh
27:18 : you can just like start there and then
27:22 : maybe go down until you don't
27:26 : have matches anymore
27:30 : um the the problem though still is
27:34 : the insertion is slow
27:41 : yeah that's the big problem and I'm
27:43 : still not sure what the solution is I'm
27:47 : still okay thinking the wheels are still
27:49 : turning no okay so I'll I'll
27:53 : tell you the solution
27:55 : um
27:56 : uh the solution is a tree
28:02 : so that's that's what we were building
28:05 : up to
28:06 : so okay
28:08 : so why do we want a tree well
28:13 : um so
28:15 : I'm gonna I'm gonna transform the sorted
28:19 : array into a sorted tree
28:21 : okay uh and I'll show you what that
28:24 : looks like so uh last time we had a
28:27 : sorted array
28:28 : oh I won't do so many numbers this time
28:31 : maybe like five
28:37 : okay and our numbers have to be sorted
28:49 : okay so what if
28:52 : again we we said that the biggest
28:56 : problem with the array
28:59 : is that if we want to insert a number
29:02 : into the middle of this array
29:04 : now I got a shift of the ones behind it
29:09 : over by one and that's a bigger of an
29:12 : operation
29:14 : um it's inconvenient
29:16 : what if we can dodge that problem
29:19 : entirely
29:21 : and this is how we're going to do that
29:24 : we're gonna say
29:29 : no maybe I should use a circle or trees
29:39 : I'm not gonna have uh five tree notes
29:44 : instead of uh five cells one two three
29:49 : hold on
29:51 : no too much too many
29:54 : go back
30:06 : um this is not a full tree
30:09 : that's okay that's okay we'll make it
30:12 : Fuller later
30:14 : um
30:15 : okay so wealth goes here
30:20 : it goes here
30:23 : 4 goes here
30:26 : 37 goes here
30:29 : and 22 goes here
30:32 : and
30:36 : um
30:41 : with binary trees uh each node
30:45 : can have two children
30:48 : but
30:50 : in some of these cases when they don't
30:53 : then they have a null value for
30:57 : uh for that child
31:00 : which can later be used so so like this
31:04 : one the in reality it has just no values
31:08 : for both of its children
31:10 : okay
31:12 : then we represent no values this way so
31:17 : although we don't we don't have to be so
31:19 : verbose about it so I won't draw the
31:22 : last layer
31:26 : um
31:26 : so so I converted this to a binary tree
31:31 : and now what this allows me to do is I
31:35 : can insert new element and and the way
31:39 : this tree is sorted is based on this
31:41 : rule
31:44 : um
31:47 : oh
31:48 : um
31:50 : the value of my left
31:55 : child
31:57 : must be
31:59 : less than mine
32:04 : and
32:06 : the value of my red trial
32:09 : must be more than mine
32:13 : those are the only two rules
32:16 : uh that so these are
32:19 : um
32:20 : in order so this are the rules in order
32:24 : for a binary tree
32:30 : to be
32:32 : a valid binary
32:36 : search tree
32:38 : so this is called a binary search tree
32:42 : to be to be more correct
32:46 : so we have a binary search tree
32:57 : okay so so now if I'm gonna insert an
33:01 : element
33:03 : um
33:04 : say 20.
33:08 : I can add that I'm going to use a
33:12 : different
33:13 : color
33:15 : I can add 20 here
33:25 : and
33:27 : and that I can do
33:30 : in Big O of login because how do I do
33:34 : that first
33:36 : um
33:39 : first I find the place that I should add
33:42 : the new value
33:44 : and that's done with the binary search
33:47 : algorithm so so big and and the funny
33:52 : thing is the binary search algorithm is
33:55 : embedded in this data structure because
33:58 : it's just like I want to look for 20 in
34:00 : this tree
34:02 : let's look starting from the root
34:11 : that's the root
34:13 : um yeah so
34:15 : is 20 greater or less than 12 oh it's
34:19 : greater than 12. based on these two
34:22 : rules I know that
34:24 : uh 20 must be in the right of 12 right
34:29 : so I go to the right side and I find 37.
34:33 : and then I say hey is 20 greater or less
34:37 : than 27.
34:39 : no it's less than 20 sorry less less
34:42 : than 37. so it's less than 37 so I go to
34:46 : the left of the left side of 37 to its
34:51 : left child and in this case I find
34:54 : nothing and if I find nothing and I want
34:57 : to insert something I can stick it in
34:59 : there
35:00 : okay
35:04 : um yeah so
35:09 : what what do you think about this scheme
35:11 : here
35:12 : I like it I like it it's very new to me
35:15 : I haven't thought very much about it or
35:18 : any about it before so now I'm wanting
35:20 : to um sit down with a piece of paper and
35:22 : and step through it like a whole bunch
35:25 : like my brain's going okay well what if
35:27 : you wanted to add 21 next where would it
35:29 : go like all the things like I just want
35:31 : to see it reaction I'll do that later
35:34 : okay cool uh yeah so
35:38 : maybe yeah what if so what if
35:42 : so I guess
35:44 : we could try different things yeah I
35:46 : mean it's your it's your session so you
35:48 : can ask whatever questions you want but
35:50 : I guess going back to the root of how we
35:56 : analyze data structures you know we look
36:00 : at like how do you create
36:03 : we look at the cut how do we do the crud
36:10 : um
36:10 : so for um for the binary search tree
36:15 : so we already saw an example of we we
36:18 : created a new 20 value inside this tree
36:23 : um
36:25 : and I I kind of hand waved over
36:30 : where to find the spot to put it
36:34 : um but but that algorithm is more or
36:37 : less the same as the retrieval algorithm
36:40 : so let's talk about the retrieval right
36:43 : uh retrieve
36:46 : a
36:50 : pipe in the tree retrieve so given
36:55 : 10 and then all of these notes could
36:58 : contain structures right that has
37:02 : multiple things in it
37:03 : sure like a person's last name and a
37:06 : phone number so you could also Imagine
37:09 : in each bubble there's a last name and a
37:12 : phone number as well
37:14 : uh but but if you do that
37:17 : um
37:19 : if you do that then one of them
37:22 : needs to be specified as the key
37:25 : okay because you can only sort
37:29 : the tree is inherently sorted right
37:33 : yes and when you have to either sort by
37:37 : the last name or the phone number but
37:40 : for our application we're going to sort
37:42 : by the last name right makes sense and
37:45 : if we're going to sort it alphabetically
37:47 : that means you know we will probably put
37:50 : Adam or it had last name Adams here
37:56 : you know and put put like Jefferson
37:59 : somewhere in the middle Etc
38:01 : yeah
38:03 : right okay so but but then yeah that's
38:07 : the key but under the key there could be
38:10 : other values like the phone number and
38:12 : even other pieces of information
38:16 : um so
38:17 : so yeah what is the retrieval algorithm
38:20 : maybe I'll just ask ask you can you
38:23 : write me if I ask for any number
38:28 : and it's same as the array index of
38:33 : method in the case of numbers anyway uh
38:37 : actually it works for anything so I
38:40 : wanna like in index of
38:44 : oh in this case there's no index
38:46 : actually I was about to ask about that
38:48 : yeah yeah no sorry so that was wrong uh
38:52 : so in this case we don't really have a
38:54 : concept of index so this would more be
38:57 : like
38:59 : and
39:01 : you retrieve the thing if it exists
39:05 : um in if like assuming that it has
39:09 : additional information like phone number
39:12 : Etc then you'll be able to get it
39:15 : um so this example is contrived in that
39:18 : we're only putting the numbers in there
39:20 : so there's no additional value but you
39:22 : could ask the tree
39:25 : uh this this number exists in the tree
39:28 : or not sure
39:32 : sure so so does does it yeah there's a
39:37 : number
39:40 : exist
39:42 : how would you do this
39:45 : Okay so
39:46 : does we're going to ask because
39:50 : eight exist
39:52 : so we're going to go to the moment maybe
39:54 : maybe I should just say find
39:58 : number
40:01 : find a number yeah and then and then
40:03 : maybe even though we don't have any in
40:05 : Associated data
40:07 : with that number
40:10 : you could still return the node
40:13 : uh
40:15 : I don't know okay yeah just just go with
40:19 : that find a number okay so I want to
40:21 : start with finding I'm just going to
40:23 : sort of Step through it mentally one
40:25 : step at a time and talk it out I'm
40:27 : starting with a number that I know does
40:29 : exist so we're looking we're saying hey
40:31 : do we have eight can we find eight in
40:34 : this
40:35 : tree so we're going to start at the root
40:38 : and then we're going to read the number
40:40 : that's at the root and say hey it's 12.
40:44 : and then
40:48 : we're going to ask ourselves is the
40:50 : target number greater less than or
40:53 : greater than 12 and since it's less than
40:57 : we know based on our rules that it's
41:00 : going to be to the right
41:02 : so we look down at the next node and
41:05 : there it is it's eight that that wasn't
41:07 : a very long example but that's okay
41:10 : um and then we can return whatever we
41:12 : need to return
41:13 : go left I believe
41:16 : oh sorry did I get it backwards yeah go
41:19 : left go left sorry sorry sorry yeah I'm
41:22 : really bad with left and right I'm a
41:23 : left-handed person and I always
41:26 : sorry about that okay so now we're going
41:28 : to look for
41:30 : oh sorry well I won't get ahead too far
41:32 : we found eight we returned it
41:34 : so now we'll look for something that we
41:37 : know because
41:38 : it's small doesn't exist we're going to
41:40 : look for
41:42 : um
41:44 : 86. so again we start at the root
41:49 : we find our number our root is 12. we're
41:53 : going to go
41:54 : to the right wait wait wait left
42:00 : no okay no hang on
42:04 : I'm getting mixed up because I'm looking
42:06 : at what's right left and right and then
42:08 : the screen is a mirror to me well you
42:10 : can say which number that is a child of
42:14 : 12. perfect perfect we're going to go
42:16 : into 37 because we know that 86 is
42:20 : larger than 12. it's going to go down
42:22 : that side the the left side
42:27 : um and then we're going to say our next
42:30 : node is 37 do our check is is our Target
42:34 : greater than or less than 37 well it's
42:38 : greater so we're going to go left again
42:43 : 372.
42:45 : or am I saying it backwards
42:50 : sorry yeah and we're going to go to 72
42:53 : and we're going to repeat the process
42:55 : we're asking ourselves again is my
42:58 : target greater than or less than 72
43:01 : well actually at this point I don't know
43:05 : where in the process it would happen
43:06 : when we get to 72 I think we we would
43:09 : probably know
43:12 : This is the End like there's no more
43:14 : that we see that the child nodes of 72
43:16 : are null oh yeah yeah I mean there's two
43:20 : ways of doing it
43:21 : um but um
43:24 : uh the
43:26 : if you have some time
43:29 : I would suggest
43:31 : uh implementing this algorithm yourself
43:33 : uh
43:36 : um but but essentially you're going to
43:38 : need to check
43:40 : that null pointer right
43:44 : right that child value check to see if
43:48 : it's no uh you could track it at the top
43:52 : level or check it
43:54 : you could say go
43:57 : go right here
43:59 : it you can say go right
44:02 : to go to the right child of 72 basically
44:05 : and then in the next step you could end
44:08 : up with the node is null
44:11 : then we would say hey our Target is not
44:13 : in this tree we we got to the null
44:16 : Terminus like and uh yeah no no it's a
44:20 : return nothing you turn off for the
44:23 : whole function
44:24 : um so that's how that's the like more
44:28 : succinct way to do it when when you're
44:31 : actually writing out the algorithm
44:33 : because you're not having to say is the
44:36 : left child no it's the right child no
44:38 : you're just testing at the top level is
44:41 : is the current note no
44:43 : and okay but uh yeah but but it'll work
44:47 : either way
44:48 : uh yeah so so visit yeah you have you
44:52 : have the retrieval algorithm down now
44:55 : um and um
45:00 : and it this algorithm is actually
45:05 : uh exactly the binary search algorithm I
45:09 : think I think it's pretty amazing
45:11 : um
45:12 : I actually didn't make this connection
45:15 : until years later like I learned my
45:18 : professor in college
45:20 : helped me this stuff
45:23 : and they never connected this to the
45:26 : binary search algorithm for a race for
45:29 : me
45:30 : um but they they are actually the exact
45:34 : same thing
45:35 : and and I think that's really cool
45:39 : um yeah
45:40 : uh yeah you see how
45:45 : it is
45:46 : it's like such in a such a different
45:50 : context though isn't it like whereas in
45:53 : one you're like traversing this tree
45:56 : but another one you're like
45:59 : moving pointers in an array it is
46:03 : visually it seems very different but
46:06 : they're so the same
46:11 : have to think about think about that one
46:13 : some more not that I don't believe you
46:14 : but just to like let it marinate in my
46:16 : brain and yeah yeah but it seems so much
46:20 : more intuitive here like yeah I feel
46:22 : like I was able to talk it out yeah
46:24 : actually this is just just to hammer
46:27 : home my point right
46:30 : like
46:31 : okay
46:33 : um this recipe here
46:38 : I'm gonna move it next to my array
46:43 : and then um
46:46 : I think this will pan out
46:49 : because the difference in the arrays
46:51 : doesn't really make a difference here
46:53 : because this 20 we never encounter 20.
46:57 : so so if we do a binary search on this
47:00 : array
47:02 : um
47:03 : first we're going to look at the middle
47:05 : right which is 12. yeah so we're like
47:09 : okay is the number 86 86 is greater than
47:14 : 12. so if you go to the right
47:17 : right
47:18 : okay there's there's two pointers yeah
47:21 : so I'm not let's not skip that but the
47:24 : initially basic initially we're like
47:26 : okay we have two pointers and then we
47:29 : went to the middle
47:31 : and then we did the comparison and we
47:33 : know it's in the right range
47:35 : so I'm gonna move the left pointer to
47:38 : the middle now
47:39 : and then uh in within the right range
47:42 : I'm gonna
47:44 : uh make a new middle pointer and that's
47:48 : going to look at 37 look note 37 yeah
47:52 : we're looking at 37 and then 86 is still
47:56 : greater than 37 so we're going to move
47:59 : to the right again and then uh and then
48:03 : basically we're gonna replace the left
48:05 : liner
48:07 : with the middle pointer and then uh
48:12 : we're gonna here in the tree we say
48:15 : we're looking at 72 in the binary search
48:18 : we probably could have stopped already
48:20 : because
48:22 : there's nothing in between these two now
48:25 : but um but if we could have decided to
48:28 : like let's just keep going
48:31 : and uh
48:32 : if we do the division it's either gonna
48:35 : point to 37 or 72. one or the other
48:39 : right and let's say it was 30 let's say
48:42 : it was 72.
48:44 : then we would be looking at the node 72
48:47 : and then we'll find out oh 86 is greater
48:49 : than 72.
48:51 : so it's somewhere over here but that's
48:53 : that's beyond the bounds of the array
48:56 : and therefore return not
49:02 : yeah not that way like I said not that I
49:04 : didn't believe you but it helps to sort
49:06 : of make a solid connection there that's
49:08 : really cool it's like the the binary
49:11 : search tree
49:12 : completely solves the problem of like
49:14 : well how do we get our our data sorted
49:18 : in the right place because the rules of
49:20 : the data structure
49:22 : sort it for you so that you can always
49:25 : use a binary search
49:28 : yeah it's already Aries
49:31 : it's tailored for the binary search
49:34 : which is why it's called the binary
49:36 : search tree
49:38 : um
49:38 : and out there okay we're getting low on
49:43 : time but um
49:45 : but there's a lot more to cover so maybe
49:48 : we could just yeah we could just
49:50 : continue
49:51 : next week uh but I guess the thing the
49:54 : thoughts I want to leave you well
49:56 : obviously we should Maybe cover
50:01 : no okay updating is pretty trivial once
50:05 : you know this stuff because re updating
50:07 : is just you find the thing and then you
50:10 : change the value right yeah
50:12 : and then deleting is interestingly
50:15 : deleting
50:17 : is the most non-trivial thing
50:21 : um
50:22 : uh creating is um
50:26 : even
50:28 : maybe can get a little
50:32 : complicated as well uh maybe but uh but
50:37 : the real problem is um
50:40 : the real problem is what if
50:43 : you
50:45 : have a scenario where you're inserting
50:49 : numbers into an empty tree
50:54 : and you insert them in order
50:57 : so let's say you have five numbers
51:00 : like one two three four five okay
51:03 : um and then you're gonna insert them
51:05 : into a empty tree and you do it in order
51:08 : so first you insert one
51:11 : and and then you you put
51:15 : one in a circle
51:18 : and then you insert two and when you
51:21 : enter two what you're gonna do uh well
51:23 : obviously you're gonna go to the
51:26 : right side of one
51:28 : and put it here
51:32 : yep
51:36 : and then when you insert three
51:39 : well you're gonna go to the right side
51:41 : of one and then you're gonna go to the
51:43 : right side of two again
51:45 : so you're gonna put three over here
51:50 : and then where is four going well four
51:54 : four is going here
51:56 : yeah
51:59 : and and then uh and then five oh sorry I
52:04 : put five there I jumped ahead four is
52:07 : going there and then five is going here
52:13 : then you get a tree that looks like this
52:19 : um what's the problem here
52:23 : it is still a valid tree it is still a
52:27 : valid uh binary search tree because it
52:30 : satisfies these two rules
52:32 : the value to my left child must be less
52:36 : than my M value if my right term must be
52:38 : more than mine so that still is
52:40 : satisfied for every node in the tree
52:44 : um
52:47 : there's a practical problem now
52:51 : is it I'm not at all sure that this is
52:54 : right but is it like now you have to
52:57 : search through
52:59 : more to get to your grade or not I don't
53:02 : know that doesn't seem right
53:04 : I'm not sure what the problem is not
53:06 : sure still thinking about it no
53:09 : that is right
53:11 : that's the problem yeah like you have
53:13 : you have now let's say you keep going
53:15 : like this and you get to
53:18 : 572 you have to search through all of
53:20 : those before you get to your large
53:22 : number exactly yeah what does this look
53:27 : like this doesn't look like a tree it
53:29 : looks like an array
53:32 : yeah exactly it looks like a linked list
53:34 : because we're not utilizing the left
53:39 : side of any of these notes so we don't
53:43 : get to
53:44 : we don't get to Partition
53:47 : our elements into two halves each time
53:52 : like like we just start at the largest
53:54 : number
53:56 : and start with five oh no that would be
53:58 : well no we can't do them in sequential
54:00 : order we have to mix up the order
54:02 : yeah when we're building our tree
54:05 : exactly or yes that that's a very key
54:09 : well that's one of the strategies
54:11 : which is um
54:14 : you randomize it when you're inserting
54:18 : into a tree you don't do it in order
54:21 : but um there are other strategies to
54:27 : um and this concept is called uh the
54:30 : balance of a tree like whether your tree
54:32 : is balanced or unbalanced and this is
54:36 : clearly very unbalanced tree
54:39 : and uh yeah so we'll explore this next
54:44 : time uh but but this is one potential
54:47 : problem with dealing with uh trees
54:52 : cool I'm excited to explore it some more
54:55 : next time