AVL Complexity

[00:00:00]
>> We'll do the other case, the arguably more complicated case. So let's do A, B, C. We'll have another Br, CL, CR, AL. So we're gonna do the exact same thing. We need to do a small rotation this way, followed by a large rotation this way. Now, technically, you can do this rotation in one maneuver, okay?

[00:00:27]
You can really be the top gun of maneuvering, but we're gonna keep it simple and just do it in a singular move or in two moves. It's just easier to reason about. So typically, what would happen is that B would come down, And C would come up. Now this would normally be fine, but since we have Br and CR or kind of in a little bit, our jimmies rustled now.

[00:00:51]
What do we do here?
>> Compare B to CR.
>> B to CR, exactly. What do we know about CR? CR is strictly greater than C. It is strictly less than B. Therefore, if it were to be moved over to here, and C moved up to here, well, it is still strictly greater than C, and is still strictly less than B.

[00:01:17]
We haven't broken any of the rules. So C's right goes to the rotation of B's left, and therefore, Br remains in the same position. We can get the hell out of here, C. And then we can put CL remains right there, because CL is still less than C, still greater than A.

[00:01:35]
And now we just do that final rotation of dropping down A down to here, keeping AL where it is. Now we need to do this, we need to think about CL. CL is strictly less than C, but greater than A. Therefore, CL can go right here, and B remains the way it is.

[00:01:52]
All right, we're feeling confident with our AVL experience here. All right, all right, I like this. This is fun? So there we go. Insertion just follows these rules. The moment you insert, you start from there and you just walk up the path recalculating the height. The moment you hit a violation, you just perform one of these four rotations.

[00:02:13]
So there's no real need to show these things, deletion works the exact same way too. Follow your three cases of deletion. Wherever your node ends, if you have to hop all the way down the tree, you need to perform a rotation. Wherever the deletion happens, you just walk up the tree looking for any violations, and then perform these rotations.

[00:02:29]
So pretty great, pretty simple, pretty exciting. I absolutely think AVL trees are just the greatest. They're just the greatest. Now what can we say about an AVL tree? Well, what we can say about it is that at some point, no matter how big it is, we'll only be out of balance at the root by either one extra level on the left or one extra level on the right.

[00:02:53]
So that's really important to know, which means that our height will be the log(n) +1, potentially, right? And since this is computer science, we don't deal with constants. Get the constants out of there, okay? We don't even think about it. So it's always a log n search. That means also we have to potentially go down the tree on insertion, which is log n.

[00:03:20]
But we also have to go back up the tree, which is log n, which means we have 2logn. Which means if we're really fun with math, we can say we have log n squared, but don't wanna do that, that's just ignorant. You definitely don't wanna do that, instead, it's a constant.

[00:03:35]
You drop it. We're just looking at it. We're just still log n. It's fantastic. We're so fast. Deletions follow the same principle. You gotta find the item. You gotta do potentially some moving. You gotta do the deletion. Then you gotta walk all the way back up. So again, it would be 2log n.

[00:03:49]
Delete the 2. So there we go. So we now know the running time. How is everyone feeling? Feeling good? Are we feeling good? Do you have questions? Come on, what's the questions? I know there's at least one of them.
>> What are some use cases for this one?

[00:04:06]
>> AVL tree? It's that if you're just constructing a binary search tree on the fly and you don't want to just have the linked list problem, right? Because at some point, if you're just inserting elements into a tree, it eventually just falls apart. Because if you insert it in order, you create worst ordered tree.

[00:04:24]
You'd have to accidentally insert it in median, left, right, left, right, left, right, left, right. You'd have to be correct on your insertion. And so, we just don't have to think about that, instead, you just maintain it this way. And typically, you're gonna wanna use an AVL if you are search-heavy, right?

[00:04:43]
Cuz if you're search-heavy, you're just getting the best possible time always. But if you're insertion-heavy, you may not want to use this one. You may want to use a red black tree, which does not organize the tree nearly as tight as an AVL. But it will allow still log and search and insertion and the deletion.

[00:05:05]
So it's a little bit different. The rules are much more complicated on a red black tree than they are on an AVL. People say red black trees are easier to implement, that they're nicer. I have yet to believe that. I think AVL trees are fantastic. And I think they're simple.

[00:05:17]
So, maybe it's a perspective problem here, all right.
>> If insertions and deletions are both log n, what are the issues with an AVL tree?
>> It just requires rotations, right? So if you already have a balanced tree, when you insert something, you don't have to re-walk back up and check for every single one of these rotations.

[00:05:38]
So obviously, rotations are done in constant time, but you still have to do a bunch of stuff. So it's constant, but it still requires work. And so but you have to do that constant check, and potentially, that constant rotation every single node up the tree. So it's just slower, right?

[00:05:52]
AVL is just simply gonna be slower, but it's more complete. It's a nicer tree that gets generated.
>> How do you practice this stuff, getting to know these? I guess this is more general question, but do you think of use cases or do you like to practice it with whiteboarding specifically, or?

[00:06:14]
>> I have a whiteboard at home, but my daughter ruins all my whiteboard by drawing on them with permanent marker. And so, my favorite one is there's the book. Everybody knows the book. If you know the algorithms book, it's like you start to see this little thing. There's a leaf and a tree, and then there's four authors right here.

[00:06:34]
And I think the current iteration is the 3rd version, which is brown background. I forget the name of it, but it's the algorithms book. It's 600 pages long. It's a thick book. You could kill somebody with this book. It is gigantic. You might even kill yourself on accident.

[00:06:51]
It's huge. It's extremely technical. CRLS book, that's what they call it. CRLS, I'm sure each one of these are an author. But it's an awesome algorithms book. I used it in college. I've bought in it twice or three times or purchased it, bought in it, bought in it, botanist.

[00:07:10]
I'm a botanist, but I have purchased it three times maybe in the course of my lifetime, and I've lost it yet again. And so I'm actually you're probably gonna re-buy this book because it is such a good book. And so typically, I like practicing algorithms. I like looking at them.

[00:07:25]
So a few times a year, I'll go on YouTube and just watch through them cuz they're just really fun to think about. I don't know, I enjoy the process of knowing how to do that. And then every now and then at your job, you'll run into something and you'll go, aha, union fine path compression.

[00:07:39]
And you'll just be able to use an algorithm that people won't know about, because you have something in the talk at all times. And so it's good to just know they exist. I always made this joke that I will hire somebody as long as they say the word priority queue, cuz I just want you to know that they exist, because at some point, you might need a priority queue.

[00:07:56]
But if you don't have a concept that they exist, you can't even know how to solve a problem in an efficient manner. And so, it leads to all these weird oddities if you just don't even have the thing in your head. So that's kind of how I always like to joke about it in my head.

[00:08:10]
It's not true if you don't say the word priority queue, it's not like I'm gonna say no to you, but you get the idea. The more complete picture you have of what is available, I think it's easier to solve problems, just in general. Even if you rarely use them, you know how to move everything around in your head.

[00:08:28]
And I think it's just a really good exercise to be able to see larger problems at once in your head. It's kind of practicing the abstraction. And I think it just makes me a better. I mostly develop tools, so I deal a lot with trees and things like that at work.

[00:08:41]
But because I develop tools, I constantly have to think about algorithms cuz they come into play pretty regularly. But kind of like I have the vision of the landscape of what's available. And so as I solve these problems, it just feels easier to put together all the things, cuz it's like putting together an algorithm.

[00:08:58]
It's the same kinda concept. Anyways, I don't know, I think it's good. Anytime you can make a concept go from something abstract in your head to practical in an editor, it's just like you're just plus one in your ability to solve larger and larger problems. So, that's my advice.

[00:09:13]
Solve them, do them, enjoy them, experience them.
>> Do you use these a lot on if you're traversing the file system?
>> Yeah, a file system is a forest. A file system is a tree, but it's also more than a tree because of symlinks. Here we go. We're about to mention it.

[00:09:31]
Everyone makes fun of me every time I mention this, Falcor. If you've heard of Falcor, it's one of the first data-fetching libraries out there in JavaScript that's meant to aggregate all the requests into something that's like GraphQL. It was developed. We actually used to go to Facebook and talk to Facebook about GraphQL before GraphQL.

[00:09:48]
And we'd be like, how are you solving this? How are you doing this? And it is the identical problem as a file system. Cuz a file system is just a general tree. But then at some point, you have a symlink that is another tree, but that technically, you need it to be transparent right here.

[00:10:03]
So it feels you're just walking through it, but it actually is somewhere else as well. And so this is the same problem as Falcor. So you can kind of think of filesystem. In my head, I like to think of it like a forest, even though it's better to think of it like a tree.

[00:10:16]
It's just like there's a root place. So, there you go. That's all you got. It's fun times file systems. They're way more complicated than this. This is just the world's simplest version. Please, don't take these things for gospel, cuz someone's gonna be like, well, actually, did you know about?

[00:10:32]
That I'm gonna be like, yeah, okay, cool, great story. You get the idea.