# Binary Trees: Part 4

Published on May 12th 2023Duration: 50:23Watch on YouTube

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: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:51 : the root
• 09:53 : but by having the root real actually do
• 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: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: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: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