From the course: Python Data Structures: Trees
Join today to access over 22,600 courses taught by industry experts or purchase this course individually.
Detecting unbalanced trees - Python Tutorial
From the course: Python Data Structures: Trees
Detecting unbalanced trees
- [Instructor] Well, adding and deleting all of these nodes, you've probably noticed that some trees get what computer scientists call unbalanced. For instance, if we have this tree, 25, 50, 75 this could obviously be more concisely written in a different way as 50, 25 and 75. All the same values, but in a much more compact tree. And this isn't just a matter of some frivolous aesthetics. The more levels of tree has, the longer it can take the search it, even if the number of nodes is the same. For instance, if we want to find the 75, we need to make two hops in the previous tree. But with this one, it's just to check to see if 75 is greater than or less than 50. Obviously not a big deal in this case, but imagine you're doing millions of tree lookups perhaps with very large trees, this becomes a huge deal. So it's critically important to be able to detect when trees are unbalanced and be able to prevent or fix imbalances.…
Download courses and learn on the go
Watch courses on your mobile device without an internet connection. Download courses using your iOS or Android LinkedIn Learning app.