Complexity and Balancing a Binary Tree
A strange phenomenon that happens with binary trees is that they get unbalanced. As we saw, this only happens with certain sequences of inputs. instead of having nodes that branch evenly, we end up with a linked list. In this section, we’re going to explore why this is a problem. Let’s first start with looking at the benefits of a tree, especially when searching for a node.
Complexity
So binary trees give us a huge benefit in terms of possible worst-case search space. We refer to this as complexity and it is usually written with the notation O(N) (pronounced Oh-of-N). Linked lists would have an O(n) worst-case for searching while Binaries Trees would also have an O(n) worst case, if not balanced. However, if we balance our trees perfectly we will be able to have an O(log2n) complexity. If we look at the video example log2(11) = 4, where the total number of elements is 11, This translates to a lot of saved time when it comes to really large data sets!
Balancing Binary Trees
In your problem set, you will follow an algorithm for balancing a binary tree. Below is the general overview of how that balancing algorithm works. Remember, each node figures out its own height, and each node is responsible to balance its subtree.