# Binary Search 2: Now with Trees

Published on Apr 22nd 2023Duration: 54:56Watch on YouTube

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