Transcript from the "Analysis of Time Complexity" Lesson

[00:00:00]

>> Bianca Gandolfo: So let's talk about time complexity of our binary search tree. What operations have we done so far?

>> off screen male: What operations have we done the tree?

>> Bianca Gandolfo: So what methods have we built for it?

>> off screen male: Insert.

>> Bianca Gandolfo: Insert.

>> off screen male: Contains.

>> Bianca Gandolfo: Contains.

>> off screen male: Delete.

>> Bianca Gandolfo: Delete.

>> off screen male: And then we had the-

[00:00:21]

>> off screen female: We had all the traversals.

>> off screen male: Traversals, yeah, the depth [INAUDIBLE] traversals.

>> Bianca Gandolfo: Yep, yep, so for insert, what is the worst case runtime?

>> off screen male: Linear?

>> Bianca Gandolfo: Linear, why is it linear?

>> off screen male: If you had to go through every single node to find the right place to put it.

[00:00:46] Well, you wouldn't really do that because it's already sorted.

>> Bianca Gandolfo: Well, it's linear for the case where it's basically a linked list, right? If it's just 11, 7, 5, 3 like that, it would just be essentially a linked list and so to get to insert maybe 2, then that would be a linear operation.

[00:01:14] So that's the worst case.

>> off screen female: It's logarithmic, isn't it?

>> Bianca Gandolfo: It's logarithmic in the average-

>> off screen female: In the average case.

>> Bianca Gandolfo: In the average case, yeah. And that's because of the binary nature of the binary search tree, right? We want to be able to cut in half our problem every single time.

[00:01:33] And what that requires is a balanced binary search tree. So there's a bunch of algorithms that will in different kinds of trees that will keep that balance. But our binary search tree does not have any method that keeps it balanced and keeps it from becoming a link list.

[00:01:50] So tree's balance when the levels in any given branch are no more than one further. So if three had two and then one, that would make it unbalanced. But if three only had a two sticking out, it would still be considered balanced.

>> Bianca Gandolfo: Does that make sense? So it's the degree in which it's from the last layer.

[00:02:27]

>> Bianca Gandolfo: And with balance comes

>> Bianca Gandolfo: Faster insert and removal. Cool, so we insert, what else do we do?

>> Bianca Gandolfo: What else do we do? We inserted, we traversed. What's the runtime of any traversal?

>> off screen female: Linear.

>> Bianca Gandolfo: Linear. Why?

>> off screen female: Because they have to visit each one.

>> Bianca Gandolfo: Yep.

[00:03:03] So it's just the nature of a traversal is you explore every node in a tree and because of that, it's gonna be linear time. Cool. What about our delete?

>> off screen male: So the delete itself should be constant? But you might have to search to perform delete, which could be linear?

[00:03:26]

>> Bianca Gandolfo: So let's look at our picture again. So if we wanted to delete 18, so first, you're right, we have to get there. Right? So searching for it. And the worst case, that's gonna be linear if this is a link list, right?

>> Bianca Gandolfo: And then yeah, the delete action itself, right, just swapping and reassigning more or less is gonna be a constant time operation.

[00:04:02]

>> Bianca Gandolfo: Cool. Okay, all right, great. So if you are intrigued by binary trees and you're like I wanna have a more performant one. Performant is not a real word but we use it in software engineering. I don't know why. But an AVL tree, a Red-Black tree, and Splay trees are all balanced trees, that will optimize your binary search tree.

[00:04:30] So look into them. They're pretty cool and they're fun. Cool, so that's binary search trees. We went through a lot. And the delete step is a doozy, right? It's doable but there are a lot of little moving pieces there.