Binary Trees: Part 4

In this episode: Carol talk about one aspect of self-balancing trees: tree rotation.

Transcript

The following transcript was automatically generated by an algorithm.

00:00 : shifting it down here
00:03 : oh okay
00:08 : so we we talked about self-balancing
00:10 : trees
00:11 : um
00:12 : uh
00:14 : and we took we went to the Wikipedia
00:17 : page for self-balancing trees and there
00:20 : was like multiple different
00:22 : implementations
00:26 : um like there was um
00:30 : there's like AVL trees
00:33 : weight balance trees
00:38 : uh red black trees
00:42 : is probably the most famous
00:46 : I'll do it like that oops I just had to
00:50 : only make that red
00:52 : I can't okay us
00:57 : um
00:58 : so well won't dig into too much detail
01:03 : um I would I'm gonna venture to say uh
01:06 : that all of them
01:08 : it do the same thing when it comes to
01:11 : number two
01:13 : okay we talked about how they detect
01:15 : when the tree is out of balance last
01:18 : time like very very briefly uh and we
01:22 : drew these weights
01:24 : um but um this time we're gonna talk
01:27 : about step two which is how do you fix
01:30 : it when you think the tree is out of
01:32 : balance
01:35 : um and that is pre-rotation so let's say
01:38 : you have a tree
01:42 : um
01:43 : zoom in a little bit more
01:48 : okay you have a tree and it's like five
01:55 : I don't want those three
01:58 : one
02:01 : four
02:03 : seven eight
02:08 : uh
02:10 : maybe just like this okay so it's hella
02:14 : balance
02:17 : um
02:20 : so this tree is out of balance we can
02:22 : clearly see it's it I guess it doesn't
02:25 : matter too much uh if there's eight has
02:28 : children or not
02:29 : uh in this simplest case we're gonna say
02:33 : it doesn't
02:35 : um so we're basically gonna edit the
02:39 : root of the tree
02:42 : um we're going to rotate and we're gonna
02:45 : say
02:47 : because the uh
02:51 : because the
02:53 : tree is too heavy to the left
02:56 : we're not we're gonna rotate
03:00 : to the right
03:02 : and make and make the left child of the
03:07 : root the new root
03:10 : okay so what that's going to look like
03:13 : is
03:15 : this I'm gonna promote him to becoming
03:18 : the new root
03:23 : so three is the new root now
03:28 : and
03:29 : three is uh and and we
03:34 : it this is might be hard to
03:37 : conceptualize in
03:39 : real life that uh the the former child
03:43 : is now the parent of the former parent
03:46 : they they reverse their relationship
03:49 : okay
03:51 : um but now there's a problem
03:54 : because
03:56 : now now three has three children
04:00 : one four and five
04:04 : what are we gonna do about that well
04:06 : okay that's actually easy because we we
04:10 : can be guaranteed that five
04:14 : five used to have two children three and
04:17 : eight right
04:19 : but we we took away its left child
04:23 : uh because that its left child becomes
04:27 : its parent now so we're guaranteed that
04:30 : five will not have a left child so we
04:32 : just put four under there
04:36 : and then this and then this just worked
04:39 : it's it's everything about this tree is
04:42 : still valid it follows all the the rules
04:46 : of uh
04:47 : the prerequisites for being a binary
04:49 : search tree
04:51 : and we just uh
04:52 : we rotated the tree uh to the right
04:57 : so that well in this case it didn't help
05:00 : that much because now we're like too
05:02 : heavy to the right
05:04 : that's what I was about to say what what
05:06 : was the point yeah just because this is
05:10 : like a small example like typically this
05:14 : actually would make a big difference
05:15 : well I mean it's not a big difference
05:17 : it's just maybe I should have done maybe
05:21 : let's try again
05:22 : let's try again and say
05:26 : um let me think
05:32 : so we're gonna have
05:35 : uh under under one okay under one we're
05:39 : gonna have two and then we're gonna have
05:42 : negative one
05:45 : [Music]
05:45 : um
05:48 : I guess we
05:51 : I guess like if
05:53 : like in that case it wasn't like two out
05:57 : of whack
05:59 : um
06:00 : you see
06:04 : maybe if we somehow started in a state
06:08 : there where
06:11 : doing a rotation will actually end up
06:14 : with a balanced tree
06:17 : how will we do that
06:21 : could we
06:23 : do we need to have it be much more
06:26 : lopsided on one side no I don't I don't
06:29 : think so I think it can just be very
06:32 : small
06:34 : um
06:35 : let me think
06:37 : I just need to imagine like if you
06:40 : rotated it
06:42 : uh like if I rotate it
06:48 : um
06:49 : um maybe maybe I added too much stuff
06:53 : okay
07:04 : like if I rotate it back to the left now
07:08 : it'll just it'll just be uh
07:12 : too heavy on the left again
07:15 : so I think what we want is we want to
07:19 : add more children to the right side of
07:21 : the tree to get the scenario we're after
07:23 : so let's say we have
07:27 : seven here
07:31 : now I have 10 here
07:37 : okay so now we're gonna rotate it to the
07:40 : left because the tree is too heavy to
07:44 : the right
07:45 : uh which means we're gonna promote five
07:48 : to become the root of the tree
07:51 : and then five is gonna be the parent of
07:55 : its former
07:57 : uh parent
07:59 : okay
08:00 : and then we're gonna
08:04 : actually I can do this yes beautiful
08:09 : like these just followed five up
08:13 : and then magically
08:16 : uh
08:17 : we place for here I believe yeah and
08:20 : then it's perfectly balanced in this
08:22 : instance yeah
08:25 : so that's a better example of where it
08:27 : actually helped the balance
08:29 : um so yeah that's basically what it is a
08:32 : rotation
08:34 : um like you should try to doing this by
08:36 : hand
08:37 : a few times
08:39 : um and the code so let's try to actually
08:43 : write this algorithm
08:45 : so
08:47 : um the the function
08:50 : let's say we had a function called
08:54 : rotate
08:58 : and you're given a root
09:07 : um
09:10 : move these away
09:15 : uh so what do you do here
09:19 : what is this
09:21 : how do you do this thing
09:24 : are you given the root that you're
09:26 : passed is that the current root or the
09:29 : new or the desire truth it's the current
09:31 : route so
09:33 : um okay so for example if I were to
09:35 : rotate right on this tree the root would
09:38 : be five
09:39 : and rotate right would mean I want three
09:43 : to be the new root
09:46 : so just the function
09:48 : have access to the whole tree or just
09:51 : the root
09:53 : but by having the root real actually do
09:56 : have access to the hook tree okay
10:03 : okay I'm still I'm just thinking
10:07 : um
10:08 : so by having the root you have access to
10:10 : the whole tree okay so because you can
10:14 : um you can Traverse it if you need it
10:16 : too in case you probably only need to
10:19 : deal with it at one or two levels deep
10:24 : so
10:26 : First You're Gonna
10:28 : take your root
10:30 : and remove it remove it from its slot or
10:34 : I don't know what the correct verbage is
10:36 : but remove it from its is it a leaf or a
10:40 : node
10:42 : um
10:43 : but in doing so can you just remove the
10:45 : root or does that
10:48 : collapse the whole data structure
10:51 : um
10:53 : when you see remove
10:56 : um delete it
10:59 : you wanna pick it out I want to delete
11:02 : it and then hold it hold the value of it
11:05 : in memory
11:07 : like like make note of
11:10 : um
11:11 : um I don't know I'm just sort of talking
11:13 : it out right here stream of
11:15 : consciousness
11:17 : um yeah so if if you remove it then
11:23 : um
11:24 : you can you can remove it but I think
11:28 : the thing you
11:31 : kind of wanna
11:33 : keep track of it's It's children
11:37 : probably
11:39 : um
11:40 : the right thing
11:42 : I mean you want to keep track of well I
11:46 : mean you you can create a new note well
11:50 : let me see
11:52 : I I don't know if at the end you
11:54 : actually end up removing any notes
11:58 : and at the end you end up with the exact
12:01 : same number of notes
12:03 : um
12:04 : because you're right we're not adding or
12:07 : deleting any notes
12:14 : immediately replace it yes I mean you
12:17 : can think of it that way
12:19 : um that like let's say we do that and
12:22 : then what
12:25 : maybe does that also mean we're gonna
12:28 : sort of delete these links
12:31 : and then we have like two orphaned sub
12:33 : trees like that yeah yeah it may be
12:37 : saddle okay but then we have to build it
12:39 : back
12:41 : so we have to so we know we're rotating
12:44 : right so we're going to take the child
12:46 : the left child of the previous root
12:51 : and create bring it into the root
12:54 : position and say hey you're the new now
12:56 : the new root but then you've got these
12:59 : abandoned children that are just sort of
13:01 : floating out here so I I don't really
13:03 : like this method I don't think that this
13:05 : is you could really
13:07 : you could just say hey you're the like
13:10 : the positioning in the diagram doesn't
13:13 : really matter in in abstract terms so we
13:18 : can just say yeah you're the new root
13:20 : now
13:22 : um
13:22 : and I think that is valid to do that uh
13:26 : let's see and then the other sub tree
13:30 : let's say
13:32 : oh come on let me
13:35 : select it and move it okay okay uh it's
13:42 : hanging out over here
13:43 : let's say uh so not now what do you do
13:48 : with this
13:50 : so now five needs to be the right child
13:54 : of the new root because they've swapped
13:56 : waiting on am I thinking about that
13:59 : right they've swapped places yeah you're
14:00 : right yeah okay so it now needs to be
14:03 : the right child so it needs to just take
14:06 : four away and put it there
14:13 : though it's like this is all easy to do
14:16 : when we're just looking at it on a piece
14:18 : of paper doing it by hand but in when
14:21 : I'm thinking about actually writing this
14:22 : as a function
14:24 : this that we're talking through it
14:27 : requires like
14:28 : so much it's gonna be so many variables
14:31 : of like okay now this is over here and
14:33 : what was this value and what what was it
14:36 : originally like it seems really messy
14:38 : and I don't like it okay
14:41 : uh I I agree yeah it could be
14:45 : 10 of um hard to put your mind around it
14:50 : um but
14:52 : I guess my experience is yes it's kind
14:56 : of messy
14:57 : the first few times you do it but uh
15:00 : once you really get it then
15:02 : you can actually write an elegant
15:05 : solution okay the same thing I was
15:08 : saying last time I was like to find an
15:10 : elegant solution is actually very
15:13 : difficult but but then yes you can
15:16 : recite the solution back that also
15:19 : doesn't necessarily mean you totally
15:21 : understand it
15:22 : um
15:23 : but uh but
15:26 : um Okay so
15:28 : okay I'm going with the mess
15:32 : let's do this let's start over
15:36 : um let's start over and maybe in this
15:40 : case we can
15:47 : okay
15:48 : let's start over and
15:52 : we're doing right rotate
15:55 : so three is gonna let's delete this
15:59 : stuff for now
16:00 : just to simplify this picture
16:04 : uh oh let's delete
16:07 : 7 and 10.
16:09 : and then so we after we rotate it'll be
16:13 : unbalanced to the other side
16:16 : um okay so now
16:18 : um
16:19 : let's think about what variables
16:23 : we might want to use well obviously
16:25 : there's the root yes
16:29 : uh I'm gonna call this to
16:34 : um let's just for convenience sake
16:38 : setup left and right left child and
16:42 : right child variables
16:44 : I guess I just call it left for short
16:49 : due to diagramming uh
16:53 : it's due to real estate
16:56 : um and then this is right
17:00 : so
17:03 : um
17:04 : so I guess what we could do like if we I
17:08 : just want the root to be I just want to
17:12 : swap left with the root right I could
17:15 : write
17:17 : [Music]
17:17 : um
17:18 : that would really be this the first
17:21 : wait
17:23 : do we want to swap
17:25 : let we want to put left
17:27 : in the root variable
17:30 : yeah we could just say root equals left
17:34 : and then now root is the left but
17:38 : um
17:39 : that's not enough and that that will be
17:42 : a problem because we would have
17:43 : forgotten what the original route was
17:45 : right we did that and we still need it
17:49 : so we should probably first set original
17:51 : root equals root sure
17:58 : and then root and then okay
18:03 : so now we've preserved both values and
18:06 : and the three is in a correct spot it's
18:09 : in the root spot now now so all right
18:14 : so we're gonna say
18:16 : uh I guess what we have done is that
18:20 : original root is also pointing to five
18:25 : but now root is actually pointing to uh
18:30 : three three yeah
18:32 : that's cool the the arrow will move when
18:35 : I move the oh nice thing
18:40 : how does it figure that out that's
18:43 : that's pretty slick okay
18:47 : um maybe I moved this guy over here
18:52 : so yeah we still know what the original
18:55 : route is and then we just said the root
18:58 : is now three okay now now what do we do
19:02 : okay so now
19:05 : um let's see now the root is three so
19:08 : now we want to set
19:10 : we want to grab our value preserve our
19:14 : value from right so we maybe want to say
19:16 : like original right
19:19 : equals right and then we want to set
19:21 : original root to right
19:31 : and then we want to say original
19:36 : set original root
19:39 : to write
19:41 : right hang on
19:45 : so I thought but maybe I'm
19:47 : I'm trying to visually visualize it
19:51 : literally what what are we trying to do
19:54 : with
19:55 : right again
19:58 : well
20:00 : oh wait
20:02 : original route should be set to left
20:05 : because they've swapped places
20:09 : yeah original
20:11 : uh wait
20:16 : you want five to be the right child of
20:20 : three right
20:23 : but it's greater than three so it can't
20:25 : be the right child or sorry it can't it
20:28 : can't be the left child yes I want it to
20:30 : be the right child yeah five to be where
20:33 : eight is and three to be or five is
20:35 : up five
20:37 : no you want five where four is
20:41 : okay I'm confused again
20:44 : because uh number four is okay because
20:48 : you want five well okay I mean
20:53 : uh
20:56 : okay okay
20:58 : depends on how you think about the
21:01 : operation I think uh but like
21:04 : maybe we're thinking about oh this guy
21:07 : can rotate
21:09 : but if if but that's actually maybe not
21:12 : the right way to think about it maybe
21:14 : that's uh misleadings and instead of
21:18 : thinking about this line rotating to the
21:20 : right
21:21 : maybe we should think about it as
21:25 : we took this whole thing
21:29 : oh can I select multiple
21:33 : command click
21:36 : shift click oh shift click okay
21:41 : think about shifting this whole side the
21:45 : whole right side of the tree including
21:48 : the root
21:50 : shifting it down here
21:53 : oh okay maybe that's uh that way maybe
21:58 : it helps more in writing diagram and
22:01 : we're gonna replace four
22:03 : with this whole thing
22:05 : I like that better that's easier to wrap
22:07 : the head around yeah yeah four you gotta
22:10 : go and then we're we're going in here
22:14 : okay that's what that's what's happening
22:17 : so
22:20 : um
22:21 : how what what let's let's start over
22:25 : redo this yeah I like that okay so
22:28 : basically we just want to say
22:30 : we want to cut out
22:33 : the root
22:35 : and its whole right side
22:37 : into a chunk
22:39 : and then remove four hold Four's value
22:44 : and stick the the subtree chunk
22:48 : there like stick like insert it yeah and
22:52 : then we just have to figure out what
22:53 : we're doing with that left child of the
22:57 : nude root
22:59 : so it's like we we hold the value the we
23:02 : we find
23:04 : our new route
23:06 : we're like okay we have our new route
23:09 : we take it the value of its left child
23:11 : and hold it somewhere
23:13 : you mean the right child yes I do I'm
23:16 : sorry if I left right my left right uh
23:20 : my left handedness is getting me yeah
23:22 : just see to see the before before yeah
23:26 : we're gonna hold four
23:28 : were yeah and tend to take four out
23:31 : really yeah like basically delete it but
23:35 : we want to preserve its value all right
23:37 : and then we want to take our subtree
23:41 : that we've sliced out and move it
23:45 : into Forest previous spot
23:48 : or or the original tree the original
23:51 : root kind of exactly originally we're
23:54 : gonna move it here yes yeah
23:58 : so now
24:00 : we just have four to deal with that this
24:03 : is yeah let's let's do um
24:07 : okay so how do you write that in code
24:11 : maybe like step one preserve the four
24:14 : how do you preserve the four
24:16 : so step one is actually we're given the
24:19 : root we want to find its
24:22 : left child
24:24 : so we know what the new route is going
24:26 : to be we know where our starting place
24:28 : is
24:29 : so we have to Define
24:31 : new root first
24:34 : so isn't that just root
24:38 : I thought root was five at this point
24:41 : the no it would change root to the left
24:45 : oh I see okay we didn't get rid of that
24:48 : okay okay we already have those two
24:50 : lines okay you're right so now we have
24:52 : root okay so now we want to say
24:56 : um
24:58 : root
25:00 : right child
25:02 : delete well before we delete it we have
25:05 : to store it in a variable so we have to
25:07 : be
25:08 : um
25:09 : I don't know
25:11 : uh
25:13 : yeah what do you call it uh maybe say
25:19 : this is a I don't know what to call it
25:22 : right right of left
25:25 : okay open okay and then we'll have this
25:29 : figure it out at the end but we just
25:31 : have the version of it
25:33 : our leaf
25:36 : there we go
25:38 : Leaf
25:41 : orphan leaf is I don't want to write too
25:45 : long because real estate
25:48 : um
25:50 : um so just just call it orphan
25:53 : it's an orphan uh is the root right so
25:57 : that would be four so we're gonna say
26:01 : orphan
26:04 : is this for
26:06 : okay and then we're going to delete it
26:08 : we're going to delete root right because
26:10 : we have to
26:11 : make room
26:13 : okay so it's kind of like setting it to
26:16 : null or something or yeah all right you
26:18 : could and I guess in JavaScript you
26:20 : could also say
26:22 : let's let's go there no
26:26 : yeah
26:28 : yeah all right so now that means we have
26:32 : this guy can come out here
26:36 : and uh yeah I'll leave this line here so
26:40 : that later on it
26:42 : uh so all right now what so now here's
26:46 : the the big question mark in my mind is
26:50 : I is there some mechanism for
26:54 : slicing a tree like it seems like there
26:56 : should be like I want to take
26:59 : five and all of its
27:03 : um
27:04 : write subtree
27:07 : and hold that like I want to hold that
27:09 : all together I want to preserve that
27:10 : subtree so that I can just plug it in
27:12 : but I don't really know
27:15 : how to do that
27:19 : for that
27:21 : no there's nothing to do to achieve that
27:24 : because um the tree is already
27:29 : the tree is already attached to its
27:31 : children
27:33 : okay so there's nothing you need to do
27:36 : to say
27:38 : take move this tree and bring along all
27:41 : of its children it will by default bring
27:43 : along all of its children okay because
27:46 : because it has pointers that's pointing
27:49 : to the children and unless you unset
27:51 : those pointers
27:53 : the children will come with it they're
27:56 : automatically grouped okay unless you
27:58 : actively remove that okay
28:01 : cool well so then the next step would be
28:06 : to
28:08 : get the value that we stored in original
28:10 : route in the very first step
28:13 : and to set it to reset root right
28:18 : of
28:20 : two five to a root right equals original
28:24 : root
28:26 : equals
28:32 : right
28:33 : so now
28:37 : this is exciting
28:40 : and we're gonna do this
28:42 : yep
28:43 : um except
28:45 : uh we still got this little line here
28:49 : um so this what is this no I don't I
28:53 : don't I didn't draw the arrows initially
28:57 : but um
28:58 : maybe in this case I should draw the
29:01 : arrows because
29:02 : um originally
29:05 : uh this this line was pointing this way
29:09 : and then this line is pointing this way
29:13 : okay
29:15 : um but okay we actually previously we
29:18 : didn't talk very much we didn't write
29:21 : out the algorithm for every little thing
29:24 : well we wrote the pseudo code kind of
29:26 : but not in this level of detail
29:30 : um
29:31 : maybe I'll give you an exercise to do
29:33 : the next episode
29:35 : Implement these things it'll be fun uh
29:40 : like like on on like when you have some
29:42 : free time
29:43 : I don't know try to work on some of
29:47 : these algorithms I think you enjoy it uh
29:50 : but uh but I guess the point of these
29:53 : arrows is to say
29:55 : it's the that's pointing to the child
29:59 : not the other way around
30:02 : um and usually that's how trees are
30:05 : implemented although there are
30:07 : there are some implementations of trees
30:09 : where they both can point to each other
30:13 : uh we're not going to do it that way so
30:16 : so which means
30:17 : if we're gonna move five down oh I love
30:21 : the fact that the arrow follows me
30:24 : this is so cool uh so
30:26 : if we move five down here
30:30 : actually five still thinks three is it's
30:34 : left child
30:36 : and and we we have like a neutral
30:39 : contradiction here like three things
30:42 : five is its right child but five thinks
30:46 : three
30:47 : is its left child
30:49 : so we need to break one of those links I
30:52 : think yeah that's what I was kind of
30:54 : getting at when I was thinking about
30:57 : um
30:58 : slicing five and it's whole right sub
31:02 : tree out so then we would be left with
31:05 : like two
31:06 : small sub trees that we could write I
31:09 : write did you mean left okay
31:11 : [Laughter]
31:14 : um no because I was thinking five five
31:17 : and eight eight seven is Right child
31:20 : they need to be this sort of
31:23 : they need to be cut cut out for the link
31:26 : needs to be removed between three and
31:28 : five and then we would just have three
31:31 : with a left child of one a five with a
31:34 : right child of eight and then four
31:35 : hanging out there all by itself so kind
31:38 : of the state I want to get into so that
31:40 : oh I see okay let's let's do that hold
31:43 : on hold on
31:45 : okay so so basically you want
31:48 : um this these guys
31:51 : uh by themselves yeah like the link
31:54 : between like yeah you just want to sever
31:57 : this link here yeah first exactly okay
31:59 : all right let's write the code to do
32:01 : that how do you sever this link
32:05 : um
32:06 : so I think we might need to back up the
32:08 : step let me see root we've set root
32:10 : right to null no we wanted to do that
32:12 : because that's removing the four we
32:14 : orphan is four is stored in the orphan
32:16 : variable then we set root right which is
32:20 : the right of three to null we want to do
32:22 : that
32:23 : okay so we need to get rid of that last
32:25 : step root right equals original root
32:28 : because there's things we have to do
32:29 : before we can do that
32:32 : um
32:33 : okay so in between the last two like in
32:36 : between can you see my uh I'll just
32:39 : insert another line here
32:42 : yeah yeah I can see your arrow now yeah
32:44 : here
32:46 : um you can type two I think okay you can
32:49 : edit this as well
32:51 : yes oh there we go yeah I sure can okay
32:55 : so in between these two steps we want to
33:01 : um
33:02 : and I'm just making up more attack
33:04 : because I honestly have no idea how this
33:06 : actually happened what the mechanism in
33:07 : code would be to do this but we want to
33:11 : like
33:12 : slice the
33:16 : tree we want to take
33:20 : five the note okay so we want to say
33:23 : original root
33:25 : like slice but that's probably not what
33:28 : it really is but you just want to unset
33:31 : its love child really
33:34 : onset original Roots left child yeah
33:38 : like the same way we unset threes right
33:42 : child four and take four out
33:45 : we can just do the same for uh
33:49 : for five and take its left child out
33:52 : some similar
33:54 : similar to this line here
33:58 : okay so we but it's no longer root it's
34:01 : original root now so we wanted to say
34:03 : like original
34:05 : root
34:08 : dot left
34:11 : will be equal no
34:13 : yeah
34:14 : so so that means or I just keep to the
34:18 : same way I was doing it visually that
34:20 : would mean
34:23 : wait it's not pointing to anything
34:26 : anymore
34:32 : so now we have exactly what I was saying
34:34 : we have three
34:35 : is these are like weird little
34:39 : bunny trees three it has one child
34:41 : that's one it's two it's right yeah two
34:45 : it's left to its left and then we have
34:47 : five it has one child and then we have
34:49 : our orphan four so now we're ready to
34:51 : rebuild I think these as six lines of
34:54 : code are are hey let's take this thing
34:56 : apart yeah yeah and now uh we also uh we
35:01 : also did this one which is root dot
35:05 : right is equal to ordinal root which uh
35:08 : we we did that already
35:11 : so that line will make this whole thing
35:16 : be pointed to
35:18 : by three yes it's in the right trial so
35:22 : so we're already here we're already here
35:24 : okay we're only uh one one step away
35:27 : so now we have to deal with our orphan
35:30 : yep so
35:32 : Okay so programmatically
35:35 : what we said we said this at the
35:37 : beginning that we know
35:40 : that we're going to have
35:44 : a null
35:46 : end point
35:48 : to the left of what was the original
35:52 : route because we've just removed like we
35:54 : can know that that's where our orphans
35:57 : always should go
35:58 : yeah well the the reason now now that we
36:01 : wrote out the code the reason we're
36:04 : guarantee that this original route will
36:09 : always have a room on its left side is
36:13 : because we set it to null right here
36:16 : honestly set it to know ourselves so
36:20 : that makes sense and I guess
36:23 : than the other thing the other question
36:24 : is how do we know
36:26 : I know we do know but how do we know how
36:29 : can we ensure that our orphan is always
36:31 : going to be
36:32 : greater
36:34 : than our original route
36:37 : so it can always you know go on to the
36:39 : left child well because it used to be
36:42 : the right child of three
36:46 : and that guarantees that it's greater
36:48 : than three
36:50 : it used to be here right and by by the
36:54 : rules of binary search tree it says your
36:57 : right child must be greater or equal to
36:59 : you thank you so
37:05 : okay so we know that but then our
37:09 : original
37:11 : sorry but it has to be less than
37:15 : it has to be less than the original root
37:18 : as well right right right
37:22 : in this case
37:24 : well we can see for his less than five
37:27 : but in general
37:30 : um we know that's true because
37:35 : it used to be like this
37:41 : it used to be like this and that so so
37:44 : for because for it is a part of the left
37:49 : subtree of five
37:51 : that guarantees like anything within the
37:54 : left subtree of five is guaranteed to be
37:57 : less than five
37:59 : okay
38:01 : true okay I'm I'm there I'm following so
38:05 : yes we can we can confidently say
38:10 : like programmatically it can always go
38:12 : there we know that will always be true
38:13 : so we the last step is just to set or um
38:18 : let's see
38:20 : um
38:22 : how what's the variable now that's
38:24 : identifying five
38:27 : original route original route okay so
38:31 : we're gonna say original root uh here
38:35 : wait okay all right
38:37 : we're going to say
38:39 : original
38:41 : root
38:42 : dot left wait is that right yeah left
38:46 : uh equals are you are you writing
38:49 : um yes can you see
38:51 : hold on I don't see your oh now I do
38:54 : okay cool yeah original route that left
38:58 : equals orphan yeah
39:00 : yes that's
39:02 : that put it there
39:06 : and I think that that's it I believe
39:10 : that I believe that works
39:12 : uh
39:14 : that's actually not as messy as I
39:16 : thought it would be it'll
39:19 : be and a lot of switching around but
39:21 : it's not too bad uh-huh
39:24 : yeah
39:25 : yeah I think that works out and um it's
39:30 : kind of like a neat exercise it's a neat
39:33 : clothing exercise I think
39:36 : um I wonder if they have it on lead mode
39:40 : let me look it up actually
39:47 : go away far
39:51 : I can't make this bar go away okay
39:55 : oops all right
39:58 : delete code
40:01 : uh tree rotation
40:07 : invert a binary tree no that's not what
40:10 : I want rotate function
40:13 : oh they don't have a problem for tree
40:15 : rotation okay I'm a little bit
40:18 : disappointed
40:20 : okay
40:22 : well
40:24 : um
40:27 : that that's cool I mean that I would say
40:30 : actually there's not too much more to
40:31 : say about tree rotation you would write
40:34 : a symmetric function to rotate it to a
40:37 : to the left
40:39 : um and then you just like you know if
40:43 : you're implementing your red black tree
40:45 : or your weight balance tree then you
40:48 : like when it's that time you think you
40:51 : should rotate it then you just call this
40:53 : function
40:55 : yeah
40:56 : that's pretty cool yeah like so
41:00 : yeah this was a good exercise oh oh hold
41:03 : on actually I didn't talk about maybe
41:05 : there's a little bit more to say about
41:06 : this so when do you do this
41:10 : when do you actually like
41:14 : like in the normal operation like
41:16 : because you're not gonna the programmer
41:19 : that's trying to use your like usually
41:23 : you write a implementation of a binary
41:27 : search tree and then as a library
41:31 : and then you let application developers
41:35 : use your library
41:37 : and and even even if you are not like
41:42 : you're not like you could be the same
41:45 : person that's using the tree sure um but
41:50 : you you still can think of it as you
41:52 : you're taking on different rows like
41:54 : sometimes your the library developer and
41:57 : other times you're the application
41:58 : developer
42:01 : um
42:02 : so I I think it will be weird to say
42:06 : oh well the the application developer
42:10 : sometimes has to call these rotate
42:13 : functions on the tree
42:16 : to make sure it's balanced
42:19 : and and also
42:20 : and also like
42:23 : it's not just you don't necessarily just
42:25 : rotate the root of the tree because
42:28 : sometimes the sub trees might be
42:30 : unbalanced
42:34 : yes and just rotating the root of the
42:38 : tree might not help all that much if
42:42 : say
42:44 : like let's say we had that um
42:47 : scenario we we had last time where it
42:50 : was like just
42:52 : uh one
42:55 : two
42:57 : three
43:00 : or
43:02 : five okay let's say we had this and then
43:05 : you're like oh yeah that's really
43:06 : unbalanced let's rotate the you know to
43:11 : a left rotation and and you would end up
43:14 : with
43:15 : this
43:17 : then that's better but it's still not
43:20 : great right
43:23 : um and and then also if you say okay
43:25 : that's still not good
43:27 : let's do another left rotation
43:30 : then you would end up with this probably
43:35 : which that would be good
43:36 : that would be better
43:38 : but still
43:41 : um
43:43 : like imagine this list was longer like
43:47 : it had 100 things in it
43:49 : and I just do a bunch of left rotates
43:52 : and then you would just have a v a very
43:55 : long V
43:57 : yeah and that's that's not a fully
44:00 : balanced tree and we're still not using
44:04 : you know the power of the logarithm how
44:07 : we can exponentially increase the number
44:11 : of elements we can handle just by
44:13 : increasing one level of the tree We're
44:15 : not gonna get that if all we do is
44:18 : rotate the root of the tree right
44:20 : so we actually want to sometimes rotate
44:25 : the uh subtrees the internal node as
44:29 : well
44:31 : yeah so is the question like when when
44:35 : does this happen like when yeah when
44:37 : when when do we call this uh rotate
44:41 : uh and so this doesn't have to be the
44:43 : root this could just be any node within
44:46 : the tree
44:47 : start starting node
44:50 : yeah yeah yeah so
44:53 : um so the answer is um
44:57 : you you do this rotate
45:00 : on an on-demand basis
45:03 : as your mod as you're editing the tree
45:06 : that's how you do it okay so like so
45:09 : like as you're adding a new node to the
45:12 : tree then you find
45:15 : you check to see
45:17 : whether I should do a rotation or not
45:21 : yeah that makes sense that's that's what
45:23 : I was kind of thinking yeah and or as
45:26 : you're right when you're deleting a tree
45:29 : and you're drilling down into some part
45:31 : of the tree and then you're like oh
45:33 : deleting it okay right after I delete it
45:35 : let's check the balance should we do a
45:39 : rotation yes let's do it
45:41 : um so that's generally how things go
45:44 : just like you're constantly checking
45:46 : your balance
45:48 : um anytime an edit is made yeah to the
45:52 : tree yeah that makes sense
45:56 : yeah so that's that's a self-balanced
45:58 : trees uh oh uh we'll talk about the tree
46:03 : traversal next time that sounds good
46:06 : what did you want
46:07 : you as an exercise just if we could
46:10 : touch on that real quick
46:12 : um you said write out
46:14 : um sort of like we did today write out
46:16 : the pseudocode steps for for but for
46:19 : what for something we talked about
46:21 : before
46:23 : um so
46:25 : but
46:28 : um let's say
46:32 : I would like to and this could be a
46:34 : longer term project uh I don't want to
46:37 : put stress on you because I know you
46:40 : you're busy
46:42 : uh at work but um maybe maybe the
46:46 : project is like build your own
46:49 : implementation of a binary tree
46:52 : okay
46:53 : okay it's always gonna have to be like
46:56 : that because
46:58 : um unless you do everything from scratch
47:01 : uh you you won't fully get the
47:04 : experience build a
47:07 : finally search tree Library
47:11 : it's basically that's what it is so so
47:14 : maybe number one is
47:17 : um
47:20 : design
47:22 : the data structure
47:25 : to hold the tree
47:27 : I'll just I won't write so wordy I just
47:31 : designed the data structure okay number
47:34 : two like uh just Implement Implement
47:38 : crud basically implement
47:41 : the crud operations
47:46 : uh which you know obviously has is a big
47:50 : thing because crud has a lot of stuff in
47:52 : it yeah um
47:54 : but the important thing is
47:58 : the sort of binary search algorithm
48:01 : based on the tree structure right but
48:04 : that's just a retrieval that's how a
48:06 : retrieval is usually done
48:09 : uh true traversal
48:11 : which we're gonna talk about next week
48:16 : um self
48:19 : balancing that's kind of more advanced
48:22 : as we talked about
48:24 : um sure so
48:26 : um but uh let me think oh maybe even
48:29 : some like more advanced
48:34 : hmm
48:37 : uh sub range
48:42 : searches
48:44 : like honest I wanna I have a whole tree
48:47 : filled with people people's information
48:52 : and I want to search you know I don't
48:55 : type
48:57 : gef and get everyone whose name starts
49:01 : with Jeff
49:02 : for example that's a sub range search of
49:05 : the tree or if it the key is a number
49:08 : instead of a string maybe I want I want
49:12 : to print out all the entries between 15
49:15 : and 17 or something like that okay
49:20 : um I have a question about step one yeah
49:22 : I'm a little bit I think I'm I'm missing
49:25 : something design the data structure
49:31 : the data structure is a tree
49:34 : like what do you mean design the data
49:37 : structure uh oh I mean how are you going
49:39 : to represent the tree in your
49:42 : programming language
49:44 : oh okay like I I and I'm not gonna even
49:49 : prescribe a programming language I will
49:52 : let you choose I don't care but uh
49:55 : depending on the programming language
49:57 : you choose the data structure could be
50:00 : very different
50:01 : gotcha okay
50:06 : okay so yeah think about and then yeah I
50:09 : don't want to put more stress on you so
50:11 : you can sort of do it at your pace and
50:14 : as as you're motivated to do it and then
50:18 : when you when you have something then
50:20 : show me okay