I often see people get confused by binary search tree balancing. This is very fair, because all the algorithms to make it work are quite complicated, and understanding them deeply is a lot of work.
But the misconceptions I see are often not about the mechanics of BST balancing, which are legitimately really complicated, but about the motivation and goals of these mechanisms. So I’ve written a few brief notes here in the hope that they let people understand what BST balancing mechanisms are supposed to do.
The key selling point of a BST is that it has O(log(n)) search and modification. The O(log(n)) here comes from the height of the tree. So we just require that the height of the tree doesn’t grow to more than a constant factor of the logarithm of the number of nodes.
Two common balancing mechanisms are AVL trees and red-black trees. In a red-black tree, the maintained invariant is that the paths from the root to a leaf can’t differ in length by more than a factor of two. So it’s fine for your left subtree